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

Last change on this file since 10371 was 10347, checked in by Don-vip, 8 years ago

sonar - add unit test to see if squid:S1244 can be safely disabled
  • Property svn:eol-style set to native
File size: 16.3 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.Main;
20import org.openstreetmap.josm.command.Command;
21import org.openstreetmap.josm.command.MoveCommand;
22import org.openstreetmap.josm.command.SequenceCommand;
23import org.openstreetmap.josm.data.coor.EastNorth;
24import org.openstreetmap.josm.data.osm.Node;
25import org.openstreetmap.josm.data.osm.OsmPrimitive;
26import org.openstreetmap.josm.data.osm.Way;
27import org.openstreetmap.josm.gui.Notification;
28import org.openstreetmap.josm.tools.Shortcut;
29
30/**
31 * Aligns all selected nodes into a straight line (useful for roads that should be straight, but have side roads and
32 * therefore need multiple nodes)
33 *
34 * <pre>
35 * Case 1: 1 or 2 ways selected and no nodes selected: align nodes of ways taking care of intersection.
36 * Case 2: Single node selected and no ways selected: align this node relative to all referrer ways (2 at most).
37 * Case 3: Single node and ways selected: align this node relative to selected ways.
38 * Case 4.1: Only nodes selected, part of a non-closed way: align these nodes on the line passing through the
39 * extremity nodes (most distant in the way sequence). See https://josm.openstreetmap.de/ticket/9605#comment:3
40 * Case 4.2: Only nodes selected, part of a closed way: align these nodes on the line passing through the most distant nodes.
41 * Case 4.3: Only nodes selected, part of multiple ways: align these nodes on the line passing through the most distant nodes.
42 * </pre>
43 *
44 * @author Matthew Newton
45 */
46public final class AlignInLineAction extends JosmAction {
47
48 /**
49 * Constructs a new {@code AlignInLineAction}.
50 */
51 public AlignInLineAction() {
52 super(tr("Align Nodes in Line"), "alignline", tr("Move the selected nodes in to a line."),
53 Shortcut.registerShortcut("tools:alignline", tr("Tool: {0}", tr("Align Nodes in Line")), KeyEvent.VK_L, Shortcut.DIRECT), true);
54 putValue("help", ht("/Action/AlignInLine"));
55 }
56
57 /**
58 * InvalidSelection exception has to be raised when action can't be performed
59 */
60 static class InvalidSelection extends Exception {
61
62 /**
63 * Create an InvalidSelection exception with default message
64 */
65 InvalidSelection() {
66 super(tr("Please select at least three nodes."));
67 }
68
69 /**
70 * Create an InvalidSelection exception with specific message
71 * @param msg Message that will be displayed to the user
72 */
73 InvalidSelection(String msg) {
74 super(msg);
75 }
76 }
77
78 /**
79 * Return 2 nodes making up the line along which provided nodes must be aligned.
80 *
81 * @param nodes Nodes to be aligned.
82 * @return A array of two nodes.
83 * @throws IllegalArgumentException if nodes is empty
84 */
85 private static Node[] nodePairFurthestApart(List<Node> nodes) {
86 // Detect if selected nodes are on the same way.
87
88 // Get ways passing though all selected nodes.
89 Set<Way> waysRef = null;
90 for (Node n: nodes) {
91 Collection<Way> ref = OsmPrimitive.getFilteredList(n.getReferrers(), Way.class);
92 if (waysRef == null)
93 waysRef = new HashSet<>(ref);
94 else
95 waysRef.retainAll(ref);
96 }
97
98 if (waysRef == null) {
99 throw new IllegalArgumentException();
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 Node nodea = null;
115 Node nodeb = null;
116
117 // The way is open, align nodes on the line passing through the extremity nodes (most distant in the way
118 // sequence). See #9605#comment:3.
119 Set<Node> remainNodes = new HashSet<>(nodes);
120 for (Node n : way.getNodes()) {
121 if (!remainNodes.contains(n))
122 continue;
123 if (nodea == null)
124 nodea = n;
125 if (remainNodes.size() == 1) {
126 nodeb = remainNodes.iterator().next();
127 break;
128 }
129 remainNodes.remove(n);
130 }
131
132 return new Node[] {nodea, nodeb};
133 }
134
135 /**
136 * Return the two nodes the most distant from the provided list.
137 *
138 * @param nodes List of nodes to analyze.
139 * @return An array containing the two most distant nodes.
140 */
141 private static Node[] nodeFurthestAppart(List<Node> nodes) {
142 Node node1 = null, node2 = null;
143 double minSqDistance = 0;
144 int nb;
145
146 nb = nodes.size();
147 for (int i = 0; i < nb - 1; i++) {
148 Node n = nodes.get(i);
149 for (int j = i + 1; j < nb; j++) {
150 Node m = nodes.get(j);
151 double sqDist = n.getEastNorth().distanceSq(m.getEastNorth());
152 if (sqDist > minSqDistance) {
153 node1 = n;
154 node2 = m;
155 minSqDistance = sqDist;
156 }
157 }
158 }
159
160 return new Node[] {node1, node2};
161 }
162
163 /**
164 * Operation depends on the selected objects:
165 */
166 @Override
167 public void actionPerformed(ActionEvent e) {
168 if (!isEnabled())
169 return;
170
171 List<Node> selectedNodes = new ArrayList<>(getCurrentDataSet().getSelectedNodes());
172 List<Way> selectedWays = new ArrayList<>(getCurrentDataSet().getSelectedWays());
173
174 try {
175 Command cmd;
176 // Decide what to align based on selection:
177
178 if (selectedNodes.isEmpty() && !selectedWays.isEmpty()) {
179 // Only ways selected -> For each way align their nodes taking care of intersection
180 cmd = alignMultiWay(selectedWays);
181 } else if (selectedNodes.size() == 1) {
182 // Only 1 node selected -> align this node relative to referers way
183 Node selectedNode = selectedNodes.get(0);
184 List<Way> involvedWays;
185 if (selectedWays.isEmpty())
186 // No selected way, all way containing this node are used
187 involvedWays = OsmPrimitive.getFilteredList(selectedNode.getReferrers(), Way.class);
188 else
189 // Selected way, use only these ways
190 involvedWays = selectedWays;
191 List<Line> lines = getInvolvedLines(selectedNode, involvedWays);
192 if (lines.size() > 2 || lines.isEmpty())
193 throw new InvalidSelection();
194 cmd = alignSingleNode(selectedNodes.get(0), lines);
195 } else if (selectedNodes.size() >= 3) {
196 // More than 3 nodes and way(s) selected -> align selected nodes. Don't care of way(s).
197 cmd = alignOnlyNodes(selectedNodes);
198 } else {
199 // All others cases are invalid
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 static 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 }
230 return new SequenceCommand(tr("Align Nodes in Line"), cmds);
231 }
232
233 /**
234 * Align way in case of multiple way #6819
235 * @param ways Collection of way to align
236 * @return Command that perform action
237 * @throws InvalidSelection if a polygon is selected, or if a node is used by 3 or more ways
238 */
239 private static Command alignMultiWay(Collection<Way> ways) throws InvalidSelection {
240 // Collect all nodes and compute line equation
241 Set<Node> nodes = new HashSet<>();
242 Map<Way, Line> lines = new HashMap<>();
243 for (Way w: ways) {
244 if (w.isClosed())
245 throw new InvalidSelection(tr("Can not align a polygon. Abort."));
246 nodes.addAll(w.getNodes());
247 lines.put(w, new Line(w));
248 }
249 Collection<Command> cmds = new ArrayList<>(nodes.size());
250 List<Way> referers = new ArrayList<>(ways.size());
251 for (Node n: nodes) {
252 referers.clear();
253 for (OsmPrimitive o: n.getReferrers()) {
254 if (ways.contains(o))
255 referers.add((Way) o);
256 }
257 if (referers.size() == 1) {
258 Way way = referers.get(0);
259 if (way.isFirstLastNode(n)) continue;
260 cmds.add(lines.get(way).projectionCommand(n));
261 } else if (referers.size() == 2) {
262 Command cmd = lines.get(referers.get(0)).intersectionCommand(n, lines.get(referers.get(1)));
263 cmds.add(cmd);
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 if a node got more than 4 neighbours (self-crossing way)
276 */
277 private static 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 }
289 if (neighbors.isEmpty())
290 continue;
291 else if (neighbors.size() == 2)
292 // Non self crossing
293 lines.add(new Line(neighbors.get(0), neighbors.get(1)));
294 else if (neighbors.size() == 4) {
295 // Self crossing, have to make 2 lines with 4 neighbors
296 // see #9081 comment 6
297 EastNorth c = node.getEastNorth();
298 double[] angle = new double[4];
299 for (int i = 0; i < 4; i++) {
300 EastNorth p = neighbors.get(i).getEastNorth();
301 angle[i] = Math.atan2(p.north() - c.north(), p.east() - c.east());
302 }
303 double[] deltaAngle = new double[3];
304 for (int i = 0; i < 3; i++) {
305 deltaAngle[i] = angle[i+1] - angle[0];
306 if (deltaAngle[i] < 0)
307 deltaAngle[i] += 2*Math.PI;
308 }
309 int nb = 0;
310 if (deltaAngle[1] < deltaAngle[0]) nb++;
311 if (deltaAngle[2] < deltaAngle[0]) nb++;
312 if (nb == 1) {
313 // Align along [neighbors[0], neighbors[1]] and [neighbors[0], neighbors[2]]
314 lines.add(new Line(neighbors.get(0), neighbors.get(1)));
315 lines.add(new Line(neighbors.get(2), neighbors.get(3)));
316 } else {
317 // Align along [neighbors[0], neighbors[2]] and [neighbors[1], neighbors[3]]
318 lines.add(new Line(neighbors.get(0), neighbors.get(2)));
319 lines.add(new Line(neighbors.get(1), neighbors.get(3)));
320 }
321 } else
322 throw new InvalidSelection("cannot treat more than 4 neighbours, got "+neighbors.size());
323 }
324 return lines;
325 }
326
327 /**
328 * Align a single node relative to a set of lines #9081
329 * @param node Node to be aligned
330 * @param lines Lines to align node on
331 * @return Command that perform action
332 * @throws InvalidSelection if more than 2 lines
333 */
334 private static Command alignSingleNode(Node node, List<Line> lines) throws InvalidSelection {
335 if (lines.size() == 1)
336 return lines.get(0).projectionCommand(node);
337 else if (lines.size() == 2)
338 return lines.get(0).intersectionCommand(node, lines.get(1));
339 throw new InvalidSelection();
340 }
341
342 /**
343 * Class that represent a line
344 */
345 static class Line {
346
347 /**
348 * Line equation ax + by + c = 0
349 * Such as a^2 + b^2 = 1, ie (-b, a) is a unit vector of line
350 */
351 private double a, b, c;
352 /**
353 * (xM, yM) are coordinates of a point of the line
354 */
355 private double xM, yM;
356
357 /**
358 * Init a line by 2 nodes.
359 * @param first One point of the line
360 * @param last Other point of the line
361 * @throws InvalidSelection if nodes have same coordinates
362 */
363 Line(Node first, Node last) throws InvalidSelection {
364 xM = first.getEastNorth().getX();
365 yM = first.getEastNorth().getY();
366 double xB = last.getEastNorth().getX();
367 double yB = last.getEastNorth().getY();
368 a = yB - yM;
369 b = xM - xB;
370 double norm = Math.sqrt(a*a + b*b);
371 if (norm == 0)
372 throw new InvalidSelection("Nodes have same coordinates!");
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 if nodes have same coordinates
382 */
383 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 if two parallels ways found
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}
Note: See TracBrowser for help on using the repository browser.