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; 016import java.util.SortedMap; 017import java.util.TreeMap; 018import java.util.stream.Collectors; 019 020import javax.swing.JOptionPane; 021 022import org.openstreetmap.josm.command.Command; 023import org.openstreetmap.josm.command.MoveCommand; 024import org.openstreetmap.josm.command.SequenceCommand; 025import org.openstreetmap.josm.data.UndoRedoHandler; 026import org.openstreetmap.josm.data.coor.EastNorth; 027import org.openstreetmap.josm.data.coor.PolarCoor; 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.data.osm.visitor.paint.relations.Multipolygon; 033import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.JoinedWay; 034import org.openstreetmap.josm.data.validation.tests.CrossingWays; 035import org.openstreetmap.josm.data.validation.tests.SelfIntersectingWay; 036import org.openstreetmap.josm.gui.Notification; 037import org.openstreetmap.josm.tools.Geometry; 038import org.openstreetmap.josm.tools.Logging; 039import org.openstreetmap.josm.tools.Shortcut; 040 041/** 042 * Aligns all selected nodes within a circle. (Useful for roundabouts) 043 * 044 * @author Matthew Newton 045 * @author Petr DlouhĂ˝ 046 * @author Teemu Koskinen 047 * @author Alain Delplanque 048 * @author Gerd Petermann 049 * 050 * @since 146 051 */ 052public final class AlignInCircleAction extends JosmAction { 053 054 /** 055 * Constructs a new {@code AlignInCircleAction}. 056 */ 057 public AlignInCircleAction() { 058 super(tr("Align Nodes in Circle"), "aligncircle", tr("Move the selected nodes into a circle."), 059 Shortcut.registerShortcut("tools:aligncircle", tr("Tools: {0}", tr("Align Nodes in Circle")), 060 KeyEvent.VK_O, Shortcut.DIRECT), true); 061 setHelpId(ht("/Action/AlignInCircle")); 062 } 063 064 /** 065 * InvalidSelection exception has to be raised when action can't be performed 066 */ 067 public static class InvalidSelection extends Exception { 068 069 /** 070 * Create an InvalidSelection exception with default message 071 */ 072 InvalidSelection() { 073 super(tr("Selection could not be used to align in circle.")); 074 } 075 076 /** 077 * Create an InvalidSelection exception with specific message 078 * @param msg Message that will be displayed to the user 079 */ 080 InvalidSelection(String msg) { 081 super(msg); 082 } 083 } 084 085 /** 086 * Add a {@link MoveCommand} to move a node to a PolarCoor if there is a significant move. 087 * @param n Node to move 088 * @param coor polar coordinate where to move the node 089 * @param cmds list of commands 090 * @since 17386 091 */ 092 public static void addMoveCommandIfNeeded(Node n, PolarCoor coor, List<Command> cmds) { 093 EastNorth en = coor.toEastNorth(); 094 double deltaEast = en.east() - n.getEastNorth().east(); 095 double deltaNorth = en.north() - n.getEastNorth().north(); 096 097 if (Math.abs(deltaEast) > 5e-6 || Math.abs(deltaNorth) > 5e-6) { 098 cmds.add(new MoveCommand(n, deltaEast, deltaNorth)); 099 } 100 } 101 102 /** 103 * Perform AlignInCircle action. 104 * 105 */ 106 @Override 107 public void actionPerformed(ActionEvent e) { 108 if (!isEnabled()) 109 return; 110 111 try { 112 Command cmd = buildCommand(getLayerManager().getEditDataSet()); 113 if (cmd != null) 114 UndoRedoHandler.getInstance().add(cmd); 115 else { 116 new Notification(tr("Nothing changed")) 117 .setIcon(JOptionPane.INFORMATION_MESSAGE) 118 .setDuration(Notification.TIME_SHORT) 119 .show(); 120 121 } 122 } catch (InvalidSelection except) { 123 Logging.debug(except); 124 new Notification(except.getMessage()) 125 .setIcon(JOptionPane.INFORMATION_MESSAGE) 126 .setDuration(Notification.TIME_SHORT) 127 .show(); 128 } 129 } 130 131 /** 132 * Builds "align in circle" command depending on the selected objects. 133 * A fixed node is a node for which it is forbidden to change the angle relative to center of the circle. 134 * All other nodes are uniformly distributed. 135 * <p> 136 * Case 1: One unclosed way. 137 * --> allow action, and align selected way nodes 138 * If nodes contained by this way are selected, there are fix. 139 * If nodes outside from the way are selected there are ignored. 140 * <p> 141 * Case 2: One or more ways are selected and can be joined into a polygon 142 * --> allow action, and align selected ways nodes 143 * If 1 node outside of way is selected, it became center 144 * If 1 node outside and 1 node inside are selected there define center and radius 145 * If no outside node and 2 inside nodes are selected those 2 nodes define diameter 146 * In all other cases outside nodes are ignored 147 * In all cases, selected nodes are fix, nodes with more than one referrers are fix 148 * (first referrer is the selected way) 149 * <p> 150 * Case 3: Only nodes are selected 151 * --> Align these nodes, all are fix 152 * @param ds data set in which the command operates 153 * @return the resulting command to execute to perform action, or null if nothing was changed 154 * @throws InvalidSelection if selection cannot be used 155 * @since 17386 156 * 157 */ 158 public static Command buildCommand(DataSet ds) throws InvalidSelection { 159 Collection<OsmPrimitive> sel = ds.getSelected(); 160 List<Node> selectedNodes = new LinkedList<>(); 161 // fixNodes: All nodes for which the angle relative to center should not be modified 162 Set<Node> fixNodes = new HashSet<>(); 163 List<Way> ways = new LinkedList<>(); 164 EastNorth center = null; 165 double radius = 0; 166 167 for (OsmPrimitive osm : sel) { 168 if (osm instanceof Node) { 169 selectedNodes.add((Node) osm); 170 } else if (osm instanceof Way) { 171 ways.add((Way) osm); 172 } 173 } 174 175 // nodes on selected ways 176 List<Node> onWay = new ArrayList<>(); 177 if (!ways.isEmpty()) { 178 List<Node> potentialCenter = new ArrayList<>(); 179 for (Node n : selectedNodes) { 180 if (ways.stream().anyMatch(w -> w.containsNode(n))) { 181 onWay.add(n); 182 } else { 183 potentialCenter.add(n); 184 } 185 } 186 if (potentialCenter.size() == 1) { 187 // center is given 188 center = potentialCenter.get(0).getEastNorth(); 189 if (onWay.size() == 1) { 190 radius = center.distance(onWay.get(0).getEastNorth()); 191 } 192 } else if (potentialCenter.size() > 1) { 193 throw new InvalidSelection(tr("Please select only one node as center.")); 194 } 195 196 } 197 198 final List<Node> nodes; 199 if (ways.isEmpty()) { 200 nodes = sortByAngle(selectedNodes); 201 fixNodes.addAll(nodes); 202 } else if (ways.size() == 1 && !ways.get(0).isClosed()) { 203 // Case 1 204 Way w = ways.get(0); 205 fixNodes.add(w.firstNode()); 206 fixNodes.add(w.lastNode()); 207 fixNodes.addAll(onWay); 208 // Temporary closed way used to reorder nodes 209 Way closedWay = new Way(w); 210 try { 211 closedWay.addNode(w.firstNode()); 212 nodes = collectNodesAnticlockwise(Collections.singletonList(closedWay)); 213 } finally { 214 closedWay.setNodes(null); // see #19885 215 } 216 } else if (Multipolygon.joinWays(ways).size() == 1) { 217 // Case 2: 218 if (onWay.size() == 2) { 219 // 2 way nodes define diameter 220 EastNorth en0 = onWay.get(0).getEastNorth(); 221 EastNorth en1 = onWay.get(1).getEastNorth(); 222 radius = en0.distance(en1) / 2; 223 if (center == null) { 224 center = en0.getCenter(en1); 225 } 226 } 227 fixNodes.addAll(onWay); 228 nodes = collectNodesAnticlockwise(ways); 229 } else { 230 throw new InvalidSelection(); 231 } 232 fixNodes.addAll(collectNodesWithExternReferrers(ways)); 233 234 // Check if one or more nodes are outside of download area 235 if (nodes.stream().anyMatch(Node::isOutsideDownloadArea)) 236 throw new InvalidSelection(tr("One or more nodes involved in this action is outside of the downloaded area.")); 237 238 239 if (center == null) { 240 if (nodes.size() < 4) { 241 throw new InvalidSelection(tr("Not enough nodes to calculate center.")); 242 } 243 if (validateGeometry(nodes)) { 244 // Compute the center of nodes 245 center = Geometry.getCenter(nodes); 246 } 247 if (center == null) { 248 throw new InvalidSelection(tr("Cannot determine center of circle for this geometry.")); 249 } 250 } 251 252 // Now calculate the average distance to each node from the 253 // center. This method is ok as long as distances are short 254 // relative to the distance from the N or S poles. 255 if (radius == 0) { 256 for (Node n : nodes) { 257 radius += center.distance(n.getEastNorth()); 258 } 259 radius = radius / nodes.size(); 260 } 261 262 List<Command> cmds = new LinkedList<>(); 263 264 // Move each node to that distance from the center. 265 // Nodes that are not "fix" will be adjust making regular arcs. 266 int nodeCount = nodes.size(); 267 // Search first fixed node 268 int startPosition; 269 for (startPosition = 0; startPosition < nodeCount; startPosition++) { 270 if (fixNodes.contains(nodes.get(startPosition % nodeCount))) 271 break; 272 } 273 int i = startPosition; // Start position for current arc 274 int j; // End position for current arc 275 while (i < startPosition + nodeCount) { 276 for (j = i + 1; j < startPosition + nodeCount; j++) { 277 if (fixNodes.contains(nodes.get(j % nodeCount))) 278 break; 279 } 280 Node first = nodes.get(i % nodeCount); 281 PolarCoor pcFirst = new PolarCoor(radius, PolarCoor.computeAngle(first.getEastNorth(), center), center); 282 addMoveCommandIfNeeded(first, pcFirst, cmds); 283 if (j > i + 1) { 284 double delta; 285 if (j == i + nodeCount) { 286 delta = 2 * Math.PI / nodeCount; 287 } else { 288 PolarCoor pcLast = new PolarCoor(nodes.get(j % nodeCount).getEastNorth(), center); 289 delta = pcLast.angle - pcFirst.angle; 290 if (delta < 0) // Assume each PolarCoor.angle is in range ]-pi; pi] 291 delta += 2*Math.PI; 292 delta /= j - i; 293 } 294 for (int k = i+1; k < j; k++) { 295 PolarCoor p = new PolarCoor(radius, pcFirst.angle + (k-i)*delta, center); 296 addMoveCommandIfNeeded(nodes.get(k % nodeCount), p, cmds); 297 } 298 } 299 i = j; // Update start point for next iteration 300 } 301 if (cmds.isEmpty()) 302 return null; 303 return new SequenceCommand(tr("Align Nodes in Circle"), cmds); 304 } 305 306 private static List<Node> sortByAngle(final List<Node> nodes) { 307 EastNorth sum = new EastNorth(0, 0); 308 for (Node n : nodes) { 309 EastNorth en = n.getEastNorth(); 310 sum = sum.add(en.east(), en.north()); 311 } 312 final EastNorth simpleCenter = new EastNorth(sum.east()/nodes.size(), sum.north()/nodes.size()); 313 314 SortedMap<Double, List<Node>> orderedMap = new TreeMap<>(); 315 for (Node n : nodes) { 316 double angle = new PolarCoor(n.getEastNorth(), simpleCenter).angle; 317 orderedMap.computeIfAbsent(angle, k-> new ArrayList<>()).add(n); 318 } 319 return orderedMap.values().stream().flatMap(List<Node>::stream).collect(Collectors.toList()); 320 } 321 322 private static boolean validateGeometry(List<Node> nodes) { 323 Way test = new Way(); 324 test.setNodes(nodes); 325 if (!test.isClosed()) { 326 test.addNode(test.firstNode()); 327 } 328 329 try { 330 if (CrossingWays.isSelfCrossing(test)) 331 return false; 332 return !SelfIntersectingWay.isSelfIntersecting(test); 333 } finally { 334 test.setNodes(null); // see #19855 335 } 336 } 337 338 /** 339 * Collect all nodes with more than one referrer. 340 * @param ways Ways from witch nodes are selected 341 * @return List of nodes with more than one referrer 342 */ 343 private static List<Node> collectNodesWithExternReferrers(List<Way> ways) { 344 return ways.stream().flatMap(w -> w.getNodes().stream()).filter(n -> n.getReferrers().size() > 1).collect(Collectors.toList()); 345 } 346 347 /** 348 * Assuming all ways can be joined into polygon, create an ordered list of node. 349 * @param ways List of ways to be joined 350 * @return Nodes anticlockwise ordered 351 * @throws InvalidSelection if selection cannot be used 352 */ 353 private static List<Node> collectNodesAnticlockwise(List<Way> ways) throws InvalidSelection { 354 Collection<JoinedWay> rings = Multipolygon.joinWays(ways); 355 if (rings.size() != 1) 356 throw new InvalidSelection(); // we should never get here 357 List<Node> nodes = new ArrayList<>(rings.iterator().next().getNodes()); 358 if (nodes.get(0) != nodes.get(nodes.size() - 1)) 359 throw new InvalidSelection(); 360 if (Geometry.isClockwise(nodes)) 361 Collections.reverse(nodes); 362 nodes.remove(nodes.size() - 1); 363 return nodes; 364 } 365 366 @Override 367 protected void updateEnabledState() { 368 DataSet ds = getLayerManager().getEditDataSet(); 369 setEnabled(ds != null && !ds.selectionEmpty()); 370 } 371 372 @Override 373 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 374 updateEnabledStateOnModifiableSelection(selection); 375 } 376}