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

Last change on this file since 16136 was 16136, checked in by GerdP, 4 years ago

see #18928: improve notification when empty way is used in Align nodes
  • Property svn:eol-style set to native
File size: 16.9 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.UndoRedoHandler;
23import org.openstreetmap.josm.data.coor.EastNorth;
24import org.openstreetmap.josm.data.coor.PolarCoor;
25import org.openstreetmap.josm.data.osm.DataSet;
26import org.openstreetmap.josm.data.osm.Node;
27import org.openstreetmap.josm.data.osm.OsmPrimitive;
28import org.openstreetmap.josm.data.osm.Way;
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 setHelpId(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 UndoRedoHandler.getInstance().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(w -> w.isIncomplete() || w.isEmpty());
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 if (!w.isEmpty()) {
259 nodes.addAll(w.getNodes());
260 lines.put(w, new Line(w));
261 }
262 }
263 if (nodes.isEmpty()) {
264 throw new InvalidSelection(tr("Intersection of three or more ways can not be solved. Abort."));
265 }
266 Collection<Command> cmds = new ArrayList<>(nodes.size());
267 List<Way> referers = new ArrayList<>(ways.size());
268 for (Node n: nodes) {
269 referers.clear();
270 for (OsmPrimitive o: n.getReferrers()) {
271 if (ways.contains(o))
272 referers.add((Way) o);
273 }
274 if (referers.size() == 1) {
275 Way way = referers.get(0);
276 if (way.isFirstLastNode(n)) continue;
277 cmds.add(lines.get(way).projectionCommand(n));
278 } else if (referers.size() == 2) {
279 cmds.add(lines.get(referers.get(0)).intersectionCommand(n, lines.get(referers.get(1))));
280 } else
281 throw new InvalidSelection(tr("Intersection of three or more ways can not be solved. Abort."));
282 }
283 return cmds.isEmpty() ? null : new SequenceCommand(tr("Align Nodes in Line"), cmds);
284 }
285
286 /**
287 * Get lines useful to do alignment of a single node
288 * @param node Node to be aligned
289 * @param refWays Ways where useful lines will be searched
290 * @return List of useful lines
291 * @throws InvalidSelection if a node got more than 4 neighbours (self-crossing way)
292 */
293 private static List<Line> getInvolvedLines(Node node, List<Way> refWays) throws InvalidSelection {
294 List<Line> lines = new ArrayList<>();
295 List<Node> neighbors = new ArrayList<>();
296 for (Way way: refWays) {
297 List<Node> nodes = way.getNodes();
298 neighbors.clear();
299 for (int i = 1; i < nodes.size()-1; i++) {
300 if (nodes.get(i) == node) {
301 neighbors.add(nodes.get(i-1));
302 neighbors.add(nodes.get(i+1));
303 }
304 }
305 if (neighbors.isEmpty())
306 continue;
307 else if (neighbors.size() == 2)
308 // Non self crossing
309 lines.add(new Line(neighbors.get(0), neighbors.get(1)));
310 else if (neighbors.size() == 4) {
311 // Self crossing, have to make 2 lines with 4 neighbors
312 // see #9081 comment 6
313 EastNorth c = node.getEastNorth();
314 double[] angle = new double[4];
315 for (int i = 0; i < 4; i++) {
316 angle[i] = PolarCoor.computeAngle(neighbors.get(i).getEastNorth(), c);
317 }
318 double[] deltaAngle = new double[3];
319 for (int i = 0; i < 3; i++) {
320 deltaAngle[i] = angle[i+1] - angle[0];
321 if (deltaAngle[i] < 0)
322 deltaAngle[i] += 2*Math.PI;
323 }
324 int nb = 0;
325 if (deltaAngle[1] < deltaAngle[0]) nb++;
326 if (deltaAngle[2] < deltaAngle[0]) nb++;
327 if (nb == 1) {
328 // Align along [neighbors[0], neighbors[1]] and [neighbors[0], neighbors[2]]
329 lines.add(new Line(neighbors.get(0), neighbors.get(1)));
330 lines.add(new Line(neighbors.get(2), neighbors.get(3)));
331 } else {
332 // Align along [neighbors[0], neighbors[2]] and [neighbors[1], neighbors[3]]
333 lines.add(new Line(neighbors.get(0), neighbors.get(2)));
334 lines.add(new Line(neighbors.get(1), neighbors.get(3)));
335 }
336 } else
337 throw new InvalidSelection("cannot treat more than 4 neighbours, got "+neighbors.size());
338 }
339 return lines;
340 }
341
342 /**
343 * Align a single node relative to a set of lines #9081
344 * @param node Node to be aligned
345 * @param lines Lines to align node on
346 * @return Command that perform action
347 * @throws InvalidSelection if more than 2 lines
348 */
349 private static Command alignSingleNode(Node node, List<Line> lines) throws InvalidSelection {
350 if (lines.size() == 1)
351 return lines.get(0).projectionCommand(node);
352 else if (lines.size() == 2)
353 return lines.get(0).intersectionCommand(node, lines.get(1));
354 throw new InvalidSelection();
355 }
356
357 /**
358 * Class that represent a line
359 */
360 static class Line {
361
362 /**
363 * Line equation ax + by + c = 0
364 * Such as a^2 + b^2 = 1, ie (-b, a) is a unit vector of line
365 */
366 private double a, b, c;
367 /**
368 * (xM, yM) are coordinates of a point of the line
369 */
370 private double xM, yM;
371
372 /**
373 * Init a line by 2 nodes.
374 * @param first One point of the line
375 * @param last Other point of the line
376 * @throws InvalidSelection if nodes have same coordinates
377 */
378 Line(Node first, Node last) throws InvalidSelection {
379 xM = first.getEastNorth().getX();
380 yM = first.getEastNorth().getY();
381 double xB = last.getEastNorth().getX();
382 double yB = last.getEastNorth().getY();
383 a = yB - yM;
384 b = xM - xB;
385 double norm = Math.sqrt(a*a + b*b);
386 if (norm == 0)
387 throw new InvalidSelection("Nodes have same coordinates!");
388 a /= norm;
389 b /= norm;
390 c = -(a*xM + b*yM);
391 }
392
393 /**
394 * Init a line equation from a way.
395 * @param way Use extremity of this way to compute line equation
396 * @throws InvalidSelection if nodes have same coordinates
397 */
398 Line(Way way) throws InvalidSelection {
399 this(way.firstNode(), way.lastNode());
400 }
401
402 /**
403 * Orthogonal projection of a node N along this line.
404 * @param n Node to be projected
405 * @return The command that do the projection of this node
406 */
407 public Command projectionCommand(Node n) {
408 double s = (xM - n.getEastNorth().getX()) * a + (yM - n.getEastNorth().getY()) * b;
409 return new MoveCommand(n, a*s, b*s);
410 }
411
412 /**
413 * Intersection of two line.
414 * @param n Node to move to the intersection
415 * @param other Second line for intersection
416 * @return The command that move the node
417 * @throws InvalidSelection if two parallels ways found
418 */
419 public Command intersectionCommand(Node n, Line other) throws InvalidSelection {
420 double d = this.a * other.b - other.a * this.b;
421 if (Math.abs(d) < 10e-6)
422 // parallels lines
423 throw new InvalidSelection(tr("Two parallels ways found. Abort."));
424 double x = (this.b * other.c - other.b * this.c) / d;
425 double y = (other.a * this.c - this.a * other.c) / d;
426 return new MoveCommand(n, x - n.getEastNorth().getX(), y - n.getEastNorth().getY());
427 }
428 }
429
430 @Override
431 protected void updateEnabledState() {
432 DataSet ds = getLayerManager().getEditDataSet();
433 setEnabled(ds != null && !ds.selectionEmpty());
434 }
435
436 @Override
437 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
438 updateEnabledStateOnModifiableSelection(selection);
439 }
440}
Note: See TracBrowser for help on using the repository browser.