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

Last change on this file since 3504 was 3504, checked in by bastiK, 14 years ago

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