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

Last change on this file since 6394 was 6380, checked in by Don-vip, 10 years ago

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