- Timestamp:
- 2017-03-13T19:35:13+01:00 (7 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java
r11611 r11729 11 11 import java.util.Collection; 12 12 import java.util.Collections; 13 import java.util.HashMap; 13 import java.util.Comparator; 14 import java.util.EnumSet; 14 15 import java.util.HashSet; 15 16 import java.util.LinkedHashSet; … … 18 19 import java.util.Map; 19 20 import java.util.Objects; 21 import java.util.Optional; 20 22 import java.util.Set; 21 23 import java.util.TreeMap; 24 import java.util.function.BiConsumer; 25 import java.util.function.BinaryOperator; 26 import java.util.function.Function; 27 import java.util.function.Supplier; 28 import java.util.function.ToDoubleFunction; 29 import java.util.stream.Collector; 30 import java.util.stream.Collectors; 31 import java.util.stream.Stream; 22 32 23 33 import javax.swing.JOptionPane; … … 50 60 import org.openstreetmap.josm.tools.UserCancelException; 51 61 import org.openstreetmap.josm.tools.Utils; 62 import org.openstreetmap.josm.tools.bugreport.BugReport; 52 63 53 64 /** … … 180 191 return insideToTheRight == that.insideToTheRight && 181 192 Objects.equals(way, that.way); 193 } 194 195 @Override 196 public String toString() { 197 return "WayInPolygon [way=" + way + ", insideToTheRight=" + insideToTheRight + "]"; 182 198 } 183 199 } … … 242 258 243 259 /** Set of {@link WayInPolygon} to be joined by walk algorithm */ 244 private final Set<WayInPolygon> availableWays;260 private final List<WayInPolygon> availableWays; 245 261 /** Current state of walk algorithm */ 246 262 private WayInPolygon lastWay; … … 252 268 */ 253 269 WayTraverser(Collection<WayInPolygon> ways) { 254 availableWays = new HashSet<>(ways);270 availableWays = new ArrayList<>(ways); 255 271 lastWay = null; 256 272 } … … 344 360 double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(), 345 361 headNode.getEastNorth().north() - prevNode.getEastNorth().north()); 346 double bestAngle = 0; 347 348 //find best next way 349 WayInPolygon bestWay = null; 350 boolean bestWayReverse = false; 351 352 for (WayInPolygon way : availableWays) { 353 Node nextNode; 354 355 // Check for a connected way 356 if (way.way.firstNode().equals(headNode) && way.insideToTheRight) { 357 nextNode = way.way.getNode(1); 358 } else if (way.way.lastNode().equals(headNode) && !way.insideToTheRight) { 359 nextNode = way.way.getNode(way.way.getNodesCount() - 2); 360 } else { 361 continue; 362 } 363 364 if (nextNode == prevNode) { 365 // go back 366 lastWay = way; 367 lastWayReverse = !way.insideToTheRight; 368 return lastWay; 369 } 370 371 double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(), 372 nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle; 373 if (angle > Math.PI) 374 angle -= 2*Math.PI; 375 if (angle <= -Math.PI) 376 angle += 2*Math.PI; 377 378 // Now we have a valid candidate way, is it better than the previous one ? 379 if (bestWay == null || angle > bestAngle) { 380 //the new way is better 381 bestWay = way; 382 bestWayReverse = !way.insideToTheRight; 383 bestAngle = angle; 384 } 385 } 386 387 lastWay = bestWay; 388 lastWayReverse = bestWayReverse; 362 363 // Pairs of (way, nextNode) 364 lastWay = Stream.concat( 365 availableWays.stream() 366 .filter(way -> way.way.firstNode().equals(headNode) && way.insideToTheRight) 367 .map(way -> new Pair<>(way, way.way.getNode(1))), 368 availableWays.stream() 369 .filter(way -> way.way.lastNode().equals(headNode) && !way.insideToTheRight) 370 .map(way -> new Pair<>(way, way.way.getNode(way.way.getNodesCount() - 2)))) 371 372 // now find the way with the best angle 373 .min(Comparator.comparingDouble(wayAndNext -> { 374 Node nextNode = wayAndNext.b; 375 if (nextNode == prevNode) { 376 // we always prefer going back. 377 return Double.POSITIVE_INFINITY; 378 } 379 double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(), 380 nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle; 381 if (angle > Math.PI) 382 angle -= 2*Math.PI; 383 if (angle <= -Math.PI) 384 angle += 2*Math.PI; 385 return angle; 386 })).map(wayAndNext -> wayAndNext.a).orElse(null); 387 lastWayReverse = lastWay != null && !lastWay.insideToTheRight; 389 388 return lastWay; 390 389 } … … 428 427 429 428 return comingToHead ? mostLeft : null; 429 } 430 431 @Override 432 public String toString() { 433 return "WayTraverser [availableWays=" + availableWays + ", lastWay=" + lastWay + ", lastWayReverse=" 434 + lastWayReverse + "]"; 430 435 } 431 436 } … … 591 596 } 592 597 598 private static class DuplicateWayCollectorAccu { 599 private List<Way> currentWays = new ArrayList<>(); 600 private List<Way> duplicatesFound = new ArrayList<>(); 601 602 private void add(Way way) { 603 List<Node> wayNodes = way.getNodes(); 604 List<Node> wayNodesReversed = way.getNodes(); 605 Collections.reverse(wayNodesReversed); 606 Optional<Way> duplicate = currentWays.stream() 607 .filter(current -> current.getNodes().equals(wayNodes) || current.getNodes().equals(wayNodesReversed)) 608 .findFirst(); 609 if (duplicate.isPresent()) { 610 currentWays.remove(duplicate.get()); 611 duplicatesFound.add(duplicate.get()); 612 duplicatesFound.add(way); 613 } else { 614 currentWays.add(way); 615 } 616 } 617 618 private DuplicateWayCollectorAccu combine(DuplicateWayCollectorAccu a2) { 619 duplicatesFound.addAll(a2.duplicatesFound); 620 a2.currentWays.forEach(this::add); 621 return this; 622 } 623 } 624 625 /** 626 * A collector that collects to a list of duplicated way pairs. 627 * 628 * It does not scale well (O(n²)), but the data base should be small enough to make this efficient. 629 * 630 * @author Michael Zangl 631 */ 632 private static class DuplicateWayCollector implements Collector<Way, DuplicateWayCollectorAccu, List<Way>> { 633 @Override 634 public Supplier<DuplicateWayCollectorAccu> supplier() { 635 return DuplicateWayCollectorAccu::new; 636 } 637 638 @Override 639 public BiConsumer<DuplicateWayCollectorAccu, Way> accumulator() { 640 return DuplicateWayCollectorAccu::add; 641 } 642 643 @Override 644 public BinaryOperator<DuplicateWayCollectorAccu> combiner() { 645 return DuplicateWayCollectorAccu::combine; 646 } 647 648 @Override 649 public Function<DuplicateWayCollectorAccu, List<Way>> finisher() { 650 return a -> a.duplicatesFound; 651 } 652 653 @Override 654 public Set<Collector.Characteristics> characteristics() { 655 return EnumSet.of(Collector.Characteristics.UNORDERED); 656 } 657 658 } 659 593 660 /** 594 661 * Will join two or more overlapping areas … … 642 709 List<WayInPolygon> preparedWays = new ArrayList<>(); 643 710 644 for (Way way : outerStartingWays) { 645 List<Way> splitWays = splitWayOnNodes(way, nodes); 646 preparedWays.addAll(markWayInsideSide(splitWays, false)); 647 } 648 649 for (Way way : innerStartingWays) { 650 List<Way> splitWays = splitWayOnNodes(way, nodes); 651 preparedWays.addAll(markWayInsideSide(splitWays, true)); 652 } 711 // Split the nodes on the 712 List<Way> splitOuterWays = outerStartingWays.stream() 713 .flatMap(way -> splitWayOnNodes(way, nodes).stream()).collect(Collectors.toList()); 714 List<Way> splitInnerWays = innerStartingWays.stream() 715 .flatMap(way -> splitWayOnNodes(way, nodes).stream()).collect(Collectors.toList()); 716 717 // remove duplicate ways (A->B->C and C->B->A) 718 List<Way> duplicates = Stream.concat(splitOuterWays.stream(), splitInnerWays.stream()).collect(new DuplicateWayCollector()); 719 720 splitOuterWays.removeAll(duplicates); 721 splitInnerWays.removeAll(duplicates); 722 723 preparedWays.addAll(markWayInsideSide(splitOuterWays, false)); 724 preparedWays.addAll(markWayInsideSide(splitInnerWays, true)); 653 725 654 726 // Find boundary ways 655 List<Way> discardedWays = new ArrayList<>( );727 List<Way> discardedWays = new ArrayList<>(duplicates); 656 728 List<AssembledPolygon> boundaries = findBoundaryPolygons(preparedWays, discardedWays); 657 729 … … 839 911 */ 840 912 private static List<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) { 841 842 //prepare next map 843 Map<Way, Way> nextWayMap = new HashMap<>(); 844 845 for (int pos = 0; pos < parts.size(); pos++) { 846 847 if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode())) 848 throw new IllegalArgumentException("Way not circular"); 849 850 nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size())); 851 } 852 853 //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?) 854 Way topWay = null; 855 Node topNode = null; 856 int topIndex = 0; 857 double minY = Double.POSITIVE_INFINITY; 858 859 for (Way way : parts) { 860 for (int pos = 0; pos < way.getNodesCount(); pos++) { 861 Node node = way.getNode(pos); 862 863 if (node.getEastNorth().getY() < minY) { 864 minY = node.getEastNorth().getY(); 865 topWay = way; 866 topNode = node; 867 topIndex = pos; 868 } 869 } 870 } 871 872 if (topWay == null || topNode == null) { 873 throw new IllegalArgumentException(); 874 } 875 876 //get the upper way and it's orientation. 877 878 boolean wayClockwise; // orientation of the top way. 879 880 if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) { 881 Node headNode; // the node at junction 882 Node prevNode; // last node from previous path 883 884 //node is in split point - find the outermost way from this point 885 886 headNode = topNode; 887 //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths. 888 prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5)); 889 890 topWay = null; 891 wayClockwise = false; 892 Node bestWayNextNode = null; 893 894 for (Way way : parts) { 895 if (way.firstNode().equals(headNode)) { 896 Node nextNode = way.getNode(1); 897 898 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { 899 //the new way is better 900 topWay = way; 901 wayClockwise = true; 902 bestWayNextNode = nextNode; 913 // the data is prepared so that all ways are split at possible intersection points. 914 // To find out which side of the way the outer side is, we can follow a ray starting anywhere at the way in any direction. 915 // Computation is done in East/North space. 916 // We use a ray at a fixed yRay coordinate that ends at xRay; 917 // we need to make sure this ray does not go into the same direction the way is going. 918 // This is done by rotating by 90° if we need to. 919 920 return parts.stream().map(way -> { 921 int intersections = 0; 922 // Use some random start point on the way 923 EastNorth rayNode1 = way.getNode(0).getEastNorth(); 924 EastNorth rayNode2 = way.getNode(1).getEastNorth(); 925 EastNorth rayFrom = rayNode1.getCenter(rayNode2); 926 927 // Now find the x/y mapping function. We need to ensure that rayNode1->rayNode2 is not parallel to our x axis. 928 ToDoubleFunction<EastNorth> x; 929 ToDoubleFunction<EastNorth> y; 930 if (Math.abs(rayNode1.east() - rayNode2.east()) < Math.abs(rayNode1.north() - rayNode2.north())) { 931 x = en -> en.east(); 932 y = en -> en.north(); 933 } else { 934 x = en -> -en.north(); 935 y = en -> en.east(); 936 } 937 938 double xRay = x.applyAsDouble(rayFrom); 939 double yRay = y.applyAsDouble(rayFrom); 940 941 for(Way part : parts) { 942 // intersect against all way segments 943 for (int i = 0; i < part.getNodesCount() - 1; i++) { 944 EastNorth n1 = part.getNode(i).getEastNorth(); 945 EastNorth n2 = part.getNode(i + 1).getEastNorth(); 946 if ((rayNode1.equals(n1) && rayNode2.equals(n2)) || (rayNode2.equals(n1) && rayNode1.equals(n2))) { 947 // This is the segment we are starting the ray from. 948 // We ignore this to avoid rounding errors. 949 continue; 903 950 } 904 } 905 906 if (way.lastNode().equals(headNode)) { 907 //end adjacent to headNode 908 Node nextNode = way.getNode(way.getNodesCount() - 2); 909 910 if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { 911 //the new way is better 912 topWay = way; 913 wayClockwise = false; 914 bestWayNextNode = nextNode; 951 952 double x1 = x.applyAsDouble(n1); 953 double x2 = x.applyAsDouble(n2); 954 double y1 = y.applyAsDouble(n1); 955 double y2 = y.applyAsDouble(n2); 956 957 if (!(y1 <= yRay && yRay < y2 || y2 <= yRay && yRay < y1)) { 958 // No intersection, since segment is above/below ray 959 continue; 915 960 } 916 } 917 } 918 } else { 919 //node is inside way - pick the clockwise going end. 920 Node prev = topWay.getNode(topIndex - 1); 921 Node next = topWay.getNode(topIndex + 1); 922 923 //there will be no parallel segments in the middle of way, so all fine. 924 wayClockwise = Geometry.angleIsClockwise(prev, topNode, next); 925 } 926 927 Way curWay = topWay; 928 boolean curWayInsideToTheRight = wayClockwise ^ isInner; 929 List<WayInPolygon> result = new ArrayList<>(); 930 931 //iterate till full circle is reached 932 while (curWay != null) { 933 934 //add cur way 935 WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight); 936 result.add(resultWay); 937 938 //process next way 939 Way nextWay = nextWayMap.get(curWay); 940 Node prevNode = curWay.getNode(curWay.getNodesCount() - 2); 941 Node headNode = curWay.lastNode(); 942 Node nextNode = nextWay.getNode(1); 943 944 if (nextWay == topWay) { 945 //full loop traversed - all done. 946 break; 947 } 948 949 //find intersecting segments 950 // the intersections will look like this: 951 // 952 // ^ 953 // | 954 // X wayBNode 955 // | 956 // wayB | 957 // | 958 // curWay | nextWay 959 //----X----------------->X----------------------X----> 960 // prevNode ^headNode nextNode 961 // | 962 // | 963 // wayA | 964 // | 965 // X wayANode 966 // | 967 968 int intersectionCount = 0; 969 970 for (Way wayA : parts) { 971 972 if (wayA == curWay) { 973 continue; 974 } 975 976 if (wayA.lastNode().equals(headNode)) { 977 978 Way wayB = nextWayMap.get(wayA); 979 980 //test if wayA is opposite wayB relative to curWay and nextWay 981 982 Node wayANode = wayA.getNode(wayA.getNodesCount() - 2); 983 Node wayBNode = wayB.getNode(1); 984 985 boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); 986 boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); 987 988 if (wayAToTheRight != wayBToTheRight) { 989 intersectionCount++; 961 double xIntersect = x1 + (x2 - x1) * (yRay - y1) / (y2 - y1); 962 if (xIntersect < xRay) { 963 intersections++; 990 964 } 991 965 } 992 966 } 993 967 994 //if odd number of crossings, invert orientation 995 if (intersectionCount % 2 != 0) { 996 curWayInsideToTheRight = !curWayInsideToTheRight; 997 } 998 999 curWay = nextWay; 1000 } 1001 1002 return result; 968 return new WayInPolygon(way, (intersections % 2 == 0) ^ isInner ^ (y.applyAsDouble(rayNode1) > yRay)); 969 }).collect(Collectors.toList()); 1003 970 } 1004 971 … … 1149 1116 // This seems to appear when is apply over invalid way like #9911 test-case 1150 1117 // Remove all of these way to make the next work. 1151 List<WayInPolygon> cleanMultigonWays = new ArrayList<>(); 1152 for (WayInPolygon way: multigonWays) { 1153 if (way.way.getNodesCount() != 2 || !way.way.isClosed()) 1154 cleanMultigonWays.add(way); 1155 } 1156 1118 List<WayInPolygon> cleanMultigonWays = multigonWays.stream() 1119 .filter(way -> way.way.getNodesCount() != 2 || !way.way.isClosed()) 1120 .collect(Collectors.toList()); 1157 1121 WayTraverser traverser = new WayTraverser(cleanMultigonWays); 1158 1122 List<AssembledPolygon> result = new ArrayList<>(); 1159 1123 1160 WayInPolygon startWay; 1161 while ((startWay = traverser.startNewWay()) != null) { 1162 List<WayInPolygon> path = new ArrayList<>(); 1163 List<WayInPolygon> startWays = new ArrayList<>(); 1124 try { 1125 WayInPolygon startWay; 1126 while ((startWay = traverser.startNewWay()) != null) { 1127 findBoundaryPolygonsStartingWith(discardedResult, traverser, result, startWay); 1128 } 1129 } catch (Throwable t) { 1130 throw BugReport.intercept(t).put("traverser", traverser); 1131 } 1132 1133 return fixTouchingPolygons(result); 1134 } 1135 1136 private static void findBoundaryPolygonsStartingWith(List<Way> discardedResult, WayTraverser traverser, List<AssembledPolygon> result, 1137 WayInPolygon startWay) { 1138 List<WayInPolygon> path = new ArrayList<>(); 1139 List<WayInPolygon> startWays = new ArrayList<>(); 1140 try { 1164 1141 path.add(startWay); 1165 1142 while (true) { 1166 WayInPolygon leftComing; 1167 while ((leftComing = traverser.leftComingWay()) != null) { 1168 if (startWays.contains(leftComing)) 1169 break; 1143 WayInPolygon leftComing = traverser.leftComingWay(); 1144 if (leftComing != null && !startWays.contains(leftComing)) { 1170 1145 // Need restart traverser walk 1171 1146 path.clear(); … … 1173 1148 traverser.setStartWay(leftComing); 1174 1149 startWays.add(leftComing); 1175 break;1176 1150 } 1177 1151 WayInPolygon nextWay = traverser.walk(); 1178 if (nextWay == null) 1179 throw new JosmRuntimeException("Join areas internal error."); 1152 if (nextWay == null) { 1153 throw new JosmRuntimeException("Join areas internal error: traverser could not find a next way."); 1154 } 1180 1155 if (path.get(0) == nextWay) { 1181 1156 // path is closed -> stop here … … 1208 1183 } 1209 1184 } 1210 } 1211 1212 return fixTouchingPolygons(result);1185 } catch (Throwable t) { 1186 throw BugReport.intercept(t).put("path", path); 1187 } 1213 1188 } 1214 1189
Note:
See TracChangeset
for help on using the changeset viewer.
