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.osm.Node;
028import org.openstreetmap.josm.data.osm.OsmPrimitive;
029import org.openstreetmap.josm.data.osm.Way;
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        putValue("help", 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 {
104        private final double a;
105        private final Node node;
106
107        PolarNode(EastNorth center, Node n) {
108            EastNorth pt = n.getEastNorth();
109            this.a = Math.atan2(pt.north() - center.north(), pt.east() - center.east());
110            this.node = n;
111        }
112    }
113
114    /**
115     * Comparator used to order PolarNode relative to their angle.
116     */
117    private static class PolarNodeComparator implements Comparator<PolarNode>, Serializable {
118        private static final long serialVersionUID = 1L;
119
120        @Override
121        public int compare(PolarNode pc1, PolarNode pc2) {
122            return Double.compare(pc1.a, pc2.a);
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 = getLayerManager().getEditDataSet().getSelected();
139        List<Node> nodes = OsmPrimitive.getFilteredList(sel, Node.class);
140        List<Way> ways = OsmPrimitive.getFilteredList(sel, Way.class);
141
142        Way existingWay = null;
143
144        // special case if no single nodes are selected and exactly one way is:
145        // then use the way's nodes
146        if (nodes.isEmpty() && (ways.size() == 1)) {
147            existingWay = ways.get(0);
148            for (Node n : existingWay.getNodes()) {
149                if (!nodes.contains(n)) {
150                    nodes.add(n);
151                }
152            }
153        }
154
155        if (nodes.size() < 2 || nodes.size() > 3) {
156            new Notification(
157                    tr("Please select exactly two or three nodes or one way with exactly two or three nodes."))
158                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
159                    .setDuration(Notification.TIME_LONG)
160                    .show();
161            return;
162        }
163
164        EastNorth center;
165
166        if (nodes.size() == 2) {
167            // diameter: two single nodes needed or a way with two nodes
168            Node n1 = nodes.get(0);
169            double x1 = n1.getEastNorth().east();
170            double y1 = n1.getEastNorth().north();
171            Node n2 = nodes.get(1);
172            double x2 = n2.getEastNorth().east();
173            double y2 = n2.getEastNorth().north();
174
175            // calculate the center (xc/yc)
176            double xc = 0.5 * (x1 + x2);
177            double yc = 0.5 * (y1 + y2);
178            center = new EastNorth(xc, yc);
179        } else {
180            // triangle: three single nodes needed or a way with three nodes
181            center = Geometry.getCenter(nodes);
182            if (center == null) {
183                notifyNodesNotOnCircle();
184                return;
185            }
186        }
187
188        // calculate the radius (r)
189        EastNorth n1 = nodes.get(0).getEastNorth();
190        double r = Math.sqrt(Math.pow(center.east()-n1.east(), 2) +
191                Math.pow(center.north()-n1.north(), 2));
192
193        // Order nodes by angle
194        PolarNode[] angles = new PolarNode[nodes.size()];
195        for (int i = 0; i < nodes.size(); i++) {
196            angles[i] = new PolarNode(center, nodes.get(i));
197        }
198        Arrays.sort(angles, new PolarNodeComparator());
199        int[] count = distributeNodes(angles,
200                numberOfNodesInCircle >= nodes.size() ? (numberOfNodesInCircle - nodes.size()) : 0);
201
202        // now we can start doing things to OSM data
203        Collection<Command> cmds = new LinkedList<>();
204
205        // build a way for the circle
206        List<Node> nodesToAdd = new ArrayList<>();
207        for (int i = 0; i < nodes.size(); i++) {
208            nodesToAdd.add(angles[i].node);
209            double delta = angles[(i+1) % nodes.size()].a - angles[i].a;
210            if (delta < 0)
211                delta += 2*Math.PI;
212            for (int j = 0; j < count[i]; j++) {
213                double alpha = angles[i].a + (j+1)*delta/(count[i]+1);
214                double x = center.east() + r*Math.cos(alpha);
215                double y = center.north() + r*Math.sin(alpha);
216                LatLon ll = Main.getProjection().eastNorth2latlon(new EastNorth(x, y));
217                if (ll.isOutSideWorld()) {
218                    notifyNodesNotOnCircle();
219                    return;
220                }
221                Node n = new Node(ll);
222                nodesToAdd.add(n);
223                cmds.add(new AddCommand(n));
224            }
225        }
226        nodesToAdd.add(nodesToAdd.get(0)); // close the circle
227        if (existingWay != null && existingWay.getNodesCount() >= 3) {
228            nodesToAdd = orderNodesByWay(nodesToAdd, existingWay);
229        } else {
230            nodesToAdd = orderNodesByTrafficHand(nodesToAdd);
231        }
232        if (existingWay == null) {
233            Way newWay = new Way();
234            newWay.setNodes(nodesToAdd);
235            cmds.add(new AddCommand(newWay));
236        } else {
237            Way newWay = new Way(existingWay);
238            newWay.setNodes(nodesToAdd);
239            cmds.add(new ChangeCommand(existingWay, newWay));
240        }
241
242        Main.main.undoRedo.add(new SequenceCommand(tr("Create Circle"), cmds));
243    }
244
245    /**
246     * Order nodes according to left/right hand traffic.
247     * @param nodes Nodes list to be ordered.
248     * @return Modified nodes list ordered according hand traffic.
249     */
250    private static List<Node> orderNodesByTrafficHand(List<Node> nodes) {
251        boolean rightHandTraffic = true;
252        for (Node n: nodes) {
253            if (!RightAndLefthandTraffic.isRightHandTraffic(n.getCoor())) {
254                rightHandTraffic = false;
255                break;
256            }
257        }
258        if (rightHandTraffic == Geometry.isClockwise(nodes)) {
259            Collections.reverse(nodes);
260        }
261        return nodes;
262    }
263
264    /**
265     * Order nodes according to way direction.
266     * @param nodes Nodes list to be ordered.
267     * @param way Way used to determine direction.
268     * @return Modified nodes list with same direction as way.
269     */
270    private static List<Node> orderNodesByWay(List<Node> nodes, Way way) {
271        List<Node> wayNodes = way.getNodes();
272        if (!way.isClosed()) {
273            wayNodes.add(wayNodes.get(0));
274        }
275        if (Geometry.isClockwise(wayNodes) != Geometry.isClockwise(nodes)) {
276            Collections.reverse(nodes);
277        }
278        return nodes;
279    }
280
281    private static void notifyNodesNotOnCircle() {
282        new Notification(
283                tr("Those nodes are not in a circle. Aborting."))
284                .setIcon(JOptionPane.WARNING_MESSAGE)
285                .show();
286    }
287
288    @Override
289    protected void updateEnabledState() {
290        updateEnabledStateOnCurrentSelection();
291    }
292
293    @Override
294    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
295        setEnabled(selection != null && !selection.isEmpty());
296    }
297}