Changeset 11822 in josm
- Timestamp:
- 2017-04-01T23:40:26+02:00 (8 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java
r11767 r11822 11 11 import java.util.Collection; 12 12 import java.util.Collections; 13 import java.util.Comparator; 14 import java.util.EnumSet; 13 import java.util.HashMap; 15 14 import java.util.HashSet; 16 15 import java.util.LinkedHashSet; … … 19 18 import java.util.Map; 20 19 import java.util.Objects; 21 import java.util.Optional;22 20 import java.util.Set; 23 21 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;32 22 33 23 import javax.swing.JOptionPane; … … 60 50 import org.openstreetmap.josm.tools.UserCancelException; 61 51 import org.openstreetmap.josm.tools.Utils; 62 import org.openstreetmap.josm.tools.bugreport.BugReport;63 52 64 53 /** … … 191 180 return insideToTheRight == that.insideToTheRight && 192 181 Objects.equals(way, that.way); 193 }194 195 @Override196 public String toString() {197 return "WayInPolygon [way=" + way + ", insideToTheRight=" + insideToTheRight + "]";198 182 } 199 183 } … … 258 242 259 243 /** Set of {@link WayInPolygon} to be joined by walk algorithm */ 260 private final List<WayInPolygon> availableWays;244 private final Set<WayInPolygon> availableWays; 261 245 /** Current state of walk algorithm */ 262 246 private WayInPolygon lastWay; … … 268 252 */ 269 253 WayTraverser(Collection<WayInPolygon> ways) { 270 availableWays = new ArrayList<>(ways);254 availableWays = new HashSet<>(ways); 271 255 lastWay = null; 272 256 } … … 360 344 double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(), 361 345 headNode.getEastNorth().north() - prevNode.getEastNorth().north()); 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; 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; 388 389 return lastWay; 389 390 } … … 427 428 428 429 return comingToHead ? mostLeft : null; 429 }430 431 @Override432 public String toString() {433 return "WayTraverser [availableWays=" + availableWays + ", lastWay=" + lastWay + ", lastWayReverse="434 + lastWayReverse + "]";435 430 } 436 431 } … … 596 591 } 597 592 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 Zangl631 */632 private static class DuplicateWayCollector implements Collector<Way, DuplicateWayCollectorAccu, List<Way>> {633 @Override634 public Supplier<DuplicateWayCollectorAccu> supplier() {635 return DuplicateWayCollectorAccu::new;636 }637 638 @Override639 public BiConsumer<DuplicateWayCollectorAccu, Way> accumulator() {640 return DuplicateWayCollectorAccu::add;641 }642 643 @Override644 public BinaryOperator<DuplicateWayCollectorAccu> combiner() {645 return DuplicateWayCollectorAccu::combine;646 }647 648 @Override649 public Function<DuplicateWayCollectorAccu, List<Way>> finisher() {650 return a -> a.duplicatesFound;651 }652 653 @Override654 public Set<Collector.Characteristics> characteristics() {655 return EnumSet.of(Collector.Characteristics.UNORDERED);656 }657 658 }659 660 593 /** 661 594 * Will join two or more overlapping areas … … 709 642 List<WayInPolygon> preparedWays = new ArrayList<>(); 710 643 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)); 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 } 725 653 726 654 // Find boundary ways 727 List<Way> discardedWays = new ArrayList<>( duplicates);655 List<Way> discardedWays = new ArrayList<>(); 728 656 List<AssembledPolygon> boundaries = findBoundaryPolygons(preparedWays, discardedWays); 729 657 … … 911 839 */ 912 840 private static List<WayInPolygon> markWayInsideSide(List<Way> parts, boolean isInner) { 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; 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; 950 903 } 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; 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; 960 915 } 961 double xIntersect = x1 + (x2 - x1) * (yRay - y1) / (y2 - y1); 962 if (xIntersect < xRay) { 963 intersections++; 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++; 964 990 } 965 991 } 966 992 } 967 993 968 return new WayInPolygon(way, (intersections % 2 == 0) ^ isInner ^ (y.applyAsDouble(rayNode1) > yRay)); 969 }).collect(Collectors.toList()); 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; 970 1003 } 971 1004 … … 1116 1149 // This seems to appear when is apply over invalid way like #9911 test-case 1117 1150 // Remove all of these way to make the next work. 1118 List<WayInPolygon> cleanMultigonWays = multigonWays.stream() 1119 .filter(way -> way.way.getNodesCount() != 2 || !way.way.isClosed()) 1120 .collect(Collectors.toList()); 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 1121 1157 WayTraverser traverser = new WayTraverser(cleanMultigonWays); 1122 1158 List<AssembledPolygon> result = new ArrayList<>(); 1123 1159 1124 try { 1125 WayInPolygon startWay; 1126 while ((startWay = traverser.startNewWay()) != null) { 1127 findBoundaryPolygonsStartingWith(discardedResult, traverser, result, startWay); 1128 } 1129 } catch (JosmRuntimeException | IllegalArgumentException | IllegalStateException 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 { 1160 WayInPolygon startWay; 1161 while ((startWay = traverser.startNewWay()) != null) { 1162 List<WayInPolygon> path = new ArrayList<>(); 1163 List<WayInPolygon> startWays = new ArrayList<>(); 1141 1164 path.add(startWay); 1142 1165 while (true) { 1143 WayInPolygon leftComing = traverser.leftComingWay(); 1144 if (leftComing != null && !startWays.contains(leftComing)) { 1166 WayInPolygon leftComing; 1167 while ((leftComing = traverser.leftComingWay()) != null) { 1168 if (startWays.contains(leftComing)) 1169 break; 1145 1170 // Need restart traverser walk 1146 1171 path.clear(); … … 1148 1173 traverser.setStartWay(leftComing); 1149 1174 startWays.add(leftComing); 1175 break; 1150 1176 } 1151 1177 WayInPolygon nextWay = traverser.walk(); 1152 if (nextWay == null) { 1153 throw new JosmRuntimeException("Join areas internal error: traverser could not find a next way."); 1154 } 1178 if (nextWay == null) 1179 throw new JosmRuntimeException("Join areas internal error."); 1155 1180 if (path.get(0) == nextWay) { 1156 1181 // path is closed -> stop here … … 1183 1208 } 1184 1209 } 1185 } catch (JosmRuntimeException | IllegalArgumentException | IllegalStateException t) {1186 throw BugReport.intercept(t).put("path", path); 1187 }1210 } 1211 1212 return fixTouchingPolygons(result); 1188 1213 } 1189 1214
Note:
See TracChangeset
for help on using the changeset viewer.
