Changeset 11822 in josm


Ignore:
Timestamp:
2017-04-01T23:40:26+02:00 (7 months ago)
Author:
michael2402
Message:

See #14528: Revert join areas algorithm to old version for 17.03 release.

File:
1 edited

Legend:

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

    r11767 r11822  
    1111import java.util.Collection;
    1212import java.util.Collections;
    13 import java.util.Comparator;
    14 import java.util.EnumSet;
     13import java.util.HashMap;
    1514import java.util.HashSet;
    1615import java.util.LinkedHashSet;
     
    1918import java.util.Map;
    2019import java.util.Objects;
    21 import java.util.Optional;
    2220import java.util.Set;
    2321import 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;
    3222
    3323import javax.swing.JOptionPane;
     
    6050import org.openstreetmap.josm.tools.UserCancelException;
    6151import org.openstreetmap.josm.tools.Utils;
    62 import org.openstreetmap.josm.tools.bugreport.BugReport;
    6352
    6453/**
     
    191180            return insideToTheRight == that.insideToTheRight &&
    192181                    Objects.equals(way, that.way);
    193         }
    194 
    195         @Override
    196         public String toString() {
    197             return "WayInPolygon [way=" + way + ", insideToTheRight=" + insideToTheRight + "]";
    198182        }
    199183    }
     
    258242
    259243        /** Set of {@link WayInPolygon} to be joined by walk algorithm */
    260         private final List<WayInPolygon> availableWays;
     244        private final Set<WayInPolygon> availableWays;
    261245        /** Current state of walk algorithm */
    262246        private WayInPolygon lastWay;
     
    268252         */
    269253        WayTraverser(Collection<WayInPolygon> ways) {
    270             availableWays = new ArrayList<>(ways);
     254            availableWays = new HashSet<>(ways);
    271255            lastWay = null;
    272256        }
     
    360344            double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(),
    361345                    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;
    388389            return lastWay;
    389390        }
     
    427428
    428429            return comingToHead ? mostLeft : null;
    429         }
    430 
    431         @Override
    432         public String toString() {
    433             return "WayTraverser [availableWays=" + availableWays + ", lastWay=" + lastWay + ", lastWayReverse="
    434                     + lastWayReverse + "]";
    435430        }
    436431    }
     
    596591    }
    597592
    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 
    660593    /**
    661594     * Will join two or more overlapping areas
     
    709642        List<WayInPolygon> preparedWays = new ArrayList<>();
    710643
    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        }
    725653
    726654        // Find boundary ways
    727         List<Way> discardedWays = new ArrayList<>(duplicates);
     655        List<Way> discardedWays = new ArrayList<>();
    728656        List<AssembledPolygon> boundaries = findBoundaryPolygons(preparedWays, discardedWays);
    729657
     
    911839     */
    912840    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;
    950903                    }
    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;
    960915                    }
    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++;
    964990                    }
    965991                }
    966992            }
    967993
    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;
    9701003    }
    9711004
     
    11161149        // This seems to appear when is apply over invalid way like #9911 test-case
    11171150        // 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
    11211157        WayTraverser traverser = new WayTraverser(cleanMultigonWays);
    11221158        List<AssembledPolygon> result = new ArrayList<>();
    11231159
    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<>();
    11411164            path.add(startWay);
    11421165            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;
    11451170                    // Need restart traverser walk
    11461171                    path.clear();
     
    11481173                    traverser.setStartWay(leftComing);
    11491174                    startWays.add(leftComing);
     1175                    break;
    11501176                }
    11511177                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.");
    11551180                if (path.get(0) == nextWay) {
    11561181                    // path is closed -> stop here
     
    11831208                }
    11841209            }
    1185         } catch (JosmRuntimeException | IllegalArgumentException | IllegalStateException t) {
    1186             throw BugReport.intercept(t).put("path", path);
    1187         }
     1210        }
     1211
     1212        return fixTouchingPolygons(result);
    11881213    }
    11891214
Note: See TracChangeset for help on using the changeset viewer.