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