source: josm/trunk/src/org/openstreetmap/josm/actions/DistributeAction.java@ 11885

Last change on this file since 11885 was 11187, checked in by bastiK, 7 years ago

fixed #13864 - distribute nodes goes into infinite loop if 2 nodes have the same coordinates
  • Property svn:eol-style set to native
File size: 10.7 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.Collection;
10import java.util.HashSet;
11import java.util.Iterator;
12import java.util.LinkedList;
13import java.util.List;
14import java.util.Set;
15
16import javax.swing.JOptionPane;
17
18import org.openstreetmap.josm.Main;
19import org.openstreetmap.josm.command.Command;
20import org.openstreetmap.josm.command.MoveCommand;
21import org.openstreetmap.josm.command.SequenceCommand;
22import org.openstreetmap.josm.data.osm.Node;
23import org.openstreetmap.josm.data.osm.OsmPrimitive;
24import org.openstreetmap.josm.data.osm.Way;
25import org.openstreetmap.josm.gui.Notification;
26import org.openstreetmap.josm.tools.Shortcut;
27
28/**
29 * Distributes the selected nodes to equal distances along a line.
30 *
31 * @author Teemu Koskinen
32 */
33public final class DistributeAction extends JosmAction {
34
35 /**
36 * Constructs a new {@code DistributeAction}.
37 */
38 public DistributeAction() {
39 super(tr("Distribute Nodes"), "distribute",
40 tr("Distribute the selected nodes to equal distances along a line."),
41 Shortcut.registerShortcut("tools:distribute", tr("Tool: {0}", tr("Distribute Nodes")), KeyEvent.VK_B, Shortcut.SHIFT),
42 true);
43 putValue("help", ht("/Action/DistributeNodes"));
44 }
45
46 /**
47 * Perform action.
48 * Select method according to user selection.
49 * Case 1: One Way (no self-crossing) and at most 2 nodes contains by this way:
50 * Distribute nodes keeping order along the way
51 * Case 2: Other
52 * Distribute nodes
53 */
54 @Override
55 public void actionPerformed(ActionEvent e) {
56 if (!isEnabled())
57 return;
58
59 // Collect user selected objects
60 Collection<OsmPrimitive> selected = getLayerManager().getEditDataSet().getSelected();
61 Collection<Way> ways = new LinkedList<>();
62 Collection<Node> nodes = new HashSet<>();
63 for (OsmPrimitive osm : selected) {
64 if (osm instanceof Node) {
65 nodes.add((Node) osm);
66 } else if (osm instanceof Way) {
67 ways.add((Way) osm);
68 }
69 }
70
71 Set<Node> ignoredNodes = removeNodesWithoutCoordinates(nodes);
72 if (!ignoredNodes.isEmpty()) {
73 Main.warn(tr("Ignoring {0} nodes with null coordinates", ignoredNodes.size()));
74 ignoredNodes.clear();
75 }
76
77 // Switch between algorithms
78 Collection<Command> cmds;
79 if (checkDistributeWay(ways, nodes)) {
80 cmds = distributeWay(ways, nodes);
81 } else if (checkDistributeNodes(ways, nodes)) {
82 cmds = distributeNodes(nodes);
83 } else {
84 new Notification(
85 tr("Please select :\n" +
86 "* One no self-crossing way with at most two of its nodes;\n" +
87 "* Three nodes."))
88 .setIcon(JOptionPane.INFORMATION_MESSAGE)
89 .setDuration(Notification.TIME_SHORT)
90 .show();
91 return;
92 }
93
94 if (cmds.isEmpty()) {
95 return;
96 }
97
98 // Do it!
99 Main.main.undoRedo.add(new SequenceCommand(tr("Distribute Nodes"), cmds));
100 }
101
102 /**
103 * Test if one way, no self-crossing, is selected with at most two of its nodes.
104 * @param ways Selected ways
105 * @param nodes Selected nodes
106 * @return true in this case
107 */
108 private static boolean checkDistributeWay(Collection<Way> ways, Collection<Node> nodes) {
109 if (ways.size() == 1 && nodes.size() <= 2) {
110 Way w = ways.iterator().next();
111 Set<Node> unduplicated = new HashSet<>(w.getNodes());
112 if (unduplicated.size() != w.getNodesCount()) {
113 // No self crossing way
114 return false;
115 }
116 for (Node node: nodes) {
117 if (!w.containsNode(node)) {
118 return false;
119 }
120 }
121 return true;
122 }
123 return false;
124 }
125
126 /**
127 * Distribute nodes contained by a way, keeping nodes order.
128 * If one or two nodes are selected, keep these nodes in place.
129 * @param ways Selected ways, must be collection of size 1.
130 * @param nodes Selected nodes, at most two nodes.
131 * @return Collection of command to be executed.
132 */
133 private static Collection<Command> distributeWay(Collection<Way> ways,
134 Collection<Node> nodes) {
135 Way w = ways.iterator().next();
136 Collection<Command> cmds = new LinkedList<>();
137
138 if (w.getNodesCount() == nodes.size() || w.getNodesCount() <= 2) {
139 // Nothing to do
140 return cmds;
141 }
142
143 double xa, ya; // Start point
144 double dx, dy; // Segment increment
145 if (nodes.isEmpty()) {
146 Node na = w.firstNode();
147 nodes.add(na);
148 Node nb = w.lastNode();
149 nodes.add(nb);
150 xa = na.getEastNorth().east();
151 ya = na.getEastNorth().north();
152 dx = (nb.getEastNorth().east() - xa) / (w.getNodesCount() - 1);
153 dy = (nb.getEastNorth().north() - ya) / (w.getNodesCount() - 1);
154 } else if (nodes.size() == 1) {
155 Node n = nodes.iterator().next();
156 int nIdx = w.getNodes().indexOf(n);
157 Node na = w.firstNode();
158 Node nb = w.lastNode();
159 dx = (nb.getEastNorth().east() - na.getEastNorth().east()) /
160 (w.getNodesCount() - 1);
161 dy = (nb.getEastNorth().north() - na.getEastNorth().north()) /
162 (w.getNodesCount() - 1);
163 xa = n.getEastNorth().east() - dx * nIdx;
164 ya = n.getEastNorth().north() - dy * nIdx;
165 } else {
166 Iterator<Node> it = nodes.iterator();
167 Node na = it.next();
168 Node nb = it.next();
169 List<Node> wayNodes = w.getNodes();
170 int naIdx = wayNodes.indexOf(na);
171 int nbIdx = wayNodes.indexOf(nb);
172 dx = (nb.getEastNorth().east() - na.getEastNorth().east()) / (nbIdx - naIdx);
173 dy = (nb.getEastNorth().north() - na.getEastNorth().north()) / (nbIdx - naIdx);
174 xa = na.getEastNorth().east() - dx * naIdx;
175 ya = na.getEastNorth().north() - dy * naIdx;
176 }
177
178 for (int i = 0; i < w.getNodesCount(); i++) {
179 Node n = w.getNode(i);
180 if (!n.isLatLonKnown() || nodes.contains(n)) {
181 continue;
182 }
183 double x = xa + i * dx;
184 double y = ya + i * dy;
185 cmds.add(new MoveCommand(n, x - n.getEastNorth().east(),
186 y - n.getEastNorth().north()));
187 }
188 return cmds;
189 }
190
191 /**
192 * Test if nodes oriented algorithm applies to the selection.
193 * @param ways Selected ways
194 * @param nodes Selected nodes
195 * @return true in this case
196 */
197 private static Boolean checkDistributeNodes(Collection<Way> ways, Collection<Node> nodes) {
198 return ways.isEmpty() && nodes.size() >= 3;
199 }
200
201 /**
202 * Distribute nodes when only nodes are selected.
203 * The general algorithm here is to find the two selected nodes
204 * that are furthest apart, and then to distribute all other selected
205 * nodes along the straight line between these nodes.
206 * @param nodes nodes to distribute
207 * @return Commands to execute to perform action
208 * @throws IllegalArgumentException if nodes is empty
209 */
210 private static Collection<Command> distributeNodes(Collection<Node> nodes) {
211 // Find from the selected nodes two that are the furthest apart.
212 // Let's call them A and B.
213 double distance = Double.NEGATIVE_INFINITY;
214
215 Node nodea = null;
216 Node nodeb = null;
217
218 Collection<Node> itnodes = new LinkedList<>(nodes);
219 for (Node n : nodes) {
220 itnodes.remove(n);
221 for (Node m : itnodes) {
222 double dist = Math.sqrt(n.getEastNorth().distance(m.getEastNorth()));
223 if (dist > distance) {
224 nodea = n;
225 nodeb = m;
226 distance = dist;
227 }
228 }
229 }
230
231 if (nodea == null || nodeb == null) {
232 throw new IllegalArgumentException();
233 }
234
235 // Remove the nodes A and B from the list of nodes to move
236 nodes.remove(nodea);
237 nodes.remove(nodeb);
238
239 // Find out co-ords of A and B
240 double ax = nodea.getEastNorth().east();
241 double ay = nodea.getEastNorth().north();
242 double bx = nodeb.getEastNorth().east();
243 double by = nodeb.getEastNorth().north();
244
245 // A list of commands to do
246 Collection<Command> cmds = new LinkedList<>();
247
248 // Amount of nodes between A and B plus 1
249 int num = nodes.size()+1;
250
251 // Current number of node
252 int pos = 0;
253 while (!nodes.isEmpty()) {
254 pos++;
255 Node s = null;
256
257 // Find the node that is furthest from B (i.e. closest to A)
258 distance = Double.NEGATIVE_INFINITY;
259 for (Node n : nodes) {
260 double dist = Math.sqrt(nodeb.getEastNorth().distance(n.getEastNorth()));
261 if (dist > distance) {
262 s = n;
263 distance = dist;
264 }
265 }
266
267 if (s != null) {
268 // First move the node to A's position, then move it towards B
269 double dx = ax - s.getEastNorth().east() + (bx-ax)*pos/num;
270 double dy = ay - s.getEastNorth().north() + (by-ay)*pos/num;
271
272 cmds.add(new MoveCommand(s, dx, dy));
273
274 //remove moved node from the list
275 nodes.remove(s);
276 }
277 }
278
279 return cmds;
280 }
281
282 /**
283 * Remove nodes without knowned coordinates from a collection.
284 * @param col Collection of nodes to check
285 * @return Set of nodes without coordinates
286 */
287 private static Set<Node> removeNodesWithoutCoordinates(Collection<Node> col) {
288 Set<Node> result = new HashSet<>();
289 for (Iterator<Node> it = col.iterator(); it.hasNext();) {
290 Node n = it.next();
291 if (!n.isLatLonKnown()) {
292 it.remove();
293 result.add(n);
294 }
295 }
296 return result;
297 }
298
299 @Override
300 protected void updateEnabledState() {
301 updateEnabledStateOnCurrentSelection();
302 }
303
304 @Override
305 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
306 setEnabled(selection != null && !selection.isEmpty());
307 }
308}
Note: See TracBrowser for help on using the repository browser.