Changeset 11729 in josm


Ignore:
Timestamp:
2017-03-13T19:35:13+01:00 (9 months ago)
Author:
michael2402
Message:

Fix #10511: Use new algorithm to check which side of the way is the inner/outer side.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java

    r11611 r11729  
    1111import java.util.Collection;
    1212import java.util.Collections;
    13 import java.util.HashMap;
     13import java.util.Comparator;
     14import java.util.EnumSet;
    1415import java.util.HashSet;
    1516import java.util.LinkedHashSet;
     
    1819import java.util.Map;
    1920import java.util.Objects;
     21import java.util.Optional;
    2022import java.util.Set;
    2123import java.util.TreeMap;
     24import java.util.function.BiConsumer;
     25import java.util.function.BinaryOperator;
     26import java.util.function.Function;
     27import java.util.function.Supplier;
     28import java.util.function.ToDoubleFunction;
     29import java.util.stream.Collector;
     30import java.util.stream.Collectors;
     31import java.util.stream.Stream;
    2232
    2333import javax.swing.JOptionPane;
     
    5060import org.openstreetmap.josm.tools.UserCancelException;
    5161import org.openstreetmap.josm.tools.Utils;
     62import org.openstreetmap.josm.tools.bugreport.BugReport;
    5263
    5364/**
     
    180191            return insideToTheRight == that.insideToTheRight &&
    181192                    Objects.equals(way, that.way);
     193        }
     194
     195        @Override
     196        public String toString() {
     197            return "WayInPolygon [way=" + way + ", insideToTheRight=" + insideToTheRight + "]";
    182198        }
    183199    }
     
    242258
    243259        /** Set of {@link WayInPolygon} to be joined by walk algorithm */
    244         private final Set<WayInPolygon> availableWays;
     260        private final List<WayInPolygon> availableWays;
    245261        /** Current state of walk algorithm */
    246262        private WayInPolygon lastWay;
     
    252268         */
    253269        WayTraverser(Collection<WayInPolygon> ways) {
    254             availableWays = new HashSet<>(ways);
     270            availableWays = new ArrayList<>(ways);
    255271            lastWay = null;
    256272        }
     
    344360            double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(),
    345361                    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;
    389388            return lastWay;
    390389        }
     
    428427
    429428            return comingToHead ? mostLeft : null;
     429        }
     430
     431        @Override
     432        public String toString() {
     433            return "WayTraverser [availableWays=" + availableWays + ", lastWay=" + lastWay + ", lastWayReverse="
     434                    + lastWayReverse + "]";
    430435        }
    431436    }
     
    591596    }
    592597
     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
    593660    /**
    594661     * Will join two or more overlapping areas
     
    642709        List<WayInPolygon> preparedWays = new ArrayList<>();
    643710
    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));
    653725
    654726        // Find boundary ways
    655         List<Way> discardedWays = new ArrayList<>();
     727        List<Way> discardedWays = new ArrayList<>(duplicates);
    656728        List<AssembledPolygon> boundaries = findBoundaryPolygons(preparedWays, discardedWays);
    657729
     
    839911     */
    840912    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;
    903950                    }
    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;
    915960                    }
    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++;
    990964                    }
    991965                }
    992966            }
    993967
    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());
    1003970    }
    1004971
     
    11491116        // This seems to appear when is apply over invalid way like #9911 test-case
    11501117        // 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());
    11571121        WayTraverser traverser = new WayTraverser(cleanMultigonWays);
    11581122        List<AssembledPolygon> result = new ArrayList<>();
    11591123
    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 {
    11641141            path.add(startWay);
    11651142            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)) {
    11701145                    // Need restart traverser walk
    11711146                    path.clear();
     
    11731148                    traverser.setStartWay(leftComing);
    11741149                    startWays.add(leftComing);
    1175                     break;
    11761150                }
    11771151                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                }
    11801155                if (path.get(0) == nextWay) {
    11811156                    // path is closed -> stop here
     
    12081183                }
    12091184            }
    1210         }
    1211 
    1212         return fixTouchingPolygons(result);
     1185        } catch (Throwable t) {
     1186            throw BugReport.intercept(t).put("path", path);
     1187        }
    12131188    }
    12141189
Note: See TracChangeset for help on using the changeset viewer.