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