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

Last change on this file since 2210 was 2210, checked in by Gubaer, 15 years ago

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