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