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.Collection; 011import java.util.Collections; 012import java.util.HashSet; 013import java.util.LinkedList; 014import java.util.List; 015import java.util.Set; 016 017import javax.swing.JOptionPane; 018 019import org.openstreetmap.josm.Main; 020import org.openstreetmap.josm.command.Command; 021import org.openstreetmap.josm.command.MoveCommand; 022import org.openstreetmap.josm.command.SequenceCommand; 023import org.openstreetmap.josm.data.coor.EastNorth; 024import org.openstreetmap.josm.data.osm.Node; 025import org.openstreetmap.josm.data.osm.OsmPrimitive; 026import org.openstreetmap.josm.data.osm.Way; 027import org.openstreetmap.josm.gui.Notification; 028import org.openstreetmap.josm.tools.Geometry; 029import org.openstreetmap.josm.tools.Shortcut; 030 031/** 032 * Aligns all selected nodes within a circle. (Useful for roundabouts) 033 * 034 * @author Matthew Newton 035 * @author Petr DlouhĂ˝ 036 * @author Teemu Koskinen 037 * @author Alain Delplanque 038 * 039 * @since 146 040 */ 041public final class AlignInCircleAction extends JosmAction { 042 043 /** 044 * Constructs a new {@code AlignInCircleAction}. 045 */ 046 public AlignInCircleAction() { 047 super(tr("Align Nodes in Circle"), "aligncircle", tr("Move the selected nodes into a circle."), 048 Shortcut.registerShortcut("tools:aligncircle", tr("Tool: {0}", tr("Align Nodes in Circle")), 049 KeyEvent.VK_O, Shortcut.DIRECT), true); 050 putValue("help", ht("/Action/AlignInCircle")); 051 } 052 053 private static double distance(EastNorth n, EastNorth m) { 054 double easd, nord; 055 easd = n.east() - m.east(); 056 nord = n.north() - m.north(); 057 return Math.sqrt(easd * easd + nord * nord); 058 } 059 060 public static class PolarCoor { 061 private double radius; 062 private double angle; 063 private EastNorth origin = new EastNorth(0, 0); 064 private double azimuth; 065 066 PolarCoor(double radius, double angle) { 067 this(radius, angle, new EastNorth(0, 0), 0); 068 } 069 070 PolarCoor(double radius, double angle, EastNorth origin, double azimuth) { 071 this.radius = radius; 072 this.angle = angle; 073 this.origin = origin; 074 this.azimuth = azimuth; 075 } 076 077 PolarCoor(EastNorth en) { 078 this(en, new EastNorth(0, 0), 0); 079 } 080 081 PolarCoor(EastNorth en, EastNorth origin, double azimuth) { 082 radius = distance(en, origin); 083 angle = Math.atan2(en.north() - origin.north(), en.east() - origin.east()); 084 this.origin = origin; 085 this.azimuth = azimuth; 086 } 087 088 public EastNorth toEastNorth() { 089 return new EastNorth(radius * Math.cos(angle - azimuth) + origin.east(), radius * Math.sin(angle - azimuth) 090 + origin.north()); 091 } 092 093 /** 094 * Create a MoveCommand to move a node to this PolarCoor. 095 * @param n Node to move 096 * @return new MoveCommand 097 */ 098 public MoveCommand createMoveCommand(Node n) { 099 EastNorth en = toEastNorth(); 100 return new MoveCommand(n, en.east() - n.getEastNorth().east(), en.north() - n.getEastNorth().north()); 101 } 102 } 103 104 105 /** 106 * Perform AlignInCircle action. 107 * 108 * A fixed node is a node for which it is forbidden to change the angle relative to center of the circle. 109 * All other nodes are uniformly distributed. 110 * 111 * Case 1: One unclosed way. 112 * --> allow action, and align selected way nodes 113 * If nodes contained by this way are selected, there are fix. 114 * If nodes outside from the way are selected there are ignored. 115 * 116 * Case 2: One or more ways are selected and can be joined into a polygon 117 * --> allow action, and align selected ways nodes 118 * If 1 node outside of way is selected, it became center 119 * If 1 node outside and 1 node inside are selected there define center and radius 120 * If no outside node and 2 inside nodes are selected those 2 nodes define diameter 121 * In all other cases outside nodes are ignored 122 * In all cases, selected nodes are fix, nodes with more than one referrers are fix 123 * (first referrer is the selected way) 124 * 125 * Case 3: Only nodes are selected 126 * --> Align these nodes, all are fix 127 */ 128 @Override 129 public void actionPerformed(ActionEvent e) { 130 if (!isEnabled()) 131 return; 132 133 Collection<OsmPrimitive> sel = getCurrentDataSet().getSelected(); 134 List<Node> nodes = new LinkedList<>(); 135 // fixNodes: All nodes for which the angle relative to center should not be modified 136 Set<Node> fixNodes = new HashSet<>(); 137 List<Way> ways = new LinkedList<>(); 138 EastNorth center = null; 139 double radius = 0; 140 141 for (OsmPrimitive osm : sel) { 142 if (osm instanceof Node) { 143 nodes.add((Node) osm); 144 } else if (osm instanceof Way) { 145 ways.add((Way) osm); 146 } 147 } 148 149 if (ways.size() == 1 && !ways.get(0).isClosed()) { 150 // Case 1 151 Way w = ways.get(0); 152 fixNodes.add(w.firstNode()); 153 fixNodes.add(w.lastNode()); 154 fixNodes.addAll(nodes); 155 fixNodes.addAll(collectNodesWithExternReferers(ways)); 156 // Temporary closed way used to reorder nodes 157 Way closedWay = new Way(w); 158 closedWay.addNode(w.firstNode()); 159 List<Way> usedWays = new ArrayList<>(1); 160 usedWays.add(closedWay); 161 nodes = collectNodesAnticlockwise(usedWays); 162 } else if (!ways.isEmpty() && checkWaysArePolygon(ways)) { 163 // Case 2 164 List<Node> inside = new ArrayList<>(); 165 List<Node> outside = new ArrayList<>(); 166 167 for (Node n: nodes) { 168 boolean isInside = false; 169 for (Way w: ways) { 170 if (w.getNodes().contains(n)) { 171 isInside = true; 172 break; 173 } 174 } 175 if (isInside) 176 inside.add(n); 177 else 178 outside.add(n); 179 } 180 181 if (outside.size() == 1 && inside.isEmpty()) { 182 center = outside.get(0).getEastNorth(); 183 } else if (outside.size() == 1 && inside.size() == 1) { 184 center = outside.get(0).getEastNorth(); 185 radius = distance(center, inside.get(0).getEastNorth()); 186 } else if (inside.size() == 2 && outside.isEmpty()) { 187 // 2 nodes inside, define diameter 188 EastNorth en0 = inside.get(0).getEastNorth(); 189 EastNorth en1 = inside.get(1).getEastNorth(); 190 center = new EastNorth((en0.east() + en1.east()) / 2, (en0.north() + en1.north()) / 2); 191 radius = distance(en0, en1) / 2; 192 } 193 194 fixNodes.addAll(inside); 195 fixNodes.addAll(collectNodesWithExternReferers(ways)); 196 nodes = collectNodesAnticlockwise(ways); 197 if (nodes.size() < 4) { 198 new Notification( 199 tr("Not enough nodes in selected ways.")) 200 .setIcon(JOptionPane.INFORMATION_MESSAGE) 201 .setDuration(Notification.TIME_SHORT) 202 .show(); 203 return; 204 } 205 } else if (ways.isEmpty() && nodes.size() > 3) { 206 // Case 3 207 fixNodes.addAll(nodes); 208 // No need to reorder nodes since all are fix 209 } else { 210 // Invalid action 211 new Notification( 212 tr("Please select at least four nodes.")) 213 .setIcon(JOptionPane.INFORMATION_MESSAGE) 214 .setDuration(Notification.TIME_SHORT) 215 .show(); 216 return; 217 } 218 219 if (center == null) { 220 // Compute the center of nodes 221 center = Geometry.getCenter(nodes); 222 if (center == null) { 223 new Notification(tr("Cannot determine center of selected nodes.")) 224 .setIcon(JOptionPane.INFORMATION_MESSAGE) 225 .setDuration(Notification.TIME_SHORT) 226 .show(); 227 return; 228 } 229 } 230 231 // Now calculate the average distance to each node from the 232 // center. This method is ok as long as distances are short 233 // relative to the distance from the N or S poles. 234 if (radius == 0) { 235 for (Node n : nodes) { 236 radius += distance(center, n.getEastNorth()); 237 } 238 radius = radius / nodes.size(); 239 } 240 241 if (!actionAllowed(nodes)) return; 242 243 Collection<Command> cmds = new LinkedList<>(); 244 245 // Move each node to that distance from the center. 246 // Nodes that are not "fix" will be adjust making regular arcs. 247 int nodeCount = nodes.size(); 248 // Search first fixed node 249 int startPosition; 250 for (startPosition = 0; startPosition < nodeCount; startPosition++) { 251 if (fixNodes.contains(nodes.get(startPosition % nodeCount))) 252 break; 253 } 254 int i = startPosition; // Start position for current arc 255 int j; // End position for current arc 256 while (i < startPosition + nodeCount) { 257 for (j = i + 1; j < startPosition + nodeCount; j++) { 258 if (fixNodes.contains(nodes.get(j % nodeCount))) 259 break; 260 } 261 Node first = nodes.get(i % nodeCount); 262 PolarCoor pcFirst = new PolarCoor(first.getEastNorth(), center, 0); 263 pcFirst.radius = radius; 264 cmds.add(pcFirst.createMoveCommand(first)); 265 if (j > i + 1) { 266 double delta; 267 if (j == i + nodeCount) { 268 delta = 2 * Math.PI / nodeCount; 269 } else { 270 PolarCoor pcLast = new PolarCoor(nodes.get(j % nodeCount).getEastNorth(), center, 0); 271 delta = pcLast.angle - pcFirst.angle; 272 if (delta < 0) // Assume each PolarCoor.angle is in range ]-pi; pi] 273 delta += 2*Math.PI; 274 delta /= j - i; 275 } 276 for (int k = i+1; k < j; k++) { 277 PolarCoor p = new PolarCoor(radius, pcFirst.angle + (k-i)*delta, center, 0); 278 cmds.add(p.createMoveCommand(nodes.get(k % nodeCount))); 279 } 280 } 281 i = j; // Update start point for next iteration 282 } 283 284 Main.main.undoRedo.add(new SequenceCommand(tr("Align Nodes in Circle"), cmds)); 285 Main.map.repaint(); 286 } 287 288 /** 289 * Collect all nodes with more than one referrer. 290 * @param ways Ways from witch nodes are selected 291 * @return List of nodes with more than one referrer 292 */ 293 private static List<Node> collectNodesWithExternReferers(List<Way> ways) { 294 List<Node> withReferrers = new ArrayList<>(); 295 for (Way w: ways) { 296 for (Node n: w.getNodes()) { 297 if (n.getReferrers().size() > 1) { 298 withReferrers.add(n); 299 } 300 } 301 } 302 return withReferrers; 303 } 304 305 /** 306 * Assuming all ways can be joined into polygon, create an ordered list of node. 307 * @param ways List of ways to be joined 308 * @return Nodes anticlockwise ordered 309 */ 310 private static List<Node> collectNodesAnticlockwise(List<Way> ways) { 311 List<Node> nodes = new ArrayList<>(); 312 Node firstNode = ways.get(0).firstNode(); 313 Node lastNode = null; 314 Way lastWay = null; 315 while (firstNode != lastNode) { 316 if (lastNode == null) lastNode = firstNode; 317 for (Way way: ways) { 318 if (way == lastWay) continue; 319 if (way.firstNode() == lastNode) { 320 List<Node> wayNodes = way.getNodes(); 321 for (int i = 0; i < wayNodes.size() - 1; i++) { 322 nodes.add(wayNodes.get(i)); 323 } 324 lastNode = way.lastNode(); 325 lastWay = way; 326 break; 327 } 328 if (way.lastNode() == lastNode) { 329 List<Node> wayNodes = way.getNodes(); 330 for (int i = wayNodes.size() - 1; i > 0; i--) { 331 nodes.add(wayNodes.get(i)); 332 } 333 lastNode = way.firstNode(); 334 lastWay = way; 335 break; 336 } 337 } 338 } 339 // Check if nodes are in anticlockwise order 340 int nc = nodes.size(); 341 double area = 0; 342 for (int i = 0; i < nc; i++) { 343 EastNorth p1 = nodes.get(i).getEastNorth(); 344 EastNorth p2 = nodes.get((i+1) % nc).getEastNorth(); 345 area += p1.east()*p2.north() - p2.east()*p1.north(); 346 } 347 if (area < 0) 348 Collections.reverse(nodes); 349 return nodes; 350 } 351 352 /** 353 * Check if one or more nodes are outside of download area 354 * @param nodes Nodes to check 355 * @return true if action can be done 356 */ 357 private static boolean actionAllowed(Collection<Node> nodes) { 358 boolean outside = false; 359 for (Node n: nodes) { 360 if (n.isOutsideDownloadArea()) { 361 outside = true; 362 break; 363 } 364 } 365 if (outside) 366 new Notification( 367 tr("One or more nodes involved in this action is outside of the downloaded area.")) 368 .setIcon(JOptionPane.WARNING_MESSAGE) 369 .setDuration(Notification.TIME_SHORT) 370 .show(); 371 return true; 372 } 373 374 @Override 375 protected void updateEnabledState() { 376 setEnabled(getCurrentDataSet() != null && !getCurrentDataSet().getSelected().isEmpty()); 377 } 378 379 @Override 380 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 381 setEnabled(selection != null && !selection.isEmpty()); 382 } 383 384 /** 385 * Determines if ways can be joined into a polygon. 386 * @param ways The ways collection to check 387 * @return true if all ways can be joined into a polygon 388 */ 389 protected static boolean checkWaysArePolygon(Collection<Way> ways) { 390 // For each way, nodes strictly between first and last should't be reference by an other way 391 for (Way way: ways) { 392 for (Node node: way.getNodes()) { 393 if (way.isFirstLastNode(node)) continue; 394 for (Way wayOther: ways) { 395 if (way == wayOther) continue; 396 if (node.getReferrers().contains(wayOther)) return false; 397 } 398 } 399 } 400 // Test if ways can be joined 401 Way currentWay = null; 402 Node startNode = null, endNode = null; 403 int used = 0; 404 while (true) { 405 Way nextWay = null; 406 for (Way w: ways) { 407 if (w.isClosed()) return ways.size() == 1; 408 if (w == currentWay) continue; 409 if (currentWay == null) { 410 nextWay = w; 411 startNode = w.firstNode(); 412 endNode = w.lastNode(); 413 break; 414 } 415 if (w.firstNode() == endNode) { 416 nextWay = w; 417 endNode = w.lastNode(); 418 break; 419 } 420 if (w.lastNode() == endNode) { 421 nextWay = w; 422 endNode = w.firstNode(); 423 break; 424 } 425 } 426 if (nextWay == null) return false; 427 used += 1; 428 currentWay = nextWay; 429 if (endNode == startNode) return used == ways.size(); 430 } 431 } 432}