source: josm/trunk/src/org/openstreetmap/josm/actions/AlignInCircleAction.java@ 17414

Last change on this file since 17414 was 17393, checked in by GerdP, 3 years ago

see #10205: Strange align nodes in circle behavior

  • allow to define center node also when a single unclosed way is selected
  • add robustness and more unit tests for evaluation of valid selections
  • if only nodes and no way are selected, order the nodes using the angle to the agv. east-north position. This should produce a predictable result
  • if way(s) are selected the order the nodes is determined by the occurence in the way(s). Self-Intersecting polygons are rejected if no center node is given
  • don't throw InvalidSelection when selection is valid but no point was moved, let buildCommand() return null instead

With a selection that gives a center point and way(s) which are not even close to a circular shape the result might still be surprising. Sometimes the way nodes are arranged around the center node, sometimes they are moved so that a circle arc with nearly the same length is produced. The result changes significantly when the way nodes are also selected. Subject to further improvements.
  • Property svn:eol-style set to native
File size: 14.3 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
5import static org.openstreetmap.josm.tools.I18n.tr;
6
7import java.awt.event.ActionEvent;
8import java.awt.event.KeyEvent;
9import java.util.ArrayList;
10import java.util.Collection;
11import java.util.Collections;
12import java.util.HashSet;
13import java.util.LinkedList;
14import java.util.List;
15import java.util.Set;
16import java.util.SortedMap;
17import java.util.TreeMap;
18import java.util.stream.Collectors;
19
20import javax.swing.JOptionPane;
21
22import org.openstreetmap.josm.command.Command;
23import org.openstreetmap.josm.command.MoveCommand;
24import org.openstreetmap.josm.command.SequenceCommand;
25import org.openstreetmap.josm.data.UndoRedoHandler;
26import org.openstreetmap.josm.data.coor.EastNorth;
27import org.openstreetmap.josm.data.coor.PolarCoor;
28import org.openstreetmap.josm.data.osm.DataSet;
29import org.openstreetmap.josm.data.osm.Node;
30import org.openstreetmap.josm.data.osm.OsmPrimitive;
31import org.openstreetmap.josm.data.osm.Way;
32import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon;
33import org.openstreetmap.josm.data.osm.visitor.paint.relations.Multipolygon.JoinedWay;
34import org.openstreetmap.josm.data.validation.tests.CrossingWays;
35import org.openstreetmap.josm.data.validation.tests.SelfIntersectingWay;
36import org.openstreetmap.josm.gui.Notification;
37import org.openstreetmap.josm.tools.Geometry;
38import org.openstreetmap.josm.tools.Logging;
39import org.openstreetmap.josm.tools.Shortcut;
40
41/**
42 * Aligns all selected nodes within a circle. (Useful for roundabouts)
43 *
44 * @author Matthew Newton
45 * @author Petr Dlouhý
46 * @author Teemu Koskinen
47 * @author Alain Delplanque
48 * @author Gerd Petermann
49 *
50 * @since 146
51 */
52public final class AlignInCircleAction extends JosmAction {
53
54 /**
55 * Constructs a new {@code AlignInCircleAction}.
56 */
57 public AlignInCircleAction() {
58 super(tr("Align Nodes in Circle"), "aligncircle", tr("Move the selected nodes into a circle."),
59 Shortcut.registerShortcut("tools:aligncircle", tr("Tools: {0}", tr("Align Nodes in Circle")),
60 KeyEvent.VK_O, Shortcut.DIRECT), true);
61 setHelpId(ht("/Action/AlignInCircle"));
62 }
63
64 /**
65 * InvalidSelection exception has to be raised when action can't be performed
66 */
67 public static class InvalidSelection extends Exception {
68
69 /**
70 * Create an InvalidSelection exception with default message
71 */
72 InvalidSelection() {
73 super(tr("Selection could not be used to align in circle."));
74 }
75
76 /**
77 * Create an InvalidSelection exception with specific message
78 * @param msg Message that will be displayed to the user
79 */
80 InvalidSelection(String msg) {
81 super(msg);
82 }
83 }
84
85 /**
86 * Add a {@link MoveCommand} to move a node to a PolarCoor if there is a significant move.
87 * @param n Node to move
88 * @param coor polar coordinate where to move the node
89 * @param cmds list of commands
90 * @since 17386
91 */
92 public static void addMoveCommandIfNeeded(Node n, PolarCoor coor, List<Command> cmds) {
93 EastNorth en = coor.toEastNorth();
94 double deltaEast = en.east() - n.getEastNorth().east();
95 double deltaNorth = en.north() - n.getEastNorth().north();
96
97 if (Math.abs(deltaEast) > 5e-6 || Math.abs(deltaNorth) > 5e-6) {
98 cmds.add(new MoveCommand(n, deltaEast, deltaNorth));
99 }
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 * --&gt; 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 * --&gt; 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 * --&gt; 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}
Note: See TracBrowser for help on using the repository browser.