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