001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.actions;
003
004import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
005import static org.openstreetmap.josm.tools.I18n.tr;
006
007import java.awt.event.ActionEvent;
008import java.awt.event.KeyEvent;
009import java.util.ArrayList;
010import java.util.Arrays;
011import java.util.Collection;
012import java.util.Comparator;
013import java.util.LinkedList;
014import java.util.List;
015
016import javax.swing.JOptionPane;
017
018import org.openstreetmap.josm.Main;
019import org.openstreetmap.josm.command.AddCommand;
020import org.openstreetmap.josm.command.ChangeCommand;
021import org.openstreetmap.josm.command.Command;
022import org.openstreetmap.josm.command.SequenceCommand;
023import org.openstreetmap.josm.data.coor.EastNorth;
024import org.openstreetmap.josm.data.coor.LatLon;
025import org.openstreetmap.josm.data.osm.Node;
026import org.openstreetmap.josm.data.osm.OsmPrimitive;
027import org.openstreetmap.josm.data.osm.Way;
028import org.openstreetmap.josm.gui.Notification;
029import org.openstreetmap.josm.tools.Geometry;
030import org.openstreetmap.josm.tools.Shortcut;
031
032/**
033 * - Create a new circle from two selected nodes or a way with 2 nodes which represent the diameter of the circle.
034 * - Create a new circle from three selected nodes--or a way with 3 nodes.
035 * - Useful for roundabouts
036 *
037 * Notes:
038 *   * If a way is selected, it is changed. If nodes are selected a new way is created.
039 *     So if you've got a way with nodes it makes a difference between running this on the way or the nodes!
040 *   * The existing nodes are retained, and additional nodes are inserted regularly
041 *     to achieve the desired number of nodes (`createcircle.nodecount`).
042 * BTW: Someone might want to implement projection corrections for this...
043 *
044 * @since 996
045 *
046 * @author Henry Loenwind
047 * @author Sebastian Masch
048 * @author Alain Delplanque
049 */
050public final class CreateCircleAction extends JosmAction {
051
052    /**
053     * Constructs a new {@code CreateCircleAction}.
054     */
055    public CreateCircleAction() {
056        super(tr("Create Circle"), "aligncircle", tr("Create a circle from three selected nodes."),
057            Shortcut.registerShortcut("tools:createcircle", tr("Tool: {0}", tr("Create Circle")),
058            KeyEvent.VK_O, Shortcut.SHIFT), true, "createcircle", true);
059        putValue("help", ht("/Action/CreateCircle"));
060    }
061
062    /**
063     * Distributes nodes according to the algorithm of election with largest remainder.
064     * @param angles Array of PolarNode ordered by increasing angles
065     * @param nodesCount Number of nodes to be distributed
066     * @return Array of number of nodes to put in each arc
067     */
068    private int[] distributeNodes(PolarNode[] angles, int nodesCount) {
069        int[] count = new int[angles.length];
070        double[] width = new double[angles.length];
071        double[] remainder = new double[angles.length];
072        for(int i = 0; i < angles.length; i++) {
073            width[i] = angles[(i+1) % angles.length].a - angles[i].a;
074            if(width[i] < 0)
075                width[i] += 2*Math.PI;
076        }
077        int assign = 0;
078        for(int i = 0; i < angles.length; i++) {
079            double part = width[i] / 2.0 / Math.PI * nodesCount;
080            count[i] = (int) Math.floor(part);
081            remainder[i] = part - count[i];
082            assign += count[i];
083        }
084        while(assign < nodesCount) {
085            int imax = 0;
086            for(int i = 1; i < angles.length; i++)
087                if(remainder[i] > remainder[imax])
088                    imax = i;
089            count[imax]++;
090            remainder[imax] = 0;
091            assign++;
092        }
093        return count;
094    }
095
096    /**
097     * Class designed to create a couple between a node and its angle relative to the center of the circle.
098     */
099    private static class PolarNode {
100        double a;
101        Node node;
102
103        PolarNode(EastNorth center, Node n) {
104            EastNorth pt = n.getEastNorth();
105            this.a = Math.atan2(pt.north() - center.north(), pt.east() - center.east());
106            this.node = n;
107        }
108    }
109
110    /**
111     * Comparator used to order PolarNode relative to their angle.
112     */
113    private static class PolarNodeComparator implements Comparator<PolarNode> {
114
115        @Override
116        public int compare(PolarNode pc1, PolarNode pc2) {
117            if(pc1.a < pc2.a)
118                return -1;
119            else if(pc1.a == pc2.a)
120                return 0;
121            else
122                return 1;
123        }
124    }
125
126    @Override
127    public void actionPerformed(ActionEvent e) {
128        if (!isEnabled())
129            return;
130
131        int numberOfNodesInCircle = Main.pref.getInteger("createcircle.nodecount", 16);
132        if (numberOfNodesInCircle < 1) {
133            numberOfNodesInCircle = 1;
134        } else if (numberOfNodesInCircle > 100) {
135            numberOfNodesInCircle = 100;
136        }
137
138        Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
139        List<Node> nodes = new LinkedList<>();
140        Way existingWay = null;
141
142        for (OsmPrimitive osm : sel)
143            if (osm instanceof Node) {
144                nodes.add((Node)osm);
145            }
146
147        // special case if no single nodes are selected and exactly one way is:
148        // then use the way's nodes
149        if (nodes.isEmpty() && (sel.size() == 1)) {
150            for (OsmPrimitive osm : sel)
151                if (osm instanceof Way) {
152                    existingWay = ((Way)osm);
153                    for (Node n : ((Way)osm).getNodes())
154                    {
155                        if(!nodes.contains(n)) {
156                            nodes.add(n);
157                        }
158                    }
159                }
160        }
161
162        if (nodes.size() < 2 || nodes.size() > 3) {
163            new Notification(
164                    tr("Please select exactly two or three nodes or one way with exactly two or three nodes."))
165                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
166                    .setDuration(Notification.TIME_LONG)
167                    .show();
168            return;
169        }
170
171        // now we can start doing things to OSM data
172        Collection<Command> cmds = new LinkedList<>();
173        EastNorth center = null;
174
175        if (nodes.size() == 2) {
176            // diameter: two single nodes needed or a way with two nodes
177            Node   n1 = nodes.get(0);
178            double x1 = n1.getEastNorth().east();
179            double y1 = n1.getEastNorth().north();
180            Node   n2 = nodes.get(1);
181            double x2 = n2.getEastNorth().east();
182            double y2 = n2.getEastNorth().north();
183
184            // calculate the center (xc/yc)
185            double xc = 0.5 * (x1 + x2);
186            double yc = 0.5 * (y1 + y2);
187            center = new EastNorth(xc, yc);
188        } else {
189            // triangle: three single nodes needed or a way with three nodes
190            center = Geometry.getCenter(nodes);
191            if (center == null) {
192                notifyNodesNotOnCircle();
193                return;
194            }
195        }
196
197        // calculate the radius (r)
198        EastNorth n1 = nodes.get(0).getEastNorth();
199        double r = Math.sqrt(Math.pow(center.east()-n1.east(),2) +
200                Math.pow(center.north()-n1.north(),2));
201
202        // Order nodes by angle
203        PolarNode[] angles = new PolarNode[nodes.size()];
204        for(int i = 0; i < nodes.size(); i++) {
205            angles[i] = new PolarNode(center, nodes.get(i));
206        }
207        Arrays.sort(angles, new PolarNodeComparator());
208        int[] count = distributeNodes(angles,
209                numberOfNodesInCircle >= nodes.size() ? numberOfNodesInCircle - nodes.size() : 0);
210
211        // build a way for the circle
212        List<Node> wayToAdd = new ArrayList<>();
213        for(int i = 0; i < nodes.size(); i++) {
214            wayToAdd.add(angles[i].node);
215            double delta = angles[(i+1) % nodes.size()].a - angles[i].a;
216            if(delta < 0)
217                delta += 2*Math.PI;
218            for(int j = 0; j < count[i]; j++) {
219                double alpha = angles[i].a + (j+1)*delta/(count[i]+1);
220                double x = center.east() + r*Math.cos(alpha);
221                double y = center.north() + r*Math.sin(alpha);
222                LatLon ll = Main.getProjection().eastNorth2latlon(new EastNorth(x,y));
223                if (ll.isOutSideWorld()) {
224                    notifyNodesNotOnCircle();
225                    return;
226                }
227                Node n = new Node(ll);
228                wayToAdd.add(n);
229                cmds.add(new AddCommand(n));
230            }
231        }
232        wayToAdd.add(wayToAdd.get(0)); // close the circle
233        if (existingWay == null) {
234            Way newWay = new Way();
235            newWay.setNodes(wayToAdd);
236            cmds.add(new AddCommand(newWay));
237        } else {
238            Way newWay = new Way(existingWay);
239            newWay.setNodes(wayToAdd);
240            cmds.add(new ChangeCommand(existingWay, newWay));
241        }
242
243        Main.main.undoRedo.add(new SequenceCommand(tr("Create Circle"), cmds));
244        Main.map.repaint();
245    }
246
247    private static void notifyNodesNotOnCircle() {
248        new Notification(
249                tr("Those nodes are not in a circle. Aborting."))
250                .setIcon(JOptionPane.WARNING_MESSAGE)
251                .show();
252    }
253
254    @Override
255    protected void updateEnabledState() {
256        if (getCurrentDataSet() == null) {
257            setEnabled(false);
258        } else {
259            updateEnabledState(getCurrentDataSet().getSelected());
260        }
261    }
262
263    @Override
264    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
265        setEnabled(selection != null && !selection.isEmpty());
266    }
267}