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

Last change on this file since 2667 was 2573, checked in by stoecker, 14 years ago

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