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