source: josm/trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java@ 6822

Last change on this file since 6822 was 6639, checked in by simon04, 10 years ago

fix #9544 - Skip nodes outside of download area for BarriersEntrances and WayConnectedToArea validation tests
  • Property svn:eol-style set to native
File size: 50.6 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.tools.I18n.marktr;
5import static org.openstreetmap.josm.tools.I18n.tr;
6import static org.openstreetmap.josm.tools.I18n.trn;
7
8import java.awt.event.ActionEvent;
9import java.awt.event.KeyEvent;
10import java.util.ArrayList;
11import java.util.Collection;
12import java.util.Collections;
13import java.util.HashMap;
14import java.util.HashSet;
15import java.util.LinkedHashSet;
16import java.util.LinkedList;
17import java.util.List;
18import java.util.Map;
19import java.util.Set;
20import java.util.TreeMap;
21
22import javax.swing.JOptionPane;
23
24import org.openstreetmap.josm.Main;
25import org.openstreetmap.josm.actions.ReverseWayAction.ReverseWayResult;
26import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult;
27import org.openstreetmap.josm.command.AddCommand;
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.UserCancelException;
33import org.openstreetmap.josm.data.UndoRedoHandler;
34import org.openstreetmap.josm.data.coor.EastNorth;
35import org.openstreetmap.josm.data.osm.DataSet;
36import org.openstreetmap.josm.data.osm.Node;
37import org.openstreetmap.josm.data.osm.NodePositionComparator;
38import org.openstreetmap.josm.data.osm.OsmPrimitive;
39import org.openstreetmap.josm.data.osm.Relation;
40import org.openstreetmap.josm.data.osm.RelationMember;
41import org.openstreetmap.josm.data.osm.TagCollection;
42import org.openstreetmap.josm.data.osm.Way;
43import org.openstreetmap.josm.gui.Notification;
44import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
45import org.openstreetmap.josm.tools.Geometry;
46import org.openstreetmap.josm.tools.Pair;
47import org.openstreetmap.josm.tools.Shortcut;
48
49/**
50 * Join Areas (i.e. closed ways and multipolygons)
51 */
52public class JoinAreasAction extends JosmAction {
53 // This will be used to commit commands and unite them into one large command sequence at the end
54 private LinkedList<Command> cmds = new LinkedList<Command>();
55 private int cmdsCount = 0;
56
57 /**
58 * This helper class describes join ares action result.
59 * @author viesturs
60 *
61 */
62 public static class JoinAreasResult {
63
64 public boolean hasChanges;
65
66 public List<Multipolygon> polygons;
67 }
68
69 public static class Multipolygon {
70 public Way outerWay;
71 public List<Way> innerWays;
72
73 public Multipolygon(Way way) {
74 outerWay = way;
75 innerWays = new ArrayList<Way>();
76 }
77 }
78
79 // HelperClass
80 // Saves a relation and a role an OsmPrimitve was part of until it was stripped from all relations
81 private static class RelationRole {
82 public final Relation rel;
83 public final String role;
84 public RelationRole(Relation rel, String role) {
85 this.rel = rel;
86 this.role = role;
87 }
88
89 @Override
90 public int hashCode() {
91 return rel.hashCode();
92 }
93
94 @Override
95 public boolean equals(Object other) {
96 if (!(other instanceof RelationRole)) return false;
97 RelationRole otherMember = (RelationRole) other;
98 return otherMember.role.equals(role) && otherMember.rel.equals(rel);
99 }
100 }
101
102
103 /**
104 * HelperClass - saves a way and the "inside" side.
105 *
106 * insideToTheLeft: if true left side is "in", false -right side is "in".
107 * Left and right are determined along the orientation of way.
108 */
109 public static class WayInPolygon {
110 public final Way way;
111 public boolean insideToTheRight;
112
113 public WayInPolygon(Way _way, boolean _insideRight) {
114 this.way = _way;
115 this.insideToTheRight = _insideRight;
116 }
117
118 @Override
119 public int hashCode() {
120 return way.hashCode();
121 }
122
123 @Override
124 public boolean equals(Object other) {
125 if (!(other instanceof WayInPolygon)) return false;
126 WayInPolygon otherMember = (WayInPolygon) other;
127 return otherMember.way.equals(this.way) && otherMember.insideToTheRight == this.insideToTheRight;
128 }
129 }
130
131 /**
132 * This helper class describes a polygon, assembled from several ways.
133 * @author viesturs
134 *
135 */
136 public static class AssembledPolygon {
137 public List<WayInPolygon> ways;
138
139 public AssembledPolygon(List<WayInPolygon> boundary) {
140 this.ways = boundary;
141 }
142
143 public List<Node> getNodes() {
144 List<Node> nodes = new ArrayList<Node>();
145 for (WayInPolygon way : this.ways) {
146 //do not add the last node as it will be repeated in the next way
147 if (way.insideToTheRight) {
148 for (int pos = 0; pos < way.way.getNodesCount() - 1; pos++) {
149 nodes.add(way.way.getNode(pos));
150 }
151 }
152 else {
153 for (int pos = way.way.getNodesCount() - 1; pos > 0; pos--) {
154 nodes.add(way.way.getNode(pos));
155 }
156 }
157 }
158
159 return nodes;
160 }
161 }
162
163 public static class AssembledMultipolygon {
164 public AssembledPolygon outerWay;
165 public List<AssembledPolygon> innerWays;
166
167 public AssembledMultipolygon(AssembledPolygon way) {
168 outerWay = way;
169 innerWays = new ArrayList<AssembledPolygon>();
170 }
171 }
172
173 /**
174 * This hepler class implements algorithm traversing trough connected ways.
175 * Assumes you are going in clockwise orientation.
176 * @author viesturs
177 *
178 */
179 private static class WayTraverser {
180
181 private Set<WayInPolygon> availableWays;
182 private WayInPolygon lastWay;
183 private boolean lastWayReverse;
184
185 public WayTraverser(Collection<WayInPolygon> ways) {
186
187 availableWays = new HashSet<WayInPolygon>(ways);
188 lastWay = null;
189 }
190
191 public void removeWays(Collection<WayInPolygon> ways) {
192 availableWays.removeAll(ways);
193 }
194
195 public boolean hasWays() {
196 return !availableWays.isEmpty();
197 }
198
199 public WayInPolygon startNewWay(WayInPolygon way) {
200 lastWay = way;
201 lastWayReverse = !lastWay.insideToTheRight;
202
203 return lastWay;
204 }
205
206 public WayInPolygon startNewWay() {
207 if (availableWays.isEmpty()) {
208 lastWay = null;
209 } else {
210 lastWay = availableWays.iterator().next();
211 lastWayReverse = !lastWay.insideToTheRight;
212 }
213
214 return lastWay;
215 }
216
217
218 public WayInPolygon advanceNextLeftmostWay() {
219 return advanceNextWay(false);
220 }
221
222 public WayInPolygon advanceNextRightmostWay() {
223 return advanceNextWay(true);
224 }
225
226 private WayInPolygon advanceNextWay(boolean rightmost) {
227
228 Node headNode = !lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
229 Node prevNode = !lastWayReverse ? lastWay.way.getNode(lastWay.way.getNodesCount() - 2) : lastWay.way.getNode(1);
230
231 //find best next way
232 WayInPolygon bestWay = null;
233 Node bestWayNextNode = null;
234 boolean bestWayReverse = false;
235
236 for (WayInPolygon way : availableWays) {
237 if (way.way.firstNode().equals(headNode)) {
238 //start adjacent to headNode
239 Node nextNode = way.way.getNode(1);
240
241 if (nextNode.equals(prevNode))
242 {
243 //this is the path we came from - ignore it.
244 }
245 else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
246 //the new way is better
247 bestWay = way;
248 bestWayReverse = false;
249 bestWayNextNode = nextNode;
250 }
251 }
252
253 if (way.way.lastNode().equals(headNode)) {
254 //end adjacent to headNode
255 Node nextNode = way.way.getNode(way.way.getNodesCount() - 2);
256
257 if (nextNode.equals(prevNode)) {
258 //this is the path we came from - ignore it.
259 }
260 else if (bestWay == null || (Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode) == rightmost)) {
261 //the new way is better
262 bestWay = way;
263 bestWayReverse = true;
264 bestWayNextNode = nextNode;
265 }
266 }
267 }
268
269 lastWay = bestWay;
270 lastWayReverse = bestWayReverse;
271
272 return lastWay;
273 }
274
275 public boolean isLastWayInsideToTheRight() {
276 return lastWayReverse != lastWay.insideToTheRight;
277 }
278
279 public Node getLastWayStartNode() {
280 return lastWayReverse ? lastWay.way.lastNode() : lastWay.way.firstNode();
281 }
282
283 public Node getLastWayEndNode() {
284 return lastWayReverse ? lastWay.way.firstNode() : lastWay.way.lastNode();
285 }
286 }
287
288 /**
289 * Helper storage class for finding findOuterWays
290 * @author viesturs
291 */
292 static class PolygonLevel {
293 public final int level;
294 public final AssembledMultipolygon pol;
295
296 public PolygonLevel(AssembledMultipolygon _pol, int _level) {
297 pol = _pol;
298 level = _level;
299 }
300 }
301
302 // Adds the menu entry, Shortcuts, etc.
303 public JoinAreasAction() {
304 super(tr("Join overlapping Areas"), "joinareas", tr("Joins areas that overlap each other"),
305 Shortcut.registerShortcut("tools:joinareas", tr("Tool: {0}", tr("Join overlapping Areas")),
306 KeyEvent.VK_J, Shortcut.SHIFT), true);
307 }
308
309 /**
310 * Gets called whenever the shortcut is pressed or the menu entry is selected
311 * Checks whether the selected objects are suitable to join and joins them if so
312 */
313 @Override
314 public void actionPerformed(ActionEvent e) {
315 LinkedList<Way> ways = new LinkedList<Way>(Main.main.getCurrentDataSet().getSelectedWays());
316
317 if (ways.isEmpty()) {
318 new Notification(
319 tr("Please select at least one closed way that should be joined."))
320 .setIcon(JOptionPane.INFORMATION_MESSAGE)
321 .show();
322 return;
323 }
324
325 List<Node> allNodes = new ArrayList<Node>();
326 for (Way way : ways) {
327 if (!way.isClosed()) {
328 new Notification(
329 tr("One of the selected ways is not closed and therefore cannot be joined."))
330 .setIcon(JOptionPane.INFORMATION_MESSAGE)
331 .show();
332 return;
333 }
334
335 allNodes.addAll(way.getNodes());
336 }
337
338 // TODO: Only display this warning when nodes outside dataSourceArea are deleted
339 boolean ok = Command.checkAndConfirmOutlyingOperation("joinarea", tr("Join area confirmation"),
340 trn("The selected way has nodes outside of the downloaded data region.",
341 "The selected ways have nodes outside of the downloaded data region.",
342 ways.size()) + "<br/>"
343 + tr("This can lead to nodes being deleted accidentally.") + "<br/>"
344 + tr("Are you really sure to continue?")
345 + tr("Please abort if you are not sure"),
346 tr("The selected area is incomplete. Continue?"),
347 allNodes, null);
348 if(!ok) return;
349
350 //analyze multipolygon relations and collect all areas
351 List<Multipolygon> areas = collectMultipolygons(ways);
352
353 if (areas == null)
354 //too complex multipolygon relations found
355 return;
356
357 if (!testJoin(areas)) {
358 new Notification(
359 tr("No intersection found. Nothing was changed."))
360 .setIcon(JOptionPane.INFORMATION_MESSAGE)
361 .show();
362 return;
363 }
364
365 if (!resolveTagConflicts(areas))
366 return;
367 //user canceled, do nothing.
368
369 try {
370 JoinAreasResult result = joinAreas(areas);
371
372 if (result.hasChanges) {
373
374 List<Way> allWays = new ArrayList<Way>();
375 for (Multipolygon pol : result.polygons) {
376 allWays.add(pol.outerWay);
377 allWays.addAll(pol.innerWays);
378 }
379 DataSet ds = Main.main.getCurrentDataSet();
380 ds.setSelected(allWays);
381 Main.map.mapView.repaint();
382 } else {
383 new Notification(
384 tr("No intersection found. Nothing was changed."))
385 .setIcon(JOptionPane.INFORMATION_MESSAGE)
386 .show();
387 }
388 }
389 catch (UserCancelException exception) {
390 //revert changes
391 //FIXME: this is dirty hack
392 makeCommitsOneAction(tr("Reverting changes"));
393 Main.main.undoRedo.undo();
394 Main.main.undoRedo.redoCommands.clear();
395 }
396 }
397
398 /**
399 * Tests if the areas have some intersections to join.
400 * @param areas Areas to test
401 * @return @{code true} if areas are joinable
402 */
403 private boolean testJoin(List<Multipolygon> areas) {
404 List<Way> allStartingWays = new ArrayList<Way>();
405
406 for (Multipolygon area : areas) {
407 allStartingWays.add(area.outerWay);
408 allStartingWays.addAll(area.innerWays);
409 }
410
411 //find intersection points
412 Set<Node> nodes = Geometry.addIntersections(allStartingWays, true, cmds);
413 return !nodes.isEmpty();
414 }
415
416 /**
417 * Will join two or more overlapping areas
418 * @param areas list of areas to join
419 * @return new area formed.
420 */
421 private JoinAreasResult joinAreas(List<Multipolygon> areas) throws UserCancelException {
422
423 JoinAreasResult result = new JoinAreasResult();
424 result.hasChanges = false;
425
426 List<Way> allStartingWays = new ArrayList<Way>();
427 List<Way> innerStartingWays = new ArrayList<Way>();
428 List<Way> outerStartingWays = new ArrayList<Way>();
429
430 for (Multipolygon area : areas) {
431 outerStartingWays.add(area.outerWay);
432 innerStartingWays.addAll(area.innerWays);
433 }
434
435 allStartingWays.addAll(innerStartingWays);
436 allStartingWays.addAll(outerStartingWays);
437
438 //first remove nodes in the same coordinate
439 boolean removedDuplicates = false;
440 removedDuplicates |= removeDuplicateNodes(allStartingWays);
441
442 if (removedDuplicates) {
443 result.hasChanges = true;
444 commitCommands(marktr("Removed duplicate nodes"));
445 }
446
447 //find intersection points
448 Set<Node> nodes = Geometry.addIntersections(allStartingWays, false, cmds);
449
450 //no intersections, return.
451 if (nodes.isEmpty())
452 return result;
453 commitCommands(marktr("Added node on all intersections"));
454
455 List<RelationRole> relations = new ArrayList<RelationRole>();
456
457 // Remove ways from all relations so ways can be combined/split quietly
458 for (Way way : allStartingWays) {
459 relations.addAll(removeFromAllRelations(way));
460 }
461
462 // Don't warn now, because it will really look corrupted
463 boolean warnAboutRelations = !relations.isEmpty() && allStartingWays.size() > 1;
464
465 List<WayInPolygon> preparedWays = new ArrayList<WayInPolygon>();
466
467 for (Way way : outerStartingWays) {
468 List<Way> splitWays = splitWayOnNodes(way, nodes);
469 preparedWays.addAll(markWayInsideSide(splitWays, false));
470 }
471
472 for (Way way : innerStartingWays) {
473 List<Way> splitWays = splitWayOnNodes(way, nodes);
474 preparedWays.addAll(markWayInsideSide(splitWays, true));
475 }
476
477 // Find boundary ways
478 List<Way> discardedWays = new ArrayList<Way>();
479 List<AssembledPolygon> bounadries = findBoundaryPolygons(preparedWays, discardedWays);
480
481 //find polygons
482 List<AssembledMultipolygon> preparedPolygons = findPolygons(bounadries);
483
484
485 //assemble final polygons
486 List<Multipolygon> polygons = new ArrayList<Multipolygon>();
487 Set<Relation> relationsToDelete = new LinkedHashSet<Relation>();
488
489 for (AssembledMultipolygon pol : preparedPolygons) {
490
491 //create the new ways
492 Multipolygon resultPol = joinPolygon(pol);
493
494 //create multipolygon relation, if necessary.
495 RelationRole ownMultipolygonRelation = addOwnMultigonRelation(resultPol.innerWays, resultPol.outerWay);
496
497 //add back the original relations, merged with our new multipolygon relation
498 fixRelations(relations, resultPol.outerWay, ownMultipolygonRelation, relationsToDelete);
499
500 //strip tags from inner ways
501 //TODO: preserve tags on existing inner ways
502 stripTags(resultPol.innerWays);
503
504 polygons.add(resultPol);
505 }
506
507 commitCommands(marktr("Assemble new polygons"));
508
509 for(Relation rel: relationsToDelete) {
510 cmds.add(new DeleteCommand(rel));
511 }
512
513 commitCommands(marktr("Delete relations"));
514
515 // Delete the discarded inner ways
516 if (!discardedWays.isEmpty()) {
517 Command deleteCmd = DeleteCommand.delete(Main.main.getEditLayer(), discardedWays, true);
518 if (deleteCmd != null) {
519 cmds.add(deleteCmd);
520 commitCommands(marktr("Delete Ways that are not part of an inner multipolygon"));
521 }
522 }
523
524 makeCommitsOneAction(marktr("Joined overlapping areas"));
525
526 if (warnAboutRelations) {
527 new Notification(
528 tr("Some of the ways were part of relations that have been modified.<br>Please verify no errors have been introduced."))
529 .setIcon(JOptionPane.INFORMATION_MESSAGE)
530 .setDuration(Notification.TIME_LONG)
531 .show();
532 }
533
534 result.hasChanges = true;
535 result.polygons = polygons;
536 return result;
537 }
538
539 /**
540 * Checks if tags of two given ways differ, and presents the user a dialog to solve conflicts
541 * @param polygons ways to check
542 * @return {@code true} if all conflicts are resolved, {@code false} if conflicts remain.
543 */
544 private boolean resolveTagConflicts(List<Multipolygon> polygons) {
545
546 List<Way> ways = new ArrayList<Way>();
547
548 for (Multipolygon pol : polygons) {
549 ways.add(pol.outerWay);
550 ways.addAll(pol.innerWays);
551 }
552
553 if (ways.size() < 2) {
554 return true;
555 }
556
557 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
558 try {
559 cmds.addAll(CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, ways));
560 commitCommands(marktr("Fix tag conflicts"));
561 return true;
562 } catch (UserCancelException ex) {
563 return false;
564 }
565 }
566
567 /**
568 * This method removes duplicate points (if any) from the input way.
569 * @param ways the ways to process
570 * @return {@code true} if any changes where made
571 */
572 private boolean removeDuplicateNodes(List<Way> ways) {
573 //TODO: maybe join nodes with JoinNodesAction, rather than reconnect the ways.
574
575 Map<Node, Node> nodeMap = new TreeMap<Node, Node>(new NodePositionComparator());
576 int totalNodesRemoved = 0;
577
578 for (Way way : ways) {
579 if (way.getNodes().size() < 2) {
580 continue;
581 }
582
583 int nodesRemoved = 0;
584 List<Node> newNodes = new ArrayList<Node>();
585 Node prevNode = null;
586
587 for (Node node : way.getNodes()) {
588 if (!nodeMap.containsKey(node)) {
589 //new node
590 nodeMap.put(node, node);
591
592 //avoid duplicate nodes
593 if (prevNode != node) {
594 newNodes.add(node);
595 } else {
596 nodesRemoved ++;
597 }
598 } else {
599 //node with same coordinates already exists, substitute with existing node
600 Node representator = nodeMap.get(node);
601
602 if (representator != node) {
603 nodesRemoved ++;
604 }
605
606 //avoid duplicate node
607 if (prevNode != representator) {
608 newNodes.add(representator);
609 }
610 }
611 prevNode = node;
612 }
613
614 if (nodesRemoved > 0) {
615
616 if (newNodes.size() == 1) { //all nodes in the same coordinate - add one more node, to have closed way.
617 newNodes.add(newNodes.get(0));
618 }
619
620 Way newWay=new Way(way);
621 newWay.setNodes(newNodes);
622 cmds.add(new ChangeCommand(way, newWay));
623 totalNodesRemoved += nodesRemoved;
624 }
625 }
626
627 return totalNodesRemoved > 0;
628 }
629
630 /**
631 * Commits the command list with a description
632 * @param description The description of what the commands do
633 */
634 private void commitCommands(String description) {
635 switch(cmds.size()) {
636 case 0:
637 return;
638 case 1:
639 Main.main.undoRedo.add(cmds.getFirst());
640 break;
641 default:
642 Command c = new SequenceCommand(tr(description), cmds);
643 Main.main.undoRedo.add(c);
644 break;
645 }
646
647 cmds.clear();
648 cmdsCount++;
649 }
650
651 /**
652 * This method analyzes the way and assigns each part what direction polygon "inside" is.
653 * @param parts the split parts of the way
654 * @param isInner - if true, reverts the direction (for multipolygon islands)
655 * @return list of parts, marked with the inside orientation.
656 */
657 private List<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) {
658
659 List<WayInPolygon> result = new ArrayList<WayInPolygon>();
660
661 //prepare prev and next maps
662 Map<Way, Way> nextWayMap = new HashMap<Way, Way>();
663 Map<Way, Way> prevWayMap = new HashMap<Way, Way>();
664
665 for (int pos = 0; pos < parts.size(); pos ++) {
666
667 if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode()))
668 throw new RuntimeException("Way not circular");
669
670 nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size()));
671 prevWayMap.put(parts.get(pos), parts.get((pos + parts.size() - 1) % parts.size()));
672 }
673
674 //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?)
675 Way topWay = null;
676 Node topNode = null;
677 int topIndex = 0;
678 double minY = Double.POSITIVE_INFINITY;
679
680 for (Way way : parts) {
681 for (int pos = 0; pos < way.getNodesCount(); pos ++) {
682 Node node = way.getNode(pos);
683
684 if (node.getEastNorth().getY() < minY) {
685 minY = node.getEastNorth().getY();
686 topWay = way;
687 topNode = node;
688 topIndex = pos;
689 }
690 }
691 }
692
693 //get the upper way and it's orientation.
694
695 boolean wayClockwise; // orientation of the top way.
696
697 if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) {
698 Node headNode = null; // the node at junction
699 Node prevNode = null; // last node from previous path
700 wayClockwise = false;
701
702 //node is in split point - find the outermost way from this point
703
704 headNode = topNode;
705 //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths.
706 prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5));
707
708 topWay = null;
709 wayClockwise = false;
710 Node bestWayNextNode = null;
711
712 for (Way way : parts) {
713 if (way.firstNode().equals(headNode)) {
714 Node nextNode = way.getNode(1);
715
716 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
717 //the new way is better
718 topWay = way;
719 wayClockwise = true;
720 bestWayNextNode = nextNode;
721 }
722 }
723
724 if (way.lastNode().equals(headNode)) {
725 //end adjacent to headNode
726 Node nextNode = way.getNode(way.getNodesCount() - 2);
727
728 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) {
729 //the new way is better
730 topWay = way;
731 wayClockwise = false;
732 bestWayNextNode = nextNode;
733 }
734 }
735 }
736 } else {
737 //node is inside way - pick the clockwise going end.
738 Node prev = topWay.getNode(topIndex - 1);
739 Node next = topWay.getNode(topIndex + 1);
740
741 //there will be no parallel segments in the middle of way, so all fine.
742 wayClockwise = Geometry.angleIsClockwise(prev, topNode, next);
743 }
744
745 Way curWay = topWay;
746 boolean curWayInsideToTheRight = wayClockwise ^ isInner;
747
748 //iterate till full circle is reached
749 while (true) {
750
751 //add cur way
752 WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight);
753 result.add(resultWay);
754
755 //process next way
756 Way nextWay = nextWayMap.get(curWay);
757 Node prevNode = curWay.getNode(curWay.getNodesCount() - 2);
758 Node headNode = curWay.lastNode();
759 Node nextNode = nextWay.getNode(1);
760
761 if (nextWay == topWay) {
762 //full loop traversed - all done.
763 break;
764 }
765
766 //find intersecting segments
767 // the intersections will look like this:
768 //
769 // ^
770 // |
771 // X wayBNode
772 // |
773 // wayB |
774 // |
775 // curWay | nextWay
776 //----X----------------->X----------------------X---->
777 // prevNode ^headNode nextNode
778 // |
779 // |
780 // wayA |
781 // |
782 // X wayANode
783 // |
784
785 int intersectionCount = 0;
786
787 for (Way wayA : parts) {
788
789 if (wayA == curWay) {
790 continue;
791 }
792
793 if (wayA.lastNode().equals(headNode)) {
794
795 Way wayB = nextWayMap.get(wayA);
796
797 //test if wayA is opposite wayB relative to curWay and nextWay
798
799 Node wayANode = wayA.getNode(wayA.getNodesCount() - 2);
800 Node wayBNode = wayB.getNode(1);
801
802 boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode);
803 boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode);
804
805 if (wayAToTheRight != wayBToTheRight) {
806 intersectionCount ++;
807 }
808 }
809 }
810
811 //if odd number of crossings, invert orientation
812 if (intersectionCount % 2 != 0) {
813 curWayInsideToTheRight = !curWayInsideToTheRight;
814 }
815
816 curWay = nextWay;
817 }
818
819 return result;
820 }
821
822 /**
823 * This is a method splits way into smaller parts, using the prepared nodes list as split points.
824 * Uses SplitWayAction.splitWay for the heavy lifting.
825 * @return list of split ways (or original ways if no splitting is done).
826 */
827 private List<Way> splitWayOnNodes(Way way, Set<Node> nodes) {
828
829 List<Way> result = new ArrayList<Way>();
830 List<List<Node>> chunks = buildNodeChunks(way, nodes);
831
832 if (chunks.size() > 1) {
833 SplitWayResult split = SplitWayAction.splitWay(Main.main.getEditLayer(), way, chunks, Collections.<OsmPrimitive>emptyList());
834
835 //execute the command, we need the results
836 cmds.add(split.getCommand());
837 commitCommands(marktr("Split ways into fragments"));
838
839 result.add(split.getOriginalWay());
840 result.addAll(split.getNewWays());
841 } else {
842 //nothing to split
843 result.add(way);
844 }
845
846 return result;
847 }
848
849 /**
850 * Simple chunking version. Does not care about circular ways and result being
851 * proper, we will glue it all back together later on.
852 * @param way the way to chunk
853 * @param splitNodes the places where to cut.
854 * @return list of node paths to produce.
855 */
856 private List<List<Node>> buildNodeChunks(Way way, Collection<Node> splitNodes) {
857 List<List<Node>> result = new ArrayList<List<Node>>();
858 List<Node> curList = new ArrayList<Node>();
859
860 for (Node node : way.getNodes()) {
861 curList.add(node);
862 if (curList.size() > 1 && splitNodes.contains(node)) {
863 result.add(curList);
864 curList = new ArrayList<Node>();
865 curList.add(node);
866 }
867 }
868
869 if (curList.size() > 1) {
870 result.add(curList);
871 }
872
873 return result;
874 }
875
876
877 /**
878 * This method finds which ways are outer and which are inner.
879 * @param boundaries list of joined boundaries to search in
880 * @return outer ways
881 */
882 private List<AssembledMultipolygon> findPolygons(Collection<AssembledPolygon> boundaries) {
883
884 List<PolygonLevel> list = findOuterWaysImpl(0, boundaries);
885 List<AssembledMultipolygon> result = new ArrayList<AssembledMultipolygon>();
886
887 //take every other level
888 for (PolygonLevel pol : list) {
889 if (pol.level % 2 == 0) {
890 result.add(pol.pol);
891 }
892 }
893
894 return result;
895 }
896
897 /**
898 * Collects outer way and corresponding inner ways from all boundaries.
899 * @param level depth level
900 * @param boundaryWays
901 * @return the outermostWay.
902 */
903 private List<PolygonLevel> findOuterWaysImpl(int level, Collection<AssembledPolygon> boundaryWays) {
904
905 //TODO: bad performance for deep nestings...
906 List<PolygonLevel> result = new ArrayList<PolygonLevel>();
907
908 for (AssembledPolygon outerWay : boundaryWays) {
909
910 boolean outerGood = true;
911 List<AssembledPolygon> innerCandidates = new ArrayList<AssembledPolygon>();
912
913 for (AssembledPolygon innerWay : boundaryWays) {
914 if (innerWay == outerWay) {
915 continue;
916 }
917
918 if (wayInsideWay(outerWay, innerWay)) {
919 outerGood = false;
920 break;
921 } else if (wayInsideWay(innerWay, outerWay)) {
922 innerCandidates.add(innerWay);
923 }
924 }
925
926 if (!outerGood) {
927 continue;
928 }
929
930 //add new outer polygon
931 AssembledMultipolygon pol = new AssembledMultipolygon(outerWay);
932 PolygonLevel polLev = new PolygonLevel(pol, level);
933
934 //process inner ways
935 if (!innerCandidates.isEmpty()) {
936 List<PolygonLevel> innerList = findOuterWaysImpl(level + 1, innerCandidates);
937 result.addAll(innerList);
938
939 for (PolygonLevel pl : innerList) {
940 if (pl.level == level + 1) {
941 pol.innerWays.add(pl.pol.outerWay);
942 }
943 }
944 }
945
946 result.add(polLev);
947 }
948
949 return result;
950 }
951
952 /**
953 * Finds all ways that form inner or outer boundaries.
954 * @param multigonWays A list of (splitted) ways that form a multigon and share common end nodes on intersections.
955 * @param discardedResult this list is filled with ways that are to be discarded
956 * @return A list of ways that form the outer and inner boundaries of the multigon.
957 */
958 public static List<AssembledPolygon> findBoundaryPolygons(Collection<WayInPolygon> multigonWays, List<Way> discardedResult) {
959 //first find all discardable ways, by getting outer shells.
960 //this will produce incorrect boundaries in some cases, but second pass will fix it.
961
962 List<WayInPolygon> discardedWays = new ArrayList<WayInPolygon>();
963 Set<WayInPolygon> processedWays = new HashSet<WayInPolygon>();
964 WayTraverser traverser = new WayTraverser(multigonWays);
965
966 for (WayInPolygon startWay : multigonWays) {
967 if (processedWays.contains(startWay)) {
968 continue;
969 }
970
971 traverser.startNewWay(startWay);
972
973 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
974 WayInPolygon lastWay = startWay;
975
976 while (true) {
977 boundary.add(lastWay);
978
979 WayInPolygon bestWay = traverser.advanceNextLeftmostWay();
980 boolean wayInsideToTheRight = bestWay == null ? false : traverser.isLastWayInsideToTheRight();
981
982 if (bestWay == null || processedWays.contains(bestWay) || !wayInsideToTheRight) {
983 //bad segment chain - proceed to discard it
984 lastWay = null;
985 break;
986 } else if (boundary.contains(bestWay)) {
987 //traversed way found - close the way
988 lastWay = bestWay;
989 break;
990 } else {
991 //proceed to next segment
992 lastWay = bestWay;
993 }
994 }
995
996 if (lastWay != null) {
997 //way good
998 processedWays.addAll(boundary);
999
1000 //remove junk segments at the start
1001 while (boundary.get(0) != lastWay) {
1002 discardedWays.add(boundary.get(0));
1003 boundary.remove(0);
1004 }
1005 } else {
1006 //way bad
1007 discardedWays.addAll(boundary);
1008 processedWays.addAll(boundary);
1009 }
1010 }
1011
1012 //now we have removed junk segments, collect the real result ways
1013
1014 traverser.removeWays(discardedWays);
1015
1016 List<AssembledPolygon> result = new ArrayList<AssembledPolygon>();
1017
1018 while (traverser.hasWays()) {
1019
1020 WayInPolygon startWay = traverser.startNewWay();
1021 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
1022 WayInPolygon curWay = startWay;
1023
1024 do {
1025 boundary.add(curWay);
1026 curWay = traverser.advanceNextRightmostWay();
1027
1028 //should not happen
1029 if (curWay == null || !traverser.isLastWayInsideToTheRight())
1030 throw new RuntimeException("Join areas internal error.");
1031
1032 } while (curWay != startWay);
1033
1034 //build result
1035 traverser.removeWays(boundary);
1036 result.add(new AssembledPolygon(boundary));
1037 }
1038
1039 for (WayInPolygon way : discardedWays) {
1040 discardedResult.add(way.way);
1041 }
1042
1043 //split inner polygons that have several touching parts.
1044 result = fixTouchingPolygons(result);
1045
1046 return result;
1047 }
1048
1049 /**
1050 * This method checks if polygons have several touching parts and splits them in several polygons.
1051 * @param polygons the polygons to process.
1052 */
1053 public static List<AssembledPolygon> fixTouchingPolygons(List<AssembledPolygon> polygons)
1054 {
1055 List<AssembledPolygon> newPolygons = new ArrayList<AssembledPolygon>();
1056
1057 for (AssembledPolygon innerPart : polygons) {
1058 WayTraverser traverser = new WayTraverser(innerPart.ways);
1059
1060 while (traverser.hasWays()) {
1061
1062 WayInPolygon startWay = traverser.startNewWay();
1063 List<WayInPolygon> boundary = new ArrayList<WayInPolygon>();
1064 WayInPolygon curWay = startWay;
1065
1066 Node startNode = traverser.getLastWayStartNode();
1067 boundary.add(curWay);
1068
1069 while (startNode != traverser.getLastWayEndNode()) {
1070 curWay = traverser.advanceNextLeftmostWay();
1071 boundary.add(curWay);
1072
1073 //should not happen
1074 if (curWay == null || !traverser.isLastWayInsideToTheRight())
1075 throw new RuntimeException("Join areas internal error.");
1076 }
1077
1078 //build result
1079 traverser.removeWays(boundary);
1080 newPolygons.add(new AssembledPolygon(boundary));
1081 }
1082 }
1083
1084 return newPolygons;
1085 }
1086
1087 /**
1088 * Tests if way is inside other way
1089 * @param outside outer polygon description
1090 * @param inside inner polygon description
1091 * @return {@code true} if inner is inside outer
1092 */
1093 public static boolean wayInsideWay(AssembledPolygon inside, AssembledPolygon outside) {
1094 Set<Node> outsideNodes = new HashSet<Node>(outside.getNodes());
1095 List<Node> insideNodes = inside.getNodes();
1096
1097 for (Node insideNode : insideNodes) {
1098
1099 if (!outsideNodes.contains(insideNode))
1100 //simply test the one node
1101 return Geometry.nodeInsidePolygon(insideNode, outside.getNodes());
1102 }
1103
1104 //all nodes shared.
1105 return false;
1106 }
1107
1108 /**
1109 * Joins the lists of ways.
1110 * @param polygon The list of outer ways that belong to that multigon.
1111 * @return The newly created outer way
1112 */
1113 private Multipolygon joinPolygon(AssembledMultipolygon polygon) throws UserCancelException {
1114 Multipolygon result = new Multipolygon(joinWays(polygon.outerWay.ways));
1115
1116 for (AssembledPolygon pol : polygon.innerWays) {
1117 result.innerWays.add(joinWays(pol.ways));
1118 }
1119
1120 return result;
1121 }
1122
1123 /**
1124 * Joins the outer ways and deletes all short ways that can't be part of a multipolygon anyway.
1125 * @param ways The list of outer ways that belong to that multigon.
1126 * @return The newly created outer way
1127 */
1128 private Way joinWays(List<WayInPolygon> ways) throws UserCancelException {
1129
1130 //leave original orientation, if all paths are reverse.
1131 boolean allReverse = true;
1132 for (WayInPolygon way : ways) {
1133 allReverse &= !way.insideToTheRight;
1134 }
1135
1136 if (allReverse) {
1137 for (WayInPolygon way : ways) {
1138 way.insideToTheRight = !way.insideToTheRight;
1139 }
1140 }
1141
1142 Way joinedWay = joinOrientedWays(ways);
1143
1144 //should not happen
1145 if (joinedWay == null || !joinedWay.isClosed())
1146 throw new RuntimeException("Join areas internal error.");
1147
1148 return joinedWay;
1149 }
1150
1151 /**
1152 * Joins a list of ways (using CombineWayAction and ReverseWayAction as specified in WayInPath)
1153 * @param ways The list of ways to join and reverse
1154 * @return The newly created way
1155 */
1156 private Way joinOrientedWays(List<WayInPolygon> ways) throws UserCancelException{
1157 if (ways.size() < 2)
1158 return ways.get(0).way;
1159
1160 // This will turn ways so all of them point in the same direction and CombineAction won't bug
1161 // the user about this.
1162
1163 //TODO: ReverseWay and Combine way are really slow and we use them a lot here. This slows down large joins.
1164 List<Way> actionWays = new ArrayList<Way>(ways.size());
1165
1166 for (WayInPolygon way : ways) {
1167 actionWays.add(way.way);
1168
1169 if (!way.insideToTheRight) {
1170 ReverseWayResult res = ReverseWayAction.reverseWay(way.way);
1171 Main.main.undoRedo.add(res.getReverseCommand());
1172 cmdsCount++;
1173 }
1174 }
1175
1176 Pair<Way, Command> result = CombineWayAction.combineWaysWorker(actionWays);
1177
1178 Main.main.undoRedo.add(result.b);
1179 cmdsCount ++;
1180
1181 return result.a;
1182 }
1183
1184 /**
1185 * This method analyzes multipolygon relationships of given ways and collects addition inner ways to consider.
1186 * @param selectedWays the selected ways
1187 * @return list of polygons, or null if too complex relation encountered.
1188 */
1189 private List<Multipolygon> collectMultipolygons(List<Way> selectedWays) {
1190
1191 List<Multipolygon> result = new ArrayList<Multipolygon>();
1192
1193 //prepare the lists, to minimize memory allocation.
1194 List<Way> outerWays = new ArrayList<Way>();
1195 List<Way> innerWays = new ArrayList<Way>();
1196
1197 Set<Way> processedOuterWays = new LinkedHashSet<Way>();
1198 Set<Way> processedInnerWays = new LinkedHashSet<Way>();
1199
1200 for (Relation r : OsmPrimitive.getParentRelations(selectedWays)) {
1201 if (r.isDeleted() || !r.isMultipolygon()) {
1202 continue;
1203 }
1204
1205 boolean hasKnownOuter = false;
1206 outerWays.clear();
1207 innerWays.clear();
1208
1209 for (RelationMember rm : r.getMembers()) {
1210 if (rm.getRole().equalsIgnoreCase("outer")) {
1211 outerWays.add(rm.getWay());
1212 hasKnownOuter |= selectedWays.contains(rm.getWay());
1213 }
1214 else if (rm.getRole().equalsIgnoreCase("inner")) {
1215 innerWays.add(rm.getWay());
1216 }
1217 }
1218
1219 if (!hasKnownOuter) {
1220 continue;
1221 }
1222
1223 if (outerWays.size() > 1) {
1224 new Notification(
1225 tr("Sorry. Cannot handle multipolygon relations with multiple outer ways."))
1226 .setIcon(JOptionPane.INFORMATION_MESSAGE)
1227 .show();
1228 return null;
1229 }
1230
1231 Way outerWay = outerWays.get(0);
1232
1233 //retain only selected inner ways
1234 innerWays.retainAll(selectedWays);
1235
1236 if (processedOuterWays.contains(outerWay)) {
1237 new Notification(
1238 tr("Sorry. Cannot handle way that is outer in multiple multipolygon relations."))
1239 .setIcon(JOptionPane.INFORMATION_MESSAGE)
1240 .show();
1241 return null;
1242 }
1243
1244 if (processedInnerWays.contains(outerWay)) {
1245 new Notification(
1246 tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."))
1247 .setIcon(JOptionPane.INFORMATION_MESSAGE)
1248 .show();
1249 return null;
1250 }
1251
1252 for (Way way :innerWays)
1253 {
1254 if (processedOuterWays.contains(way)) {
1255 new Notification(
1256 tr("Sorry. Cannot handle way that is both inner and outer in multipolygon relations."))
1257 .setIcon(JOptionPane.INFORMATION_MESSAGE)
1258 .show();
1259 return null;
1260 }
1261
1262 if (processedInnerWays.contains(way)) {
1263 new Notification(
1264 tr("Sorry. Cannot handle way that is inner in multiple multipolygon relations."))
1265 .setIcon(JOptionPane.INFORMATION_MESSAGE)
1266 .show();
1267 return null;
1268 }
1269 }
1270
1271 processedOuterWays.add(outerWay);
1272 processedInnerWays.addAll(innerWays);
1273
1274 Multipolygon pol = new Multipolygon(outerWay);
1275 pol.innerWays.addAll(innerWays);
1276
1277 result.add(pol);
1278 }
1279
1280 //add remaining ways, not in relations
1281 for (Way way : selectedWays) {
1282 if (processedOuterWays.contains(way) || processedInnerWays.contains(way)) {
1283 continue;
1284 }
1285
1286 result.add(new Multipolygon(way));
1287 }
1288
1289 return result;
1290 }
1291
1292 /**
1293 * Will add own multipolygon relation to the "previously existing" relations. Fixup is done by fixRelations
1294 * @param inner List of already closed inner ways
1295 * @param outer The outer way
1296 * @return The list of relation with roles to add own relation to
1297 */
1298 private RelationRole addOwnMultigonRelation(Collection<Way> inner, Way outer) {
1299 if (inner.isEmpty()) return null;
1300 // Create new multipolygon relation and add all inner ways to it
1301 Relation newRel = new Relation();
1302 newRel.put("type", "multipolygon");
1303 for (Way w : inner) {
1304 newRel.addMember(new RelationMember("inner", w));
1305 }
1306 cmds.add(new AddCommand(newRel));
1307
1308 // We don't add outer to the relation because it will be handed to fixRelations()
1309 // which will then do the remaining work.
1310 return new RelationRole(newRel, "outer");
1311 }
1312
1313 /**
1314 * Removes a given OsmPrimitive from all relations
1315 * @param osm Element to remove from all relations
1316 * @return List of relations with roles the primitives was part of
1317 */
1318 private List<RelationRole> removeFromAllRelations(OsmPrimitive osm) {
1319 List<RelationRole> result = new ArrayList<RelationRole>();
1320
1321 for (Relation r : Main.main.getCurrentDataSet().getRelations()) {
1322 if (r.isDeleted()) {
1323 continue;
1324 }
1325 for (RelationMember rm : r.getMembers()) {
1326 if (rm.getMember() != osm) {
1327 continue;
1328 }
1329
1330 Relation newRel = new Relation(r);
1331 List<RelationMember> members = newRel.getMembers();
1332 members.remove(rm);
1333 newRel.setMembers(members);
1334
1335 cmds.add(new ChangeCommand(r, newRel));
1336 RelationRole saverel = new RelationRole(r, rm.getRole());
1337 if (!result.contains(saverel)) {
1338 result.add(saverel);
1339 }
1340 break;
1341 }
1342 }
1343
1344 commitCommands(marktr("Removed Element from Relations"));
1345 return result;
1346 }
1347
1348 /**
1349 * Adds the previously removed relations again to the outer way. If there are multiple multipolygon
1350 * relations where the joined areas were in "outer" role a new relation is created instead with all
1351 * members of both. This function depends on multigon relations to be valid already, it won't fix them.
1352 * @param rels List of relations with roles the (original) ways were part of
1353 * @param outer The newly created outer area/way
1354 * @param ownMultipol elements to directly add as outer
1355 * @param relationsToDelete set of relations to delete.
1356 */
1357 private void fixRelations(List<RelationRole> rels, Way outer, RelationRole ownMultipol, Set<Relation> relationsToDelete) {
1358 List<RelationRole> multiouters = new ArrayList<RelationRole>();
1359
1360 if (ownMultipol != null) {
1361 multiouters.add(ownMultipol);
1362 }
1363
1364 for (RelationRole r : rels) {
1365 if (r.rel.isMultipolygon() && r.role.equalsIgnoreCase("outer")) {
1366 multiouters.add(r);
1367 continue;
1368 }
1369 // Add it back!
1370 Relation newRel = new Relation(r.rel);
1371 newRel.addMember(new RelationMember(r.role, outer));
1372 cmds.add(new ChangeCommand(r.rel, newRel));
1373 }
1374
1375 Relation newRel;
1376 switch (multiouters.size()) {
1377 case 0:
1378 return;
1379 case 1:
1380 // Found only one to be part of a multipolygon relation, so just add it back as well
1381 newRel = new Relation(multiouters.get(0).rel);
1382 newRel.addMember(new RelationMember(multiouters.get(0).role, outer));
1383 cmds.add(new ChangeCommand(multiouters.get(0).rel, newRel));
1384 return;
1385 default:
1386 // Create a new relation with all previous members and (Way)outer as outer.
1387 newRel = new Relation();
1388 for (RelationRole r : multiouters) {
1389 // Add members
1390 for (RelationMember rm : r.rel.getMembers())
1391 if (!newRel.getMembers().contains(rm)) {
1392 newRel.addMember(rm);
1393 }
1394 // Add tags
1395 for (String key : r.rel.keySet()) {
1396 newRel.put(key, r.rel.get(key));
1397 }
1398 // Delete old relation
1399 relationsToDelete.add(r.rel);
1400 }
1401 newRel.addMember(new RelationMember("outer", outer));
1402 cmds.add(new AddCommand(newRel));
1403 }
1404 }
1405
1406 /**
1407 * Remove all tags from the all the way
1408 * @param ways The List of Ways to remove all tags from
1409 */
1410 private void stripTags(Collection<Way> ways) {
1411 for (Way w : ways) {
1412 stripTags(w);
1413 }
1414 /* I18N: current action printed in status display */
1415 commitCommands(marktr("Remove tags from inner ways"));
1416 }
1417
1418 /**
1419 * Remove all tags from the way
1420 * @param x The Way to remove all tags from
1421 */
1422 private void stripTags(Way x) {
1423 Way y = new Way(x);
1424 for (String key : x.keySet()) {
1425 y.remove(key);
1426 }
1427 cmds.add(new ChangeCommand(x, y));
1428 }
1429
1430 /**
1431 * Takes the last cmdsCount actions back and combines them into a single action
1432 * (for when the user wants to undo the join action)
1433 * @param message The commit message to display
1434 */
1435 private void makeCommitsOneAction(String message) {
1436 UndoRedoHandler ur = Main.main.undoRedo;
1437 cmds.clear();
1438 int i = Math.max(ur.commands.size() - cmdsCount, 0);
1439 for (; i < ur.commands.size(); i++) {
1440 cmds.add(ur.commands.get(i));
1441 }
1442
1443 for (i = 0; i < cmds.size(); i++) {
1444 ur.undo();
1445 }
1446
1447 commitCommands(message == null ? marktr("Join Areas Function") : message);
1448 cmdsCount = 0;
1449 }
1450
1451 @Override
1452 protected void updateEnabledState() {
1453 if (getCurrentDataSet() == null) {
1454 setEnabled(false);
1455 } else {
1456 updateEnabledState(getCurrentDataSet().getSelected());
1457 }
1458 }
1459
1460 @Override
1461 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
1462 setEnabled(selection != null && !selection.isEmpty());
1463 }
1464}
Note: See TracBrowser for help on using the repository browser.