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.Arrays; 011import java.util.Collection; 012import java.util.Collections; 013import java.util.HashMap; 014import java.util.HashSet; 015import java.util.Iterator; 016import java.util.LinkedList; 017import java.util.List; 018import java.util.Map; 019import java.util.Set; 020 021import javax.swing.JOptionPane; 022 023import org.openstreetmap.josm.Main; 024import org.openstreetmap.josm.command.Command; 025import org.openstreetmap.josm.command.MoveCommand; 026import org.openstreetmap.josm.command.SequenceCommand; 027import org.openstreetmap.josm.data.coor.EastNorth; 028import org.openstreetmap.josm.data.osm.DataSet; 029import org.openstreetmap.josm.data.osm.Node; 030import org.openstreetmap.josm.data.osm.OsmPrimitive; 031import org.openstreetmap.josm.data.osm.Way; 032import org.openstreetmap.josm.gui.ConditionalOptionPaneUtil; 033import org.openstreetmap.josm.gui.Notification; 034import org.openstreetmap.josm.tools.Shortcut; 035 036/** 037 * Tools / Orthogonalize 038 * 039 * Align edges of a way so all angles are angles of 90 or 180 degrees. 040 * See USAGE String below. 041 */ 042public final class OrthogonalizeAction extends JosmAction { 043 private static final String USAGE = tr( 044 "<h3>When one or more ways are selected, the shape is adjusted such, that all angles are 90 or 180 degrees.</h3>"+ 045 "You can add two nodes to the selection. Then, the direction is fixed by these two reference nodes. "+ 046 "(Afterwards, you can undo the movement for certain nodes:<br>"+ 047 "Select them and press the shortcut for Orthogonalize / Undo. The default is Shift-Q.)"); 048 049 /** 050 * Constructs a new {@code OrthogonalizeAction}. 051 */ 052 public OrthogonalizeAction() { 053 super(tr("Orthogonalize Shape"), 054 "ortho", 055 tr("Move nodes so all angles are 90 or 180 degrees"), 056 Shortcut.registerShortcut("tools:orthogonalize", tr("Tool: {0}", tr("Orthogonalize Shape")), 057 KeyEvent.VK_Q, 058 Shortcut.DIRECT), true); 059 putValue("help", ht("/Action/OrthogonalizeShape")); 060 } 061 062 /** 063 * excepted deviation from an angle of 0, 90, 180, 360 degrees 064 * maximum value: 45 degrees 065 * 066 * Current policy is to except just everything, no matter how strange the result would be. 067 */ 068 private static final double TOLERANCE1 = Math.toRadians(45.); // within a way 069 private static final double TOLERANCE2 = Math.toRadians(45.); // ways relative to each other 070 071 /** 072 * Remember movements, so the user can later undo it for certain nodes 073 */ 074 private static final Map<Node, EastNorth> rememberMovements = new HashMap<>(); 075 076 /** 077 * Undo the previous orthogonalization for certain nodes. 078 * 079 * This is useful, if the way shares nodes that you don't like to change, e.g. imports or 080 * work of another user. 081 * 082 * This action can be triggered by shortcut only. 083 */ 084 public static class Undo extends JosmAction { 085 /** 086 * Constructor 087 */ 088 public Undo() { 089 super(tr("Orthogonalize Shape / Undo"), "ortho", 090 tr("Undo orthogonalization for certain nodes"), 091 Shortcut.registerShortcut("tools:orthogonalizeUndo", tr("Tool: {0}", tr("Orthogonalize Shape / Undo")), 092 KeyEvent.VK_Q, 093 Shortcut.SHIFT), 094 true, "action/orthogonalize/undo", true); 095 } 096 097 @Override 098 public void actionPerformed(ActionEvent e) { 099 if (!isEnabled()) 100 return; 101 final Collection<Command> commands = new LinkedList<>(); 102 final Collection<OsmPrimitive> sel = getLayerManager().getEditDataSet().getSelected(); 103 try { 104 for (OsmPrimitive p : sel) { 105 if (!(p instanceof Node)) throw new InvalidUserInputException("selected object is not a node"); 106 Node n = (Node) p; 107 if (rememberMovements.containsKey(n)) { 108 EastNorth tmp = rememberMovements.get(n); 109 commands.add(new MoveCommand(n, -tmp.east(), -tmp.north())); 110 rememberMovements.remove(n); 111 } 112 } 113 if (!commands.isEmpty()) { 114 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize / Undo"), commands)); 115 } else { 116 throw new InvalidUserInputException("Commands are empty"); 117 } 118 } catch (InvalidUserInputException ex) { 119 Main.debug(ex); 120 new Notification( 121 tr("Orthogonalize Shape / Undo<br>"+ 122 "Please select nodes that were moved by the previous Orthogonalize Shape action!")) 123 .setIcon(JOptionPane.INFORMATION_MESSAGE) 124 .show(); 125 } 126 } 127 } 128 129 @Override 130 public void actionPerformed(ActionEvent e) { 131 if (!isEnabled()) 132 return; 133 if ("EPSG:4326".equals(Main.getProjection().toString())) { 134 String msg = tr("<html>You are using the EPSG:4326 projection which might lead<br>" + 135 "to undesirable results when doing rectangular alignments.<br>" + 136 "Change your projection to get rid of this warning.<br>" + 137 "Do you want to continue?</html>"); 138 if (!ConditionalOptionPaneUtil.showConfirmationDialog( 139 "align_rectangular_4326", 140 Main.parent, 141 msg, 142 tr("Warning"), 143 JOptionPane.YES_NO_OPTION, 144 JOptionPane.QUESTION_MESSAGE, 145 JOptionPane.YES_OPTION)) 146 return; 147 } 148 149 final Collection<OsmPrimitive> sel = getLayerManager().getEditDataSet().getSelected(); 150 151 try { 152 final SequenceCommand command = orthogonalize(sel); 153 Main.main.undoRedo.add(new SequenceCommand(tr("Orthogonalize"), command)); 154 } catch (InvalidUserInputException ex) { 155 Main.debug(ex); 156 String msg; 157 if ("usage".equals(ex.getMessage())) { 158 msg = "<h2>" + tr("Usage") + "</h2>" + USAGE; 159 } else { 160 msg = ex.getMessage() + "<br><hr><h2>" + tr("Usage") + "</h2>" + USAGE; 161 } 162 new Notification(msg) 163 .setIcon(JOptionPane.INFORMATION_MESSAGE) 164 .setDuration(Notification.TIME_DEFAULT) 165 .show(); 166 } 167 } 168 169 /** 170 * Rectifies the selection 171 * @param selection the selection which should be rectified 172 * @return a rectifying command 173 * @throws InvalidUserInputException if the selection is invalid 174 */ 175 static SequenceCommand orthogonalize(Iterable<OsmPrimitive> selection) throws InvalidUserInputException { 176 final List<Node> nodeList = new ArrayList<>(); 177 final List<WayData> wayDataList = new ArrayList<>(); 178 // collect nodes and ways from the selection 179 for (OsmPrimitive p : selection) { 180 if (p instanceof Node) { 181 nodeList.add((Node) p); 182 } else if (p instanceof Way) { 183 wayDataList.add(new WayData(((Way) p).getNodes())); 184 } else { 185 throw new InvalidUserInputException(tr("Selection must consist only of ways and nodes.")); 186 } 187 } 188 if (wayDataList.isEmpty() && nodeList.size() > 2) { 189 final WayData data = new WayData(nodeList); 190 final Collection<Command> commands = orthogonalize(Collections.singletonList(data), Collections.<Node>emptyList()); 191 return new SequenceCommand(tr("Orthogonalize"), commands); 192 } else if (wayDataList.isEmpty()) { 193 throw new InvalidUserInputException("usage"); 194 } else { 195 if (nodeList.size() == 2 || nodeList.isEmpty()) { 196 OrthogonalizeAction.rememberMovements.clear(); 197 final Collection<Command> commands = new LinkedList<>(); 198 199 if (nodeList.size() == 2) { // fixed direction 200 commands.addAll(orthogonalize(wayDataList, nodeList)); 201 } else if (nodeList.isEmpty()) { 202 List<List<WayData>> groups = buildGroups(wayDataList); 203 for (List<WayData> g: groups) { 204 commands.addAll(orthogonalize(g, nodeList)); 205 } 206 } else { 207 throw new IllegalStateException(); 208 } 209 210 return new SequenceCommand(tr("Orthogonalize"), commands); 211 212 } else { 213 throw new InvalidUserInputException("usage"); 214 } 215 } 216 } 217 218 /** 219 * Collect groups of ways with common nodes in order to orthogonalize each group separately. 220 * @param wayDataList list of ways 221 * @return groups of ways with common nodes 222 */ 223 private static List<List<WayData>> buildGroups(List<WayData> wayDataList) { 224 List<List<WayData>> groups = new ArrayList<>(); 225 Set<WayData> remaining = new HashSet<>(wayDataList); 226 while (!remaining.isEmpty()) { 227 List<WayData> group = new ArrayList<>(); 228 groups.add(group); 229 Iterator<WayData> it = remaining.iterator(); 230 WayData next = it.next(); 231 it.remove(); 232 extendGroupRec(group, next, new ArrayList<>(remaining)); 233 remaining.removeAll(group); 234 } 235 return groups; 236 } 237 238 private static void extendGroupRec(List<WayData> group, WayData newGroupMember, List<WayData> remaining) { 239 group.add(newGroupMember); 240 for (int i = 0; i < remaining.size(); ++i) { 241 WayData candidate = remaining.get(i); 242 if (candidate == null) continue; 243 if (!Collections.disjoint(candidate.wayNodes, newGroupMember.wayNodes)) { 244 remaining.set(i, null); 245 extendGroupRec(group, candidate, remaining); 246 } 247 } 248 } 249 250 /** 251 * 252 * Outline: 253 * 1. Find direction of all segments 254 * - direction = 0..3 (right,up,left,down) 255 * - right is not really right, you may have to turn your screen 256 * 2. Find average heading of all segments 257 * - heading = angle of a vector in polar coordinates 258 * - sum up horizontal segments (those with direction 0 or 2) 259 * - sum up vertical segments 260 * - turn the vertical sum by 90 degrees and add it to the horizontal sum 261 * - get the average heading from this total sum 262 * 3. Rotate all nodes by the average heading so that right is really right 263 * and all segments are approximately NS or EW. 264 * 4. If nodes are connected by a horizontal segment: Replace their y-Coordinate by 265 * the mean value of their y-Coordinates. 266 * - The same for vertical segments. 267 * 5. Rotate back. 268 * @param wayDataList list of ways 269 * @param headingNodes list of heading nodes 270 * @return list of commands to perform 271 * @throws InvalidUserInputException if selected ways have an angle different from 90 or 180 degrees 272 **/ 273 private static Collection<Command> orthogonalize(List<WayData> wayDataList, List<Node> headingNodes) throws InvalidUserInputException { 274 // find average heading 275 double headingAll; 276 try { 277 if (headingNodes.isEmpty()) { 278 // find directions of the segments and make them consistent between different ways 279 wayDataList.get(0).calcDirections(Direction.RIGHT); 280 double refHeading = wayDataList.get(0).heading; 281 EastNorth totSum = new EastNorth(0., 0.); 282 for (WayData w : wayDataList) { 283 w.calcDirections(Direction.RIGHT); 284 int directionOffset = angleToDirectionChange(w.heading - refHeading, TOLERANCE2); 285 w.calcDirections(Direction.RIGHT.changeBy(directionOffset)); 286 if (angleToDirectionChange(refHeading - w.heading, TOLERANCE2) != 0) 287 throw new RuntimeException(); 288 totSum = EN.sum(totSum, w.segSum); 289 } 290 headingAll = EN.polar(new EastNorth(0., 0.), totSum); 291 } else { 292 headingAll = EN.polar(headingNodes.get(0).getEastNorth(), headingNodes.get(1).getEastNorth()); 293 for (WayData w : wayDataList) { 294 w.calcDirections(Direction.RIGHT); 295 int directionOffset = angleToDirectionChange(w.heading - headingAll, TOLERANCE2); 296 w.calcDirections(Direction.RIGHT.changeBy(directionOffset)); 297 } 298 } 299 } catch (RejectedAngleException ex) { 300 throw new InvalidUserInputException( 301 tr("<html>Please make sure all selected ways head in a similar direction<br>"+ 302 "or orthogonalize them one by one.</html>"), ex); 303 } 304 305 // put the nodes of all ways in a set 306 final Set<Node> allNodes = new HashSet<>(); 307 for (WayData w : wayDataList) { 308 allNodes.addAll(w.wayNodes); 309 } 310 311 // the new x and y value for each node 312 final Map<Node, Double> nX = new HashMap<>(); 313 final Map<Node, Double> nY = new HashMap<>(); 314 315 // calculate the centroid of all nodes 316 // it is used as rotation center 317 EastNorth pivot = new EastNorth(0., 0.); 318 for (Node n : allNodes) { 319 pivot = EN.sum(pivot, n.getEastNorth()); 320 } 321 pivot = new EastNorth(pivot.east() / allNodes.size(), pivot.north() / allNodes.size()); 322 323 // rotate 324 for (Node n: allNodes) { 325 EastNorth tmp = EN.rotateCC(pivot, n.getEastNorth(), -headingAll); 326 nX.put(n, tmp.east()); 327 nY.put(n, tmp.north()); 328 } 329 330 // orthogonalize 331 final Direction[] horizontal = {Direction.RIGHT, Direction.LEFT}; 332 final Direction[] vertical = {Direction.UP, Direction.DOWN}; 333 final Direction[][] orientations = {horizontal, vertical}; 334 for (Direction[] orientation : orientations) { 335 final Set<Node> s = new HashSet<>(allNodes); 336 int size = s.size(); 337 for (int dummy = 0; dummy < size; ++dummy) { 338 if (s.isEmpty()) { 339 break; 340 } 341 final Node dummyN = s.iterator().next(); // pick arbitrary element of s 342 343 final Set<Node> cs = new HashSet<>(); // will contain each node that can be reached from dummyN 344 cs.add(dummyN); // walking only on horizontal / vertical segments 345 346 boolean somethingHappened = true; 347 while (somethingHappened) { 348 somethingHappened = false; 349 for (WayData w : wayDataList) { 350 for (int i = 0; i < w.nSeg; ++i) { 351 Node n1 = w.wayNodes.get(i); 352 Node n2 = w.wayNodes.get(i+1); 353 if (Arrays.asList(orientation).contains(w.segDirections[i])) { 354 if (cs.contains(n1) && !cs.contains(n2)) { 355 cs.add(n2); 356 somethingHappened = true; 357 } 358 if (cs.contains(n2) && !cs.contains(n1)) { 359 cs.add(n1); 360 somethingHappened = true; 361 } 362 } 363 } 364 } 365 } 366 367 final Map<Node, Double> nC = (orientation == horizontal) ? nY : nX; 368 369 double average = 0; 370 for (Node n : cs) { 371 s.remove(n); 372 average += nC.get(n).doubleValue(); 373 } 374 average = average / cs.size(); 375 376 // if one of the nodes is a heading node, forget about the average and use its value 377 for (Node fn : headingNodes) { 378 if (cs.contains(fn)) { 379 average = nC.get(fn); 380 } 381 } 382 383 // At this point, the two heading nodes (if any) are horizontally aligned, i.e. they 384 // have the same y coordinate. So in general we shouldn't find them in a vertical string 385 // of segments. This can still happen in some pathological cases (see #7889). To avoid 386 // both heading nodes collapsing to one point, we simply skip this segment string and 387 // don't touch the node coordinates. 388 if (orientation == vertical && headingNodes.size() == 2 && cs.containsAll(headingNodes)) { 389 continue; 390 } 391 392 for (Node n : cs) { 393 nC.put(n, average); 394 } 395 } 396 if (!s.isEmpty()) throw new RuntimeException(); 397 } 398 399 // rotate back and log the change 400 final Collection<Command> commands = new LinkedList<>(); 401 for (Node n: allNodes) { 402 EastNorth tmp = new EastNorth(nX.get(n), nY.get(n)); 403 tmp = EN.rotateCC(pivot, tmp, headingAll); 404 final double dx = tmp.east() - n.getEastNorth().east(); 405 final double dy = tmp.north() - n.getEastNorth().north(); 406 if (headingNodes.contains(n)) { // The heading nodes should not have changed 407 final double epsilon = 1E-6; 408 if (Math.abs(dx) > Math.abs(epsilon * tmp.east()) || 409 Math.abs(dy) > Math.abs(epsilon * tmp.east())) 410 throw new AssertionError(); 411 } else { 412 OrthogonalizeAction.rememberMovements.put(n, new EastNorth(dx, dy)); 413 commands.add(new MoveCommand(n, dx, dy)); 414 } 415 } 416 return commands; 417 } 418 419 /** 420 * Class contains everything we need to know about a single way. 421 */ 422 private static class WayData { 423 public final List<Node> wayNodes; // The assigned way 424 public final int nSeg; // Number of Segments of the Way 425 public final int nNode; // Number of Nodes of the Way 426 public final Direction[] segDirections; // Direction of the segments 427 // segment i goes from node i to node (i+1) 428 public EastNorth segSum; // (Vector-)sum of all horizontal segments plus the sum of all vertical 429 // segments turned by 90 degrees 430 public double heading; // heading of segSum == approximate heading of the way 431 432 WayData(List<Node> wayNodes) { 433 this.wayNodes = wayNodes; 434 this.nNode = wayNodes.size(); 435 this.nSeg = nNode - 1; 436 this.segDirections = new Direction[nSeg]; 437 } 438 439 /** 440 * Estimate the direction of the segments, given the first segment points in the 441 * direction <code>pInitialDirection</code>. 442 * Then sum up all horizontal / vertical segments to have a good guess for the 443 * heading of the entire way. 444 * @param pInitialDirection initial direction 445 * @throws InvalidUserInputException if selected ways have an angle different from 90 or 180 degrees 446 */ 447 public void calcDirections(Direction pInitialDirection) throws InvalidUserInputException { 448 final EastNorth[] en = new EastNorth[nNode]; // alias: wayNodes.get(i).getEastNorth() ---> en[i] 449 for (int i = 0; i < nNode; i++) { 450 en[i] = wayNodes.get(i).getEastNorth(); 451 } 452 Direction direction = pInitialDirection; 453 segDirections[0] = direction; 454 for (int i = 0; i < nSeg - 1; i++) { 455 double h1 = EN.polar(en[i], en[i+1]); 456 double h2 = EN.polar(en[i+1], en[i+2]); 457 try { 458 direction = direction.changeBy(angleToDirectionChange(h2 - h1, TOLERANCE1)); 459 } catch (RejectedAngleException ex) { 460 throw new InvalidUserInputException(tr("Please select ways with angles of approximately 90 or 180 degrees."), ex); 461 } 462 segDirections[i+1] = direction; 463 } 464 465 // sum up segments 466 EastNorth h = new EastNorth(0., 0.); 467 EastNorth v = new EastNorth(0., 0.); 468 for (int i = 0; i < nSeg; ++i) { 469 EastNorth segment = EN.diff(en[i+1], en[i]); 470 if (segDirections[i] == Direction.RIGHT) { 471 h = EN.sum(h, segment); 472 } else if (segDirections[i] == Direction.UP) { 473 v = EN.sum(v, segment); 474 } else if (segDirections[i] == Direction.LEFT) { 475 h = EN.diff(h, segment); 476 } else if (segDirections[i] == Direction.DOWN) { 477 v = EN.diff(v, segment); 478 } else throw new IllegalStateException(); 479 } 480 // rotate the vertical vector by 90 degrees (clockwise) and add it to the horizontal vector 481 segSum = EN.sum(h, new EastNorth(v.north(), -v.east())); 482 this.heading = EN.polar(new EastNorth(0., 0.), segSum); 483 } 484 } 485 486 private enum Direction { 487 RIGHT, UP, LEFT, DOWN; 488 public Direction changeBy(int directionChange) { 489 int tmp = (this.ordinal() + directionChange) % 4; 490 if (tmp < 0) { 491 tmp += 4; // the % operator can return negative value 492 } 493 return Direction.values()[tmp]; 494 } 495 } 496 497 /** 498 * Make sure angle (up to 2*Pi) is in interval [ 0, 2*Pi ). 499 * @param a angle 500 * @return correct angle 501 */ 502 private static double standard_angle_0_to_2PI(double a) { 503 while (a >= 2 * Math.PI) { 504 a -= 2 * Math.PI; 505 } 506 while (a < 0) { 507 a += 2 * Math.PI; 508 } 509 return a; 510 } 511 512 /** 513 * Make sure angle (up to 2*Pi) is in interval ( -Pi, Pi ]. 514 * @param a angle 515 * @return correct angle 516 */ 517 private static double standard_angle_mPI_to_PI(double a) { 518 while (a > Math.PI) { 519 a -= 2 * Math.PI; 520 } 521 while (a <= -Math.PI) { 522 a += 2 * Math.PI; 523 } 524 return a; 525 } 526 527 /** 528 * Class contains some auxiliary functions 529 */ 530 private static final class EN { 531 private EN() { 532 // Hide implicit public constructor for utility class 533 } 534 535 /** 536 * Rotate counter-clock-wise. 537 * @param pivot pivot 538 * @param en original east/north 539 * @param angle angle, in radians 540 * @return new east/north 541 */ 542 public static EastNorth rotateCC(EastNorth pivot, EastNorth en, double angle) { 543 double cosPhi = Math.cos(angle); 544 double sinPhi = Math.sin(angle); 545 double x = en.east() - pivot.east(); 546 double y = en.north() - pivot.north(); 547 double nx = cosPhi * x - sinPhi * y + pivot.east(); 548 double ny = sinPhi * x + cosPhi * y + pivot.north(); 549 return new EastNorth(nx, ny); 550 } 551 552 public static EastNorth sum(EastNorth en1, EastNorth en2) { 553 return new EastNorth(en1.east() + en2.east(), en1.north() + en2.north()); 554 } 555 556 public static EastNorth diff(EastNorth en1, EastNorth en2) { 557 return new EastNorth(en1.east() - en2.east(), en1.north() - en2.north()); 558 } 559 560 public static double polar(EastNorth en1, EastNorth en2) { 561 return Math.atan2(en2.north() - en1.north(), en2.east() - en1.east()); 562 } 563 } 564 565 /** 566 * Recognize angle to be approximately 0, 90, 180 or 270 degrees. 567 * returns an integral value, corresponding to a counter clockwise turn. 568 * @param a angle, in radians 569 * @param deltaMax maximum tolerance, in radians 570 * @return an integral value, corresponding to a counter clockwise turn 571 * @throws RejectedAngleException in case of invalid angle 572 */ 573 private static int angleToDirectionChange(double a, double deltaMax) throws RejectedAngleException { 574 a = standard_angle_mPI_to_PI(a); 575 double d0 = Math.abs(a); 576 double d90 = Math.abs(a - Math.PI / 2); 577 double dm90 = Math.abs(a + Math.PI / 2); 578 int dirChange; 579 if (d0 < deltaMax) { 580 dirChange = 0; 581 } else if (d90 < deltaMax) { 582 dirChange = 1; 583 } else if (dm90 < deltaMax) { 584 dirChange = -1; 585 } else { 586 a = standard_angle_0_to_2PI(a); 587 double d180 = Math.abs(a - Math.PI); 588 if (d180 < deltaMax) { 589 dirChange = 2; 590 } else 591 throw new RejectedAngleException(); 592 } 593 return dirChange; 594 } 595 596 /** 597 * Exception: unsuited user input 598 */ 599 protected static class InvalidUserInputException extends Exception { 600 InvalidUserInputException(String message) { 601 super(message); 602 } 603 604 InvalidUserInputException(String message, Throwable cause) { 605 super(message, cause); 606 } 607 } 608 609 /** 610 * Exception: angle cannot be recognized as 0, 90, 180 or 270 degrees 611 */ 612 protected static class RejectedAngleException extends Exception { 613 RejectedAngleException() { 614 super(); 615 } 616 } 617 618 @Override 619 protected void updateEnabledState() { 620 DataSet ds = getLayerManager().getEditDataSet(); 621 setEnabled(ds != null && !ds.selectionEmpty()); 622 } 623 624 @Override 625 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 626 setEnabled(selection != null && !selection.isEmpty()); 627 } 628}