source: josm/trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java@ 6453

Last change on this file since 6453 was 6380, checked in by Don-vip, 10 years ago

update license/copyright information
  • Property svn:eol-style set to native
File size: 21.8 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.LinkedHashMap;
14import java.util.LinkedHashSet;
15import java.util.LinkedList;
16import java.util.List;
17import java.util.Map;
18import java.util.Set;
19import java.util.Stack;
20
21import javax.swing.JOptionPane;
22
23import org.openstreetmap.josm.Main;
24import org.openstreetmap.josm.command.ChangeCommand;
25import org.openstreetmap.josm.command.Command;
26import org.openstreetmap.josm.command.DeleteCommand;
27import org.openstreetmap.josm.command.SequenceCommand;
28import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
29import org.openstreetmap.josm.corrector.UserCancelException;
30import org.openstreetmap.josm.data.osm.Node;
31import org.openstreetmap.josm.data.osm.OsmPrimitive;
32import org.openstreetmap.josm.data.osm.TagCollection;
33import org.openstreetmap.josm.data.osm.Way;
34import org.openstreetmap.josm.data.preferences.BooleanProperty;
35import org.openstreetmap.josm.gui.ExtendedDialog;
36import org.openstreetmap.josm.gui.Notification;
37import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
38import org.openstreetmap.josm.gui.util.GuiHelper;
39import org.openstreetmap.josm.tools.Pair;
40import org.openstreetmap.josm.tools.Shortcut;
41
42/**
43 * Combines multiple ways into one.
44 * @since 213
45 */
46public class CombineWayAction extends JosmAction {
47
48 private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
49
50 /**
51 * Constructs a new {@code CombineWayAction}.
52 */
53 public CombineWayAction() {
54 super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
55 Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
56 putValue("help", ht("/Action/CombineWay"));
57 }
58
59 protected static boolean confirmChangeDirectionOfWays() {
60 ExtendedDialog ed = new ExtendedDialog(Main.parent,
61 tr("Change directions?"),
62 new String[] {tr("Reverse and Combine"), tr("Cancel")});
63 ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
64 ed.setContent(tr("The ways can not be combined in their current directions. "
65 + "Do you want to reverse some of them?"));
66 ed.showDialog();
67 return ed.getValue() == 1;
68 }
69
70 protected static void warnCombiningImpossible() {
71 String msg = tr("Could not combine ways<br>"
72 + "(They could not be merged into a single string of nodes)");
73 new Notification(msg)
74 .setIcon(JOptionPane.INFORMATION_MESSAGE)
75 .show();
76 return;
77 }
78
79 protected static Way getTargetWay(Collection<Way> combinedWays) {
80 // init with an arbitrary way
81 Way targetWay = combinedWays.iterator().next();
82
83 // look for the first way already existing on
84 // the server
85 for (Way w : combinedWays) {
86 targetWay = w;
87 if (!w.isNew()) {
88 break;
89 }
90 }
91 return targetWay;
92 }
93
94 /**
95 * @param ways
96 * @return null if ways cannot be combined. Otherwise returns the combined
97 * ways and the commands to combine
98 * @throws UserCancelException
99 */
100 public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
101
102 // prepare and clean the list of ways to combine
103 //
104 if (ways == null || ways.isEmpty())
105 return null;
106 ways.remove(null); // just in case - remove all null ways from the collection
107
108 // remove duplicates, preserving order
109 ways = new LinkedHashSet<Way>(ways);
110
111 // try to build a new way which includes all the combined
112 // ways
113 //
114 NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
115 List<Node> path = graph.buildSpanningPath();
116 if (path == null) {
117 warnCombiningImpossible();
118 return null;
119 }
120 // check whether any ways have been reversed in the process
121 // and build the collection of tags used by the ways to combine
122 //
123 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
124
125 List<Way> reversedWays = new LinkedList<Way>();
126 List<Way> unreversedWays = new LinkedList<Way>();
127 for (Way w: ways) {
128 // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
129 if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
130 unreversedWays.add(w);
131 } else {
132 reversedWays.add(w);
133 }
134 }
135 // reverse path if all ways have been reversed
136 if (unreversedWays.isEmpty()) {
137 Collections.reverse(path);
138 unreversedWays = reversedWays;
139 reversedWays = null;
140 }
141 if ((reversedWays != null) && !reversedWays.isEmpty()) {
142 if (!confirmChangeDirectionOfWays()) return null;
143 // filter out ways that have no direction-dependent tags
144 unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
145 reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
146 // reverse path if there are more reversed than unreversed ways with direction-dependent tags
147 if (reversedWays.size() > unreversedWays.size()) {
148 Collections.reverse(path);
149 List<Way> tempWays = unreversedWays;
150 unreversedWays = reversedWays;
151 reversedWays = tempWays;
152 }
153 // if there are still reversed ways with direction-dependent tags, reverse their tags
154 if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
155 List<Way> unreversedTagWays = new ArrayList<Way>(ways);
156 unreversedTagWays.removeAll(reversedWays);
157 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
158 List<Way> reversedTagWays = new ArrayList<Way>(reversedWays.size());
159 Collection<Command> changePropertyCommands = null;
160 for (Way w : reversedWays) {
161 Way wnew = new Way(w);
162 reversedTagWays.add(wnew);
163 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
164 }
165 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
166 for (Command c : changePropertyCommands) {
167 c.executeCommand();
168 }
169 }
170 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
171 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
172 }
173 }
174
175 // create the new way and apply the new node list
176 //
177 Way targetWay = getTargetWay(ways);
178 Way modifiedTargetWay = new Way(targetWay);
179 modifiedTargetWay.setNodes(path);
180
181 List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
182
183 LinkedList<Command> cmds = new LinkedList<Command>();
184 LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
185 deletedWays.remove(targetWay);
186
187 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
188 cmds.addAll(resolution);
189 cmds.add(new DeleteCommand(deletedWays));
190 final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
191
192 return new Pair<Way, Command>(targetWay, sequenceCommand);
193 }
194
195 @Override
196 public void actionPerformed(ActionEvent event) {
197 if (getCurrentDataSet() == null)
198 return;
199 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
200 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
201 if (selectedWays.size() < 2) {
202 new Notification(
203 tr("Please select at least two ways to combine."))
204 .setIcon(JOptionPane.INFORMATION_MESSAGE)
205 .setDuration(Notification.TIME_SHORT)
206 .show();
207 return;
208 }
209 // combine and update gui
210 Pair<Way, Command> combineResult;
211 try {
212 combineResult = combineWaysWorker(selectedWays);
213 } catch (UserCancelException ex) {
214 return;
215 }
216
217 if (combineResult == null)
218 return;
219 final Way selectedWay = combineResult.a;
220 Main.main.undoRedo.add(combineResult.b);
221 if(selectedWay != null)
222 {
223 Runnable guiTask = new Runnable() {
224 @Override
225 public void run() {
226 getCurrentDataSet().setSelected(selectedWay);
227 }
228 };
229 GuiHelper.runInEDT(guiTask);
230 }
231 }
232
233 @Override
234 protected void updateEnabledState() {
235 if (getCurrentDataSet() == null) {
236 setEnabled(false);
237 return;
238 }
239 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
240 updateEnabledState(selection);
241 }
242
243 @Override
244 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
245 int numWays = 0;
246 for (OsmPrimitive osm : selection)
247 if (osm instanceof Way) {
248 numWays++;
249 }
250 setEnabled(numWays >= 2);
251 }
252
253 /**
254 * A pair of nodes.
255 */
256 static public class NodePair {
257 private final Node a;
258 private final Node b;
259
260 /**
261 * Constructs a new {@code NodePair}.
262 * @param a The first node
263 * @param b The second node
264 */
265 public NodePair(Node a, Node b) {
266 this.a = a;
267 this.b = b;
268 }
269
270 /**
271 * Constructs a new {@code NodePair}.
272 * @param pair An existing {@code Pair} of nodes
273 */
274 public NodePair(Pair<Node,Node> pair) {
275 this(pair.a, pair.b);
276 }
277
278 /**
279 * Constructs a new {@code NodePair}.
280 * @param other An existing {@code NodePair}
281 */
282 public NodePair(NodePair other) {
283 this(other.a, other.b);
284 }
285
286 /**
287 * Replies the first node.
288 * @return The first node
289 */
290 public Node getA() {
291 return a;
292 }
293
294 /**
295 * Replies the second node
296 * @return The second node
297 */
298 public Node getB() {
299 return b;
300 }
301
302 public boolean isAdjacentToA(NodePair other) {
303 return other.getA() == a || other.getB() == a;
304 }
305
306 public boolean isAdjacentToB(NodePair other) {
307 return other.getA() == b || other.getB() == b;
308 }
309
310 public boolean isSuccessorOf(NodePair other) {
311 return other.getB() == a;
312 }
313
314 public boolean isPredecessorOf(NodePair other) {
315 return b == other.getA();
316 }
317
318 public NodePair swap() {
319 return new NodePair(b,a);
320 }
321
322 @Override
323 public String toString() {
324 return new StringBuilder()
325 .append("[")
326 .append(a.getId())
327 .append(",")
328 .append(b.getId())
329 .append("]")
330 .toString();
331 }
332
333 /**
334 * Determines if this pair contains the given node.
335 * @param n The node to look for
336 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
337 */
338 public boolean contains(Node n) {
339 return a == n || b == n;
340 }
341
342 @Override
343 public int hashCode() {
344 final int prime = 31;
345 int result = 1;
346 result = prime * result + ((a == null) ? 0 : a.hashCode());
347 result = prime * result + ((b == null) ? 0 : b.hashCode());
348 return result;
349 }
350
351 @Override
352 public boolean equals(Object obj) {
353 if (this == obj)
354 return true;
355 if (obj == null)
356 return false;
357 if (getClass() != obj.getClass())
358 return false;
359 NodePair other = (NodePair) obj;
360 if (a == null) {
361 if (other.a != null)
362 return false;
363 } else if (!a.equals(other.a))
364 return false;
365 if (b == null) {
366 if (other.b != null)
367 return false;
368 } else if (!b.equals(other.b))
369 return false;
370 return true;
371 }
372 }
373
374 static public class NodeGraph {
375 static public List<NodePair> buildNodePairs(Way way, boolean directed) {
376 List<NodePair> pairs = new ArrayList<NodePair>();
377 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
378 pairs.add(new NodePair(pair));
379 if (!directed) {
380 pairs.add(new NodePair(pair).swap());
381 }
382 }
383 return pairs;
384 }
385
386 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
387 List<NodePair> pairs = new ArrayList<NodePair>();
388 for (Way w: ways) {
389 pairs.addAll(buildNodePairs(w, directed));
390 }
391 return pairs;
392 }
393
394 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
395 List<NodePair> cleaned = new ArrayList<NodePair>();
396 for(NodePair p: pairs) {
397 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
398 cleaned.add(p);
399 }
400 }
401 return cleaned;
402 }
403
404 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
405 NodeGraph graph = new NodeGraph();
406 for (NodePair pair: pairs) {
407 graph.add(pair);
408 }
409 return graph;
410 }
411
412 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
413 NodeGraph graph = new NodeGraph();
414 for (Way w: ways) {
415 graph.add(buildNodePairs(w, true /* directed */));
416 }
417 return graph;
418 }
419
420 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
421 NodeGraph graph = new NodeGraph();
422 for (NodePair pair: pairs) {
423 graph.add(pair);
424 graph.add(pair.swap());
425 }
426 return graph;
427 }
428
429 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
430 NodeGraph graph = new NodeGraph();
431 for (Way w: ways) {
432 graph.add(buildNodePairs(w, false /* undirected */));
433 }
434 return graph;
435 }
436
437 private Set<NodePair> edges;
438 private int numUndirectedEges = 0;
439 private Map<Node, List<NodePair>> successors;
440 private Map<Node, List<NodePair>> predecessors;
441
442 protected void rememberSuccessor(NodePair pair) {
443 if (successors.containsKey(pair.getA())) {
444 if (!successors.get(pair.getA()).contains(pair)) {
445 successors.get(pair.getA()).add(pair);
446 }
447 } else {
448 List<NodePair> l = new ArrayList<NodePair>();
449 l.add(pair);
450 successors.put(pair.getA(), l);
451 }
452 }
453
454 protected void rememberPredecessors(NodePair pair) {
455 if (predecessors.containsKey(pair.getB())) {
456 if (!predecessors.get(pair.getB()).contains(pair)) {
457 predecessors.get(pair.getB()).add(pair);
458 }
459 } else {
460 List<NodePair> l = new ArrayList<NodePair>();
461 l.add(pair);
462 predecessors.put(pair.getB(), l);
463 }
464 }
465
466 protected boolean isTerminalNode(Node n) {
467 if (successors.get(n) == null) return false;
468 if (successors.get(n).size() != 1) return false;
469 if (predecessors.get(n) == null) return true;
470 if (predecessors.get(n).size() == 1) {
471 NodePair p1 = successors.get(n).iterator().next();
472 NodePair p2 = predecessors.get(n).iterator().next();
473 return p1.equals(p2.swap());
474 }
475 return false;
476 }
477
478 protected void prepare() {
479 Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
480 successors = new LinkedHashMap<Node, List<NodePair>>();
481 predecessors = new LinkedHashMap<Node, List<NodePair>>();
482
483 for (NodePair pair: edges) {
484 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
485 undirectedEdges.add(pair);
486 }
487 rememberSuccessor(pair);
488 rememberPredecessors(pair);
489 }
490 numUndirectedEges = undirectedEdges.size();
491 }
492
493 /**
494 * Constructs a new {@code NodeGraph}.
495 */
496 public NodeGraph() {
497 edges = new LinkedHashSet<NodePair>();
498 }
499
500 public void add(NodePair pair) {
501 if (!edges.contains(pair)) {
502 edges.add(pair);
503 }
504 }
505
506 public void add(List<NodePair> pairs) {
507 for (NodePair pair: pairs) {
508 add(pair);
509 }
510 }
511
512 protected Node getStartNode() {
513 Set<Node> nodes = getNodes();
514 for (Node n: nodes) {
515 if (successors.get(n) != null && successors.get(n).size() ==1)
516 return n;
517 }
518 return null;
519 }
520
521 protected Set<Node> getTerminalNodes() {
522 Set<Node> ret = new LinkedHashSet<Node>();
523 for (Node n: getNodes()) {
524 if (isTerminalNode(n)) {
525 ret.add(n);
526 }
527 }
528 return ret;
529 }
530
531 protected Set<Node> getNodes(Stack<NodePair> pairs) {
532 HashSet<Node> nodes = new LinkedHashSet<Node>(2*pairs.size());
533 for (NodePair pair: pairs) {
534 nodes.add(pair.getA());
535 nodes.add(pair.getB());
536 }
537 return nodes;
538 }
539
540 protected List<NodePair> getOutboundPairs(NodePair pair) {
541 return getOutboundPairs(pair.getB());
542 }
543
544 protected List<NodePair> getOutboundPairs(Node node) {
545 List<NodePair> l = successors.get(node);
546 if (l == null)
547 return Collections.emptyList();
548 return l;
549 }
550
551 protected Set<Node> getNodes() {
552 Set<Node> nodes = new LinkedHashSet<Node>(2 * edges.size());
553 for (NodePair pair: edges) {
554 nodes.add(pair.getA());
555 nodes.add(pair.getB());
556 }
557 return nodes;
558 }
559
560 protected boolean isSpanningWay(Stack<NodePair> way) {
561 return numUndirectedEges == way.size();
562 }
563
564 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
565 LinkedList<Node> ret = new LinkedList<Node>();
566 for (NodePair pair: path) {
567 ret.add(pair.getA());
568 }
569 ret.add(path.peek().getB());
570 return ret;
571 }
572
573 /**
574 * Tries to find a spanning path starting from node <code>startNode</code>.
575 *
576 * Traverses the path in depth-first order.
577 *
578 * @param startNode the start node
579 * @return the spanning path; null, if no path is found
580 */
581 protected List<Node> buildSpanningPath(Node startNode) {
582 if (startNode == null)
583 return null;
584 Stack<NodePair> path = new Stack<NodePair>();
585 Stack<NodePair> nextPairs = new Stack<NodePair>();
586 nextPairs.addAll(getOutboundPairs(startNode));
587 while(!nextPairs.isEmpty()) {
588 NodePair cur= nextPairs.pop();
589 if (! path.contains(cur) && ! path.contains(cur.swap())) {
590 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
591 path.pop();
592 }
593 path.push(cur);
594 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
595 nextPairs.addAll(getOutboundPairs(path.peek()));
596 }
597 }
598 return null;
599 }
600
601 /**
602 * Tries to find a path through the graph which visits each edge (i.e.
603 * the segment of a way) exactly one.
604 *
605 * @return the path; null, if no path was found
606 */
607 public List<Node> buildSpanningPath() {
608 prepare();
609 // try to find a path from each "terminal node", i.e. from a
610 // node which is connected by exactly one undirected edges (or
611 // two directed edges in opposite direction) to the graph. A
612 // graph built up from way segments is likely to include such
613 // nodes, unless all ways are closed.
614 // In the worst case this loops over all nodes which is
615 // very slow for large ways.
616 //
617 Set<Node> nodes = getTerminalNodes();
618 nodes = nodes.isEmpty() ? getNodes() : nodes;
619 for (Node n: nodes) {
620 List<Node> path = buildSpanningPath(n);
621 if (path != null)
622 return path;
623 }
624 return null;
625 }
626 }
627}
Note: See TracBrowser for help on using the repository browser.