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