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

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

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