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.HashMap;
012import java.util.HashSet;
013import java.util.List;
014import java.util.Map;
015import java.util.Set;
016
017import javax.swing.JOptionPane;
018
019import org.openstreetmap.josm.Main;
020import org.openstreetmap.josm.command.Command;
021import org.openstreetmap.josm.command.MoveCommand;
022import org.openstreetmap.josm.command.SequenceCommand;
023import org.openstreetmap.josm.data.coor.EastNorth;
024import org.openstreetmap.josm.data.osm.DataSet;
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.Shortcut;
030
031/**
032 * Aligns all selected nodes into a straight line (useful for roads that should be straight, but have side roads and
033 * therefore need multiple nodes)
034 *
035 * <pre>
036 * Case 1: 1 or 2 ways selected and no nodes selected: align nodes of ways taking care of intersection.
037 * Case 2: Single node selected and no ways selected: align this node relative to all referrer ways (2 at most).
038 * Case 3: Single node and ways selected: align this node relative to selected ways.
039 * Case 4.1: Only nodes selected, part of a non-closed way: align these nodes on the line passing through the
040 *   extremity nodes (most distant in the way sequence). See https://josm.openstreetmap.de/ticket/9605#comment:3
041 * Case 4.2: Only nodes selected, part of a closed way: align these nodes on the line passing through the most distant nodes.
042 * Case 4.3: Only nodes selected, part of multiple ways: align these nodes on the line passing through the most distant nodes.
043 * </pre>
044 *
045 * @author Matthew Newton
046 */
047public final class AlignInLineAction extends JosmAction {
048
049    /**
050     * Constructs a new {@code AlignInLineAction}.
051     */
052    public AlignInLineAction() {
053        super(tr("Align Nodes in Line"), "alignline", tr("Move the selected nodes in to a line."),
054                Shortcut.registerShortcut("tools:alignline", tr("Tool: {0}", tr("Align Nodes in Line")), KeyEvent.VK_L, Shortcut.DIRECT), true);
055        putValue("help", ht("/Action/AlignInLine"));
056    }
057
058    /**
059     * InvalidSelection exception has to be raised when action can't be performed
060     */
061    static class InvalidSelection extends Exception {
062
063        /**
064         * Create an InvalidSelection exception with default message
065         */
066        InvalidSelection() {
067            super(tr("Please select at least three nodes."));
068        }
069
070        /**
071         * Create an InvalidSelection exception with specific message
072         * @param msg Message that will be displayed to the user
073         */
074        InvalidSelection(String msg) {
075            super(msg);
076        }
077    }
078
079    /**
080     * Return 2 nodes making up the line along which provided nodes must be aligned.
081     *
082     * @param nodes Nodes to be aligned.
083     * @return A array of two nodes.
084     * @throws IllegalArgumentException if nodes is empty
085     */
086    private static Node[] nodePairFurthestApart(List<Node> nodes) {
087        // Detect if selected nodes are on the same way.
088
089        // Get ways passing though all selected nodes.
090        Set<Way> waysRef = null;
091        for (Node n: nodes) {
092            Collection<Way> ref = OsmPrimitive.getFilteredList(n.getReferrers(), Way.class);
093            if (waysRef == null)
094                waysRef = new HashSet<>(ref);
095            else
096                waysRef.retainAll(ref);
097        }
098
099        if (waysRef == null) {
100            throw new IllegalArgumentException();
101        }
102
103        // Nodes belongs to multiple ways, return most distant nodes.
104        if (waysRef.size() != 1)
105            return nodeFurthestAppart(nodes);
106
107        // All nodes are part of the same way. See #9605.
108        Way way = waysRef.iterator().next();
109
110        if (way.isClosed()) {
111            // Align these nodes on the line passing through the most distant nodes.
112            return nodeFurthestAppart(nodes);
113        }
114
115        Node nodea = null;
116        Node nodeb = null;
117
118        // The way is open, align nodes on the line passing through the extremity nodes (most distant in the way
119        // sequence). See #9605#comment:3.
120        Set<Node> remainNodes = new HashSet<>(nodes);
121        for (Node n : way.getNodes()) {
122            if (!remainNodes.contains(n))
123                continue;
124            if (nodea == null)
125                nodea = n;
126            if (remainNodes.size() == 1) {
127                nodeb = remainNodes.iterator().next();
128                break;
129            }
130            remainNodes.remove(n);
131        }
132
133        return new Node[] {nodea, nodeb};
134    }
135
136    /**
137     * Return the two nodes the most distant from the provided list.
138     *
139     * @param nodes List of nodes to analyze.
140     * @return An array containing the two most distant nodes.
141     */
142    private static Node[] nodeFurthestAppart(List<Node> nodes) {
143        Node node1 = null, node2 = null;
144        double minSqDistance = 0;
145        int nb;
146
147        nb = nodes.size();
148        for (int i = 0; i < nb - 1; i++) {
149            Node n = nodes.get(i);
150            for (int j = i + 1; j < nb; j++) {
151                Node m = nodes.get(j);
152                double sqDist = n.getEastNorth().distanceSq(m.getEastNorth());
153                if (sqDist > minSqDistance) {
154                    node1 = n;
155                    node2 = m;
156                    minSqDistance = sqDist;
157                }
158            }
159        }
160
161        return new Node[] {node1, node2};
162    }
163
164    /**
165     * Operation depends on the selected objects:
166     */
167    @Override
168    public void actionPerformed(ActionEvent e) {
169        if (!isEnabled())
170            return;
171
172        DataSet ds = getLayerManager().getEditDataSet();
173        List<Node> selectedNodes = new ArrayList<>(ds.getSelectedNodes());
174        List<Way> selectedWays = new ArrayList<>(ds.getSelectedWays());
175
176        try {
177            Command cmd;
178            // Decide what to align based on selection:
179
180            if (selectedNodes.isEmpty() && !selectedWays.isEmpty()) {
181                // Only ways selected -> For each way align their nodes taking care of intersection
182                cmd = alignMultiWay(selectedWays);
183            } else if (selectedNodes.size() == 1) {
184                // Only 1 node selected -> align this node relative to referers way
185                Node selectedNode = selectedNodes.get(0);
186                List<Way> involvedWays;
187                if (selectedWays.isEmpty())
188                    // No selected way, all way containing this node are used
189                    involvedWays = OsmPrimitive.getFilteredList(selectedNode.getReferrers(), Way.class);
190                else
191                    // Selected way, use only these ways
192                    involvedWays = selectedWays;
193                List<Line> lines = getInvolvedLines(selectedNode, involvedWays);
194                if (lines.size() > 2 || lines.isEmpty())
195                    throw new InvalidSelection();
196                cmd = alignSingleNode(selectedNodes.get(0), lines);
197            } else if (selectedNodes.size() >= 3) {
198                // More than 3 nodes and way(s) selected -> align selected nodes. Don't care of way(s).
199                cmd = alignOnlyNodes(selectedNodes);
200            } else {
201                // All others cases are invalid
202                throw new InvalidSelection();
203            }
204
205            // Do it!
206            Main.main.undoRedo.add(cmd);
207
208        } catch (InvalidSelection except) {
209            Main.debug(except);
210            new Notification(except.getMessage())
211                .setIcon(JOptionPane.INFORMATION_MESSAGE)
212                .show();
213        }
214    }
215
216    /**
217     * Align nodes in case 3 or more nodes are selected.
218     *
219     * @param nodes Nodes to be aligned.
220     * @return Command that perform action.
221     * @throws InvalidSelection If the nodes have same coordinates.
222     */
223    private static Command alignOnlyNodes(List<Node> nodes) throws InvalidSelection {
224        // Choose nodes used as anchor points for projection.
225        Node[] anchors = nodePairFurthestApart(nodes);
226        Collection<Command> cmds = new ArrayList<>(nodes.size());
227        Line line = new Line(anchors[0], anchors[1]);
228        for (Node node: nodes) {
229            if (node != anchors[0] && node != anchors[1])
230                cmds.add(line.projectionCommand(node));
231        }
232        return new SequenceCommand(tr("Align Nodes in Line"), cmds);
233    }
234
235    /**
236     * Align way in case of multiple way #6819
237     * @param ways Collection of way to align
238     * @return Command that perform action
239     * @throws InvalidSelection if a polygon is selected, or if a node is used by 3 or more ways
240     */
241    private static Command alignMultiWay(Collection<Way> ways) throws InvalidSelection {
242        // Collect all nodes and compute line equation
243        Set<Node> nodes = new HashSet<>();
244        Map<Way, Line> lines = new HashMap<>();
245        for (Way w: ways) {
246            if (w.isClosed())
247                throw new InvalidSelection(tr("Can not align a polygon. Abort."));
248            nodes.addAll(w.getNodes());
249            lines.put(w, new Line(w));
250        }
251        Collection<Command> cmds = new ArrayList<>(nodes.size());
252        List<Way> referers = new ArrayList<>(ways.size());
253        for (Node n: nodes) {
254            referers.clear();
255            for (OsmPrimitive o: n.getReferrers()) {
256                if (ways.contains(o))
257                    referers.add((Way) o);
258            }
259            if (referers.size() == 1) {
260                Way way = referers.get(0);
261                if (way.isFirstLastNode(n)) continue;
262                cmds.add(lines.get(way).projectionCommand(n));
263            } else if (referers.size() == 2) {
264                Command cmd = lines.get(referers.get(0)).intersectionCommand(n, lines.get(referers.get(1)));
265                cmds.add(cmd);
266            } else
267                throw new InvalidSelection(tr("Intersection of three or more ways can not be solved. Abort."));
268        }
269        return new SequenceCommand(tr("Align Nodes in Line"), cmds);
270    }
271
272    /**
273     * Get lines useful to do alignment of a single node
274     * @param node Node to be aligned
275     * @param refWays Ways where useful lines will be searched
276     * @return List of useful lines
277     * @throws InvalidSelection if a node got more than 4 neighbours (self-crossing way)
278     */
279    private static List<Line> getInvolvedLines(Node node, List<Way> refWays) throws InvalidSelection {
280        List<Line> lines = new ArrayList<>();
281        List<Node> neighbors = new ArrayList<>();
282        for (Way way: refWays) {
283            List<Node> nodes = way.getNodes();
284            neighbors.clear();
285            for (int i = 1; i < nodes.size()-1; i++) {
286                if (nodes.get(i) == node) {
287                    neighbors.add(nodes.get(i-1));
288                    neighbors.add(nodes.get(i+1));
289                }
290            }
291            if (neighbors.isEmpty())
292                continue;
293            else if (neighbors.size() == 2)
294                // Non self crossing
295                lines.add(new Line(neighbors.get(0), neighbors.get(1)));
296            else if (neighbors.size() == 4) {
297                // Self crossing, have to make 2 lines with 4 neighbors
298                // see #9081 comment 6
299                EastNorth c = node.getEastNorth();
300                double[] angle = new double[4];
301                for (int i = 0; i < 4; i++) {
302                    EastNorth p = neighbors.get(i).getEastNorth();
303                    angle[i] = Math.atan2(p.north() - c.north(), p.east() - c.east());
304                }
305                double[] deltaAngle = new double[3];
306                for (int i = 0; i < 3; i++) {
307                    deltaAngle[i] = angle[i+1] - angle[0];
308                    if (deltaAngle[i] < 0)
309                        deltaAngle[i] += 2*Math.PI;
310                }
311                int nb = 0;
312                if (deltaAngle[1] < deltaAngle[0]) nb++;
313                if (deltaAngle[2] < deltaAngle[0]) nb++;
314                if (nb == 1) {
315                    // Align along [neighbors[0], neighbors[1]] and [neighbors[0], neighbors[2]]
316                    lines.add(new Line(neighbors.get(0), neighbors.get(1)));
317                    lines.add(new Line(neighbors.get(2), neighbors.get(3)));
318                } else {
319                    // Align along [neighbors[0], neighbors[2]] and [neighbors[1], neighbors[3]]
320                    lines.add(new Line(neighbors.get(0), neighbors.get(2)));
321                    lines.add(new Line(neighbors.get(1), neighbors.get(3)));
322                }
323            } else
324                throw new InvalidSelection("cannot treat more than 4 neighbours, got "+neighbors.size());
325        }
326        return lines;
327    }
328
329    /**
330     * Align a single node relative to a set of lines #9081
331     * @param node Node to be aligned
332     * @param lines Lines to align node on
333     * @return Command that perform action
334     * @throws InvalidSelection if more than 2 lines
335     */
336    private static Command alignSingleNode(Node node, List<Line> lines) throws InvalidSelection {
337        if (lines.size() == 1)
338            return lines.get(0).projectionCommand(node);
339        else if (lines.size() == 2)
340            return lines.get(0).intersectionCommand(node, lines.get(1));
341        throw new InvalidSelection();
342    }
343
344    /**
345     * Class that represent a line
346     */
347    static class Line {
348
349        /**
350         * Line equation ax + by + c = 0
351         * Such as a^2 + b^2 = 1, ie (-b, a) is a unit vector of line
352         */
353        private double a, b, c;
354        /**
355         * (xM, yM) are coordinates of a point of the line
356         */
357        private double xM, yM;
358
359        /**
360         * Init a line by 2 nodes.
361         * @param first One point of the line
362         * @param last Other point of the line
363         * @throws InvalidSelection if nodes have same coordinates
364         */
365        Line(Node first, Node last) throws InvalidSelection {
366            xM = first.getEastNorth().getX();
367            yM = first.getEastNorth().getY();
368            double xB = last.getEastNorth().getX();
369            double yB = last.getEastNorth().getY();
370            a = yB - yM;
371            b = xM - xB;
372            double norm = Math.sqrt(a*a + b*b);
373            if (norm == 0)
374                throw new InvalidSelection("Nodes have same coordinates!");
375            a /= norm;
376            b /= norm;
377            c = -(a*xM + b*yM);
378        }
379
380        /**
381         * Init a line equation from a way.
382         * @param way Use extremity of this way to compute line equation
383         * @throws InvalidSelection if nodes have same coordinates
384         */
385        Line(Way way) throws InvalidSelection {
386            this(way.firstNode(), way.lastNode());
387        }
388
389        /**
390         * Orthogonal projection of a node N along this line.
391         * @param n Node to be projected
392         * @return The command that do the projection of this node
393         */
394        public Command projectionCommand(Node n) {
395            double s = (xM - n.getEastNorth().getX()) * a + (yM - n.getEastNorth().getY()) * b;
396            return new MoveCommand(n, a*s, b*s);
397        }
398
399        /**
400         * Intersection of two line.
401         * @param n Node to move to the intersection
402         * @param other Second line for intersection
403         * @return The command that move the node
404         * @throws InvalidSelection if two parallels ways found
405         */
406        public Command intersectionCommand(Node n, Line other) throws InvalidSelection {
407            double d = this.a * other.b - other.a * this.b;
408            if (Math.abs(d) < 10e-6)
409                // parallels lines
410                throw new InvalidSelection(tr("Two parallels ways found. Abort."));
411            double x = (this.b * other.c - other.b * this.c) / d;
412            double y = (other.a * this.c - this.a * other.c) / d;
413            return new MoveCommand(n, x - n.getEastNorth().getX(), y - n.getEastNorth().getY());
414        }
415    }
416
417    @Override
418    protected void updateEnabledState() {
419        DataSet ds = getLayerManager().getEditDataSet();
420        setEnabled(ds != null && !ds.selectionEmpty());
421    }
422
423    @Override
424    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
425        setEnabled(selection != null && !selection.isEmpty());
426    }
427}