source: josm/trunk/src/org/openstreetmap/josm/actions/AlignInLineAction.java@ 13312

Last change on this file since 13312 was 13108, checked in by Don-vip, 6 years ago

fix #15538 - add robustness to AlignInLineAction
  • Property svn:eol-style set to native
File size: 16.8 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
5import static org.openstreetmap.josm.tools.I18n.tr;
6
7import java.awt.event.ActionEvent;
8import java.awt.event.KeyEvent;
9import java.util.ArrayList;
10import java.util.Collection;
11import java.util.HashMap;
12import java.util.HashSet;
13import java.util.List;
14import java.util.Map;
15import java.util.Set;
16
17import javax.swing.JOptionPane;
18
19import org.openstreetmap.josm.command.Command;
20import org.openstreetmap.josm.command.MoveCommand;
21import org.openstreetmap.josm.command.SequenceCommand;
22import org.openstreetmap.josm.data.coor.EastNorth;
23import org.openstreetmap.josm.data.coor.PolarCoor;
24import org.openstreetmap.josm.data.osm.DataSet;
25import org.openstreetmap.josm.data.osm.Node;
26import org.openstreetmap.josm.data.osm.OsmPrimitive;
27import org.openstreetmap.josm.data.osm.Way;
28import org.openstreetmap.josm.gui.MainApplication;
29import org.openstreetmap.josm.gui.Notification;
30import org.openstreetmap.josm.tools.Logging;
31import org.openstreetmap.josm.tools.Shortcut;
32
33/**
34 * Aligns all selected nodes into a straight line (useful for roads that should be straight, but have side roads and
35 * therefore need multiple nodes)
36 *
37 * <pre>
38 * Case 1: 1 or 2 ways selected and no nodes selected: align nodes of ways taking care of intersection.
39 * Case 2: Single node selected and no ways selected: align this node relative to all referrer ways (2 at most).
40 * Case 3: Single node and ways selected: align this node relative to selected ways.
41 * Case 4.1: Only nodes selected, part of a non-closed way: align these nodes on the line passing through the
42 * extremity nodes (most distant in the way sequence). See https://josm.openstreetmap.de/ticket/9605#comment:3
43 * Case 4.2: Only nodes selected, part of a closed way: align these nodes on the line passing through the most distant nodes.
44 * Case 4.3: Only nodes selected, part of multiple ways: align these nodes on the line passing through the most distant nodes.
45 * </pre>
46 *
47 * @author Matthew Newton
48 */
49public final class AlignInLineAction extends JosmAction {
50
51 /**
52 * Constructs a new {@code AlignInLineAction}.
53 */
54 public AlignInLineAction() {
55 super(tr("Align Nodes in Line"), "alignline", tr("Move the selected nodes in to a line."),
56 Shortcut.registerShortcut("tools:alignline", tr("Tool: {0}", tr("Align Nodes in Line")), KeyEvent.VK_L, Shortcut.DIRECT), true);
57 putValue("help", ht("/Action/AlignInLine"));
58 }
59
60 /**
61 * InvalidSelection exception has to be raised when action can't be performed
62 */
63 static class InvalidSelection extends Exception {
64
65 /**
66 * Create an InvalidSelection exception with default message
67 */
68 InvalidSelection() {
69 super(tr("Please select at least three nodes."));
70 }
71
72 /**
73 * Create an InvalidSelection exception with specific message
74 * @param msg Message that will be displayed to the user
75 */
76 InvalidSelection(String msg) {
77 super(msg);
78 }
79 }
80
81 /**
82 * Return 2 nodes making up the line along which provided nodes must be aligned.
83 *
84 * @param nodes Nodes to be aligned.
85 * @return A array of two nodes.
86 * @throws IllegalArgumentException if nodes is empty
87 */
88 private static Node[] nodePairFurthestApart(List<Node> nodes) {
89 // Detect if selected nodes are on the same way.
90
91 // Get ways passing though all selected nodes.
92 Set<Way> waysRef = null;
93 for (Node n: nodes) {
94 Collection<Way> ref = n.getParentWays();
95 if (waysRef == null)
96 waysRef = new HashSet<>(ref);
97 else
98 waysRef.retainAll(ref);
99 }
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 MainApplication.undoRedo.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 setEnabled(selection != null && !selection.isEmpty());
437 }
438}
Note: See TracBrowser for help on using the repository browser.