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