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