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