source: josm/trunk/src/org/openstreetmap/josm/actions/OrthogonalizeAction.java@ 2484

Last change on this file since 2484 was 2323, checked in by Gubaer, 15 years ago

Added explicit help topics
See also current list of help topics with links to source files and to help pages
File size: 22.5 KB
Line 
1// License: GPL. See LICENSE file for details.
2//
3package org.openstreetmap.josm.actions;
4
5import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
6import static org.openstreetmap.josm.tools.I18n.tr;
7
8import java.awt.event.ActionEvent;
9import java.awt.event.KeyEvent;
10import java.util.ArrayList;
11import java.util.Arrays;
12import java.util.Collection;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.LinkedList;
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.ConditionalOptionPaneUtil;
28import org.openstreetmap.josm.tools.Shortcut;
29
30/**
31 * Tools / Orthogonalize
32 *
33 * Align edges of a way so all angles are angles of 90 or 180 degrees.
34 * See USAGE String below.
35 */
36public final class OrthogonalizeAction extends JosmAction {
37 String USAGE = "<h3>"+
38 "When one or more ways are selected, the shape is adjusted, such that all angles are 90 or 180 degrees.<h3>"+
39 "You can add two nodes to the selection. Then the direction is fixed by these two reference nodes.<h3>"+
40 "(Afterwards, you can undo the movement for certain nodes:<br>"+
41 "Select them and press the shortcut for Orthogonalize / Undo. The default is Shift-Q.)";
42
43 public OrthogonalizeAction() {
44 super(tr("Orthogonalize Shape"),
45 "ortho",
46 tr("Move nodes so all angles are 90 or 270 degree"),
47 Shortcut.registerShortcut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize Shape")),
48 KeyEvent.VK_Q,
49 Shortcut.GROUP_EDIT), true);
50 putValue("help", ht("/Action/Orthogonalize"));
51 }
52
53 /**
54 * excepted deviation from an angle of 0, 90, 180, 360 degrees
55 * maximum value: 45 degrees
56 */
57 private static final double TOLERANCE1 = Math.toRadians(35.); // within a way
58 private static final double TOLERANCE2 = Math.toRadians(35.); // ways relative to each other
59
60 /**
61 * Remember movements, so the user can later undo it for certain nodes
62 */
63 private static final HashMap<Node, EastNorth> rememberMovements = new HashMap<Node, EastNorth>();
64
65 /**
66 * Undo the previous orthogonalization for certain nodes.
67 *
68 * This is useful, if the way shares nodes that you don't like to change, e.g. imports or
69 * work of another user.
70 *
71 * This action can be triggered by shortcut only.
72 */
73 public class Undo extends JosmAction {
74 public Undo() {
75 super(tr("Orthogonalize Shape / Undo"),
76 "ortho",
77 tr("Undo orthogonalization for certain nodes"),
78 Shortcut.registerShortcut("tools:orthogonalizeUndo", tr("Tool: {0}", tr("Orthogonalize Shape / Undo")),
79 KeyEvent.VK_Q,
80 Shortcut.GROUP_EDIT, Shortcut.SHIFT_DEFAULT), true);
81 }
82 public void actionPerformed(ActionEvent e) {
83 if (!isEnabled())
84 return;
85 final Collection<Command> commands = new LinkedList<Command>();
86 final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
87 try {
88 for (OsmPrimitive p : sel) {
89 if (! (p instanceof Node)) throw new InvalidUserInputException();
90 Node n = (Node) p;
91 if (rememberMovements.containsKey(n)) {
92 EastNorth tmp = rememberMovements.get(n);
93 commands.add(new MoveCommand(n, - tmp.east(), - tmp.north()));
94 rememberMovements.remove(n);
95 }
96 }
97 if (commands.size() > 0) {
98 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize / Undo"), commands));
99 Main.map.repaint();
100 } else throw new InvalidUserInputException();
101 }
102 catch (InvalidUserInputException ex) {
103 JOptionPane.showMessageDialog(
104 Main.parent,
105 tr("Orthogonalize Shape / Undo\n"+
106 "Please select nodes that were moved by the previous Orthogonalize Shape action!"),
107 tr("Undo Orthogonalize Shape"),
108 JOptionPane.INFORMATION_MESSAGE);
109 }
110 }
111 }
112
113 public void actionPerformed(ActionEvent e) {
114 if (!isEnabled())
115 return;
116 if ("EPSG:4326".equals(Main.proj.toString())) {
117 String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" +
118 "to undesirable results when doing rectangular alignments.<br>" +
119 "Change your projection to get rid of this warning.<br>" +
120 "Do you want to continue?</html>");
121 if (!ConditionalOptionPaneUtil.showConfirmationDialog(
122 "align_rectangular_4326",
123 Main.parent,
124 msg,
125 tr("Warning"),
126 JOptionPane.YES_NO_OPTION,
127 JOptionPane.QUESTION_MESSAGE,
128 JOptionPane.YES_OPTION))
129 return;
130 }
131
132 final ArrayList<Node> nodeList = new ArrayList<Node>();
133 final ArrayList<WayData> wayDataList = new ArrayList<WayData>();
134 final Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected();
135
136 try {
137 // collect nodes and ways from the selection
138 for (OsmPrimitive p : sel) {
139 if (p instanceof Node) {
140 nodeList.add((Node) p);
141 }
142 else if (p instanceof Way) {
143 wayDataList.add(new WayData((Way) p));
144 }
145 else { // maybe a relation got selected...
146 throw new InvalidUserInputException("Selection must consist only of ways and nodes.");
147 }
148 }
149 if (wayDataList.isEmpty()) {
150 throw new InvalidUserInputException("usage");
151 }
152 else {
153 if (nodeList.size() == 2) {
154 orthogonalize(wayDataList, nodeList);
155 }
156 else if (nodeList.isEmpty()) {
157 orthogonalize(wayDataList, nodeList);
158 }
159 else {
160 throw new InvalidUserInputException("usage");
161 }
162 }
163 } catch (InvalidUserInputException ex) {
164 if (ex.getMessage().equals("usage")) {
165 JOptionPane.showMessageDialog(
166 Main.parent,
167 "<html><h2>"+tr("Usage")+tr(USAGE),
168 tr("Orthogonalize Shape"),
169 JOptionPane.INFORMATION_MESSAGE);
170 }
171 else {
172 JOptionPane.showMessageDialog(
173 Main.parent,
174 "<html><h3>"+tr(ex.getMessage())+"<br><hr><h3>"+tr("Usage")+tr(USAGE),
175 tr("Selected Elements cannot be orthogonalized"),
176 JOptionPane.INFORMATION_MESSAGE);
177 }
178 }
179 }
180
181 /**
182 *
183 * Outline:
184 * 1. Find direction of all segments
185 * - direction = 0..3 (right,up,left,down)
186 * - right is not really right, you may have to turn your screen
187 * 2. Find average heading of all segments
188 * - heading = angle of a vector in polar coordinates
189 * - sum up horizontal segments (those with direction 0 or 2)
190 * - sum up vertical segments
191 * - turn the vertical sum by 90 degrees and add it to the horizontal sum
192 * - get the average heading from this total sum
193 * 3. Rotate all nodes by the average heading so that right is really right
194 * and all segments are approximately NS or EW.
195 * 4. If nodes are connected by a horizontal segment: Replace their y-Coordinate by
196 * the mean value of their y-Coordinates.
197 * - The same for vertical segments.
198 * 5. Rotate back.
199 *
200 **/
201 private static void orthogonalize(ArrayList<WayData> wayDataList, ArrayList<Node> headingNodes)
202 throws InvalidUserInputException
203 {
204 // find average heading
205 double headingAll;
206 try {
207 if (headingNodes.isEmpty()) {
208 // find directions of the segments and make them consistent between different ways
209 wayDataList.get(0).calcDirections(Direction.RIGHT);
210 double refHeading = wayDataList.get(0).heading;
211 for (WayData w : wayDataList) {
212 w.calcDirections(Direction.RIGHT);
213 int directionOffset = angleToDirectionChange(w.heading - refHeading, TOLERANCE2);
214 w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
215 if (angleToDirectionChange(refHeading - w.heading, TOLERANCE2) != 0) throw new RuntimeException();
216 }
217 EastNorth totSum = new EastNorth(0., 0.);
218 for (WayData w : wayDataList) {
219 totSum = EN.sum(totSum, w.segSum);
220 }
221 headingAll = EN.polar(new EastNorth(0., 0.), totSum);
222 }
223 else {
224 headingAll = EN.polar(headingNodes.get(0).getEastNorth(), headingNodes.get(1).getEastNorth());
225 for (WayData w : wayDataList) {
226 w.calcDirections(Direction.RIGHT);
227 int directionOffset = angleToDirectionChange(w.heading - headingAll, TOLERANCE2);
228 w.calcDirections(Direction.RIGHT.changeBy(directionOffset));
229 }
230 }
231 } catch (RejectedAngleException ex) {
232 throw new InvalidUserInputException(
233 "<html>Please make sure all selected ways head in a similar direction<br>"+
234 "or orthogonalize them one by one.");
235 }
236
237 // put the nodes of all ways in a set
238 final HashSet<Node> allNodes = new HashSet<Node>();
239 for (WayData w : wayDataList) {
240 for (Node n : w.way.getNodes()) {
241 allNodes.add(n);
242 }
243 }
244
245 // the new x and y value for each node
246 final HashMap<Node, Double> nX = new HashMap<Node, Double>();
247 final HashMap<Node, Double> nY = new HashMap<Node, Double>();
248
249 // caluclate the centroid of all nodes
250 // it is used as rotation center
251 EastNorth pivot = new EastNorth(0., 0.);
252 for (Node n : allNodes) {
253 pivot = EN.sum(pivot, n.getEastNorth());
254 }
255 pivot = new EastNorth(pivot.east() / allNodes.size(), pivot.north() / allNodes.size());
256
257 // rotate
258 for (Node n: allNodes) {
259 EastNorth tmp = EN.rotate_cc(pivot, n.getEastNorth(), - headingAll);
260 nX.put(n, tmp.east());
261 nY.put(n, tmp.north());
262 }
263
264 // orthogonalize
265 final Direction[] HORIZONTAL = {Direction.RIGHT, Direction.LEFT};
266 final Direction[] VERTICAL = {Direction.UP, Direction.DOWN};
267 final Direction[][] ORIENTATIONS = {HORIZONTAL, VERTICAL};
268 for (Direction[] orientation : ORIENTATIONS){
269 final HashSet<Node> s = new HashSet<Node>(allNodes);
270 int s_size = s.size();
271 for (int dummy = 0; dummy < s_size; ++ dummy) {
272 if (s.isEmpty()) break;
273 final Node dummy_n = s.iterator().next(); // pick arbitrary element of s
274
275 final HashSet<Node> cs = new HashSet<Node>(); // will contain each node that can be reached from dummy_n
276 cs.add(dummy_n); // walking only on horizontal / vertical segments
277
278 boolean somethingHappened = true;
279 while (somethingHappened) {
280 somethingHappened = false;
281 for (WayData w : wayDataList) {
282 for (int i=0; i < w.nSeg; ++i) {
283 Node n1 = w.way.getNodes().get(i);
284 Node n2 = w.way.getNodes().get(i+1);
285 if (Arrays.asList(orientation).contains(w.segDirections[i])) {
286 if (cs.contains(n1) && ! cs.contains(n2)) {
287 cs.add(n2);
288 somethingHappened = true;
289 }
290 if (cs.contains(n2) && ! cs.contains(n1)) {
291 cs.add(n1);
292 somethingHappened = true;
293 }
294 }
295 }
296 }
297 }
298
299 final HashMap<Node, Double> nC = (orientation == HORIZONTAL) ? nY : nX;
300
301 double average = 0;
302 for (Node n : cs) {
303 average += nC.get(n).doubleValue();
304 }
305 average = average / cs.size();
306
307 // if one of the nodes is a heading node, forget about the average and use its value
308 for (Node fn : headingNodes) {
309 if (cs.contains(fn)) {
310 average = nC.get(fn);
311 }
312 }
313
314 for (Node n : cs) {
315 nC.put(n, average);
316 }
317
318 for (Node n : cs) {
319 s.remove(n);
320 }
321 }
322 if (!s.isEmpty()) throw new RuntimeException();
323 }
324
325 // rotate back and log the change
326 final Collection<Command> commands = new LinkedList<Command>();
327 OrthogonalizeAction.rememberMovements.clear();
328 for (Node n: allNodes) {
329 EastNorth tmp = new EastNorth(nX.get(n), nY.get(n));
330 tmp = EN.rotate_cc(pivot, tmp, headingAll);
331 final double dx = tmp.east() - n.getEastNorth().east();
332 final double dy = tmp.north() - n.getEastNorth().north();
333 if (headingNodes.contains(n)) { // The heading nodes should not have changed
334 final double EPSILON = 1E-6;
335 if (Math.abs(dx) > Math.abs(EPSILON * tmp.east()) ||
336 Math.abs(dy) > Math.abs(EPSILON * tmp.east())) {
337 throw new AssertionError();
338 }
339 }
340 else {
341 OrthogonalizeAction.rememberMovements.put(n, new EastNorth(dx, dy));
342 commands.add(new MoveCommand(n, dx, dy));
343 }
344 }
345 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), commands));
346 Main.map.repaint();
347 }
348
349
350 /**
351 * Class contains everything we need to know about a singe way.
352 */
353 private static class WayData {
354 final public Way way; // The assigned way
355 final public int nSeg; // Number of Segments of the Way
356 final public int nNode; // Number of Nodes of the Way
357 public Direction[] segDirections; // Direction of the segments
358 // segment i goes from node i to node (i+1)
359 public EastNorth segSum; // (Vector-)sum of all horizontal segments plus the sum of all vertical
360 // segments turned by 90 degrees
361 public double heading; // heading of segSum == approximate heading of the way
362 public WayData(Way pWay) {
363 way = pWay;
364 nNode = way.getNodes().size();
365 nSeg = nNode - 1;
366 }
367 /**
368 * Estimate the direction of the segments, given the first segment points in the
369 * direction <code>pInitialDirection</code>.
370 * Then sum up all horizontal / vertical segments to have a good guess for the
371 * heading of the entire way.
372 */
373 public void calcDirections(Direction pInitialDirection) throws InvalidUserInputException {
374 final EastNorth[] en = new EastNorth[nNode]; // alias: way.getNodes().get(i).getEastNorth() ---> en[i]
375 for (int i=0; i < nNode; i++) {
376 en[i] = new EastNorth(way.getNodes().get(i).getEastNorth().east(), way.getNodes().get(i).getEastNorth().north());
377 }
378 segDirections = new Direction[nSeg];
379 Direction direction = pInitialDirection;
380 segDirections[0] = direction;
381 for (int i=0; i < nSeg - 1; i++) {
382 double h1 = EN.polar(en[i],en[i+1]);
383 double h2 = EN.polar(en[i+1],en[i+2]);
384 try {
385 direction = direction.changeBy(angleToDirectionChange(h2 - h1, TOLERANCE1));
386 } catch (RejectedAngleException ex) {
387 throw new InvalidUserInputException("Please select ways with angles of approximately 90 or 180 degrees.");
388 }
389 segDirections[i+1] = direction;
390 }
391
392 // sum up segments
393 EastNorth h = new EastNorth(0.,0.);
394 double lh = EN.abs(h);
395 EastNorth v = new EastNorth(0.,0.);
396 double lv = EN.abs(v);
397 for (int i = 0; i < nSeg; ++i) {
398 EastNorth segment = EN.diff(en[i+1], en[i]);
399 if (segDirections[i] == Direction.RIGHT) h = EN.sum(h,segment);
400 else if (segDirections[i] == Direction.UP) v = EN.sum(v,segment);
401 else if (segDirections[i] == Direction.LEFT) h = EN.diff(h,segment);
402 else if (segDirections[i] == Direction.DOWN) v = EN.diff(v,segment);
403 else throw new IllegalStateException();
404 /**
405 * When summing up the length of the sum vector should increase.
406 * However, it is possible to construct ways, such that this assertion fails.
407 * So only uncomment this for testing
408 **/
409// if (segDirections[i].ordinal() % 2 == 0) {
410// if (EN.abs(h) < lh) throw new AssertionError();
411// lh = EN.abs(h);
412// } else {
413// if (EN.abs(v) < lv) throw new AssertionError();
414// lv = EN.abs(v);
415// }
416 }
417 // rotate the vertical vector by 90 degrees (clockwise) and add it to the horizontal vector
418 segSum = EN.sum(h, new EastNorth(v.north(), - v.east()));
419// if (EN.abs(segSum) < lh) throw new AssertionError();
420 this.heading = EN.polar(new EastNorth(0.,0.), segSum);
421 }
422 }
423
424 private enum Direction {
425 RIGHT, UP, LEFT, DOWN;
426 public Direction changeBy(int directionChange) {
427 int tmp = (this.ordinal() + directionChange) % 4;
428 if (tmp < 0) tmp += 4; // the % operator can return negative value
429 return Direction.values()[tmp];
430 }
431 }
432
433 /**
434 * Make sure angle (up to 2*Pi) is in interval [ 0, 2*Pi ).
435 */
436 private static double standard_angle_0_to_2PI(double a) {
437 while (a >= 2 * Math.PI) a -= 2 * Math.PI;
438 while (a < 0) a += 2 * Math.PI;
439 return a;
440 }
441
442 /**
443 * Make sure angle (up to 2*Pi) is in interval ( -Pi, Pi ].
444 */
445 private static double standard_angle_mPI_to_PI(double a) {
446 while (a > Math.PI) a -= 2 * Math.PI;
447 while (a <= - Math.PI) a += 2 * Math.PI;
448 return a;
449 }
450
451 /**
452 * Class contains some auxiliary functions
453 */
454 private static class EN {
455 // rotate counter-clock-wise
456 public static EastNorth rotate_cc(EastNorth pivot, EastNorth en, double angle) {
457 double cosPhi = Math.cos(angle);
458 double sinPhi = Math.sin(angle);
459 double x = en.east() - pivot.east();
460 double y = en.north() - pivot.north();
461 double nx = cosPhi * x - sinPhi * y + pivot.east();
462 double ny = sinPhi * x + cosPhi * y + pivot.north();
463 return new EastNorth(nx, ny);
464 }
465 public static EastNorth sum(EastNorth en1, EastNorth en2) {
466 return new EastNorth(en1.east() + en2.east(), en1.north() + en2.north());
467 }
468 public static EastNorth diff(EastNorth en1, EastNorth en2) {
469 return new EastNorth(en1.east() - en2.east(), en1.north() - en2.north());
470 }
471 public static double abs(EastNorth en) {
472 return Math.sqrt(en.east() * en.east() + en.north() * en.north());
473 }
474 public static String toString(EastNorth en) {
475 return "["+u(en.east())+","+u(en.north())+"]";
476 }
477 public static long u(double d) {
478 return Math.round(d * 1000000.);
479 }
480 public static double polar(EastNorth en1, EastNorth en2) {
481 return Math.atan2(en2.north() - en1.north(), en2.east() - en1.east());
482 }
483 }
484
485 /**
486 * Recognize angle to be approximately 0, 90, 180 or 270 degrees.
487 * returns a integral value, corresponding to a counter clockwise turn:
488 */
489 private static int angleToDirectionChange(double a, double deltaMax) throws RejectedAngleException {
490 a = standard_angle_mPI_to_PI(a);
491 double d0 = Math.abs(a);
492 double d90 = Math.abs(a - Math.PI / 2);
493 double d_m90 = Math.abs(a + Math.PI / 2);
494 int dirChange;
495 if (d0 < deltaMax) dirChange = 0;
496 else if (d90 < deltaMax) dirChange = 1;
497 else if (d_m90 < deltaMax) dirChange = -1;
498 else {
499 a = standard_angle_0_to_2PI(a);
500 double d180 = Math.abs(a - Math.PI);
501 if (d180 < deltaMax) dirChange = 2;
502 else {
503 throw new RejectedAngleException();
504 }
505 }
506 return dirChange;
507 }
508
509 /**
510 * Exception: unsuited user input
511 */
512 private static class InvalidUserInputException extends Exception {
513 InvalidUserInputException(String message) {
514 super(message);
515 }
516 InvalidUserInputException() {
517 super();
518 }
519 }
520 /**
521 * Exception: angle cannot be recognized as 0, 90, 180 or 270 degrees
522 */
523 private static class RejectedAngleException extends Exception {
524 RejectedAngleException() {
525 super();
526 }
527 }
528
529 /**
530 * Don't check, if the current selection is suited for orthogonalization.
531 * Instead, show a usage dialog, that explains, why it cannot be done.
532 */
533 @Override
534 protected void updateEnabledState() {
535 setEnabled(getCurrentDataSet() != null);
536 }
537}
Note: See TracBrowser for help on using the repository browser.