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