Index: /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java =================================================================== --- /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 11728) +++ /trunk/src/org/openstreetmap/josm/actions/JoinAreasAction.java (revision 11729) @@ -11,5 +11,6 @@ import java.util.Collection; import java.util.Collections; -import java.util.HashMap; +import java.util.Comparator; +import java.util.EnumSet; import java.util.HashSet; import java.util.LinkedHashSet; @@ -18,6 +19,15 @@ import java.util.Map; import java.util.Objects; +import java.util.Optional; import java.util.Set; import java.util.TreeMap; +import java.util.function.BiConsumer; +import java.util.function.BinaryOperator; +import java.util.function.Function; +import java.util.function.Supplier; +import java.util.function.ToDoubleFunction; +import java.util.stream.Collector; +import java.util.stream.Collectors; +import java.util.stream.Stream; import javax.swing.JOptionPane; @@ -50,4 +60,5 @@ import org.openstreetmap.josm.tools.UserCancelException; import org.openstreetmap.josm.tools.Utils; +import org.openstreetmap.josm.tools.bugreport.BugReport; /** @@ -180,4 +191,9 @@ return insideToTheRight == that.insideToTheRight && Objects.equals(way, that.way); + } + + @Override + public String toString() { + return "WayInPolygon [way=" + way + ", insideToTheRight=" + insideToTheRight + "]"; } } @@ -242,5 +258,5 @@ /** Set of {@link WayInPolygon} to be joined by walk algorithm */ - private final Set availableWays; + private final List availableWays; /** Current state of walk algorithm */ private WayInPolygon lastWay; @@ -252,5 +268,5 @@ */ WayTraverser(Collection ways) { - availableWays = new HashSet<>(ways); + availableWays = new ArrayList<>(ways); lastWay = null; } @@ -344,47 +360,30 @@ double headAngle = Math.atan2(headNode.getEastNorth().east() - prevNode.getEastNorth().east(), headNode.getEastNorth().north() - prevNode.getEastNorth().north()); - double bestAngle = 0; - - //find best next way - WayInPolygon bestWay = null; - boolean bestWayReverse = false; - - for (WayInPolygon way : availableWays) { - Node nextNode; - - // Check for a connected way - if (way.way.firstNode().equals(headNode) && way.insideToTheRight) { - nextNode = way.way.getNode(1); - } else if (way.way.lastNode().equals(headNode) && !way.insideToTheRight) { - nextNode = way.way.getNode(way.way.getNodesCount() - 2); - } else { - continue; - } - - if (nextNode == prevNode) { - // go back - lastWay = way; - lastWayReverse = !way.insideToTheRight; - return lastWay; - } - - double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(), - nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle; - if (angle > Math.PI) - angle -= 2*Math.PI; - if (angle <= -Math.PI) - angle += 2*Math.PI; - - // Now we have a valid candidate way, is it better than the previous one ? - if (bestWay == null || angle > bestAngle) { - //the new way is better - bestWay = way; - bestWayReverse = !way.insideToTheRight; - bestAngle = angle; - } - } - - lastWay = bestWay; - lastWayReverse = bestWayReverse; + + // Pairs of (way, nextNode) + lastWay = Stream.concat( + availableWays.stream() + .filter(way -> way.way.firstNode().equals(headNode) && way.insideToTheRight) + .map(way -> new Pair<>(way, way.way.getNode(1))), + availableWays.stream() + .filter(way -> way.way.lastNode().equals(headNode) && !way.insideToTheRight) + .map(way -> new Pair<>(way, way.way.getNode(way.way.getNodesCount() - 2)))) + + // now find the way with the best angle + .min(Comparator.comparingDouble(wayAndNext -> { + Node nextNode = wayAndNext.b; + if (nextNode == prevNode) { + // we always prefer going back. + return Double.POSITIVE_INFINITY; + } + double angle = Math.atan2(nextNode.getEastNorth().east() - headNode.getEastNorth().east(), + nextNode.getEastNorth().north() - headNode.getEastNorth().north()) - headAngle; + if (angle > Math.PI) + angle -= 2*Math.PI; + if (angle <= -Math.PI) + angle += 2*Math.PI; + return angle; + })).map(wayAndNext -> wayAndNext.a).orElse(null); + lastWayReverse = lastWay != null && !lastWay.insideToTheRight; return lastWay; } @@ -428,4 +427,10 @@ return comingToHead ? mostLeft : null; + } + + @Override + public String toString() { + return "WayTraverser [availableWays=" + availableWays + ", lastWay=" + lastWay + ", lastWayReverse=" + + lastWayReverse + "]"; } } @@ -591,4 +596,66 @@ } + private static class DuplicateWayCollectorAccu { + private List currentWays = new ArrayList<>(); + private List duplicatesFound = new ArrayList<>(); + + private void add(Way way) { + List wayNodes = way.getNodes(); + List wayNodesReversed = way.getNodes(); + Collections.reverse(wayNodesReversed); + Optional duplicate = currentWays.stream() + .filter(current -> current.getNodes().equals(wayNodes) || current.getNodes().equals(wayNodesReversed)) + .findFirst(); + if (duplicate.isPresent()) { + currentWays.remove(duplicate.get()); + duplicatesFound.add(duplicate.get()); + duplicatesFound.add(way); + } else { + currentWays.add(way); + } + } + + private DuplicateWayCollectorAccu combine(DuplicateWayCollectorAccu a2) { + duplicatesFound.addAll(a2.duplicatesFound); + a2.currentWays.forEach(this::add); + return this; + } + } + + /** + * A collector that collects to a list of duplicated way pairs. + * + * It does not scale well (O(n²)), but the data base should be small enough to make this efficient. + * + * @author Michael Zangl + */ + private static class DuplicateWayCollector implements Collector> { + @Override + public Supplier supplier() { + return DuplicateWayCollectorAccu::new; + } + + @Override + public BiConsumer accumulator() { + return DuplicateWayCollectorAccu::add; + } + + @Override + public BinaryOperator combiner() { + return DuplicateWayCollectorAccu::combine; + } + + @Override + public Function> finisher() { + return a -> a.duplicatesFound; + } + + @Override + public Set characteristics() { + return EnumSet.of(Collector.Characteristics.UNORDERED); + } + + } + /** * Will join two or more overlapping areas @@ -642,16 +709,21 @@ List preparedWays = new ArrayList<>(); - for (Way way : outerStartingWays) { - List splitWays = splitWayOnNodes(way, nodes); - preparedWays.addAll(markWayInsideSide(splitWays, false)); - } - - for (Way way : innerStartingWays) { - List splitWays = splitWayOnNodes(way, nodes); - preparedWays.addAll(markWayInsideSide(splitWays, true)); - } + // Split the nodes on the + List splitOuterWays = outerStartingWays.stream() + .flatMap(way -> splitWayOnNodes(way, nodes).stream()).collect(Collectors.toList()); + List splitInnerWays = innerStartingWays.stream() + .flatMap(way -> splitWayOnNodes(way, nodes).stream()).collect(Collectors.toList()); + + // remove duplicate ways (A->B->C and C->B->A) + List duplicates = Stream.concat(splitOuterWays.stream(), splitInnerWays.stream()).collect(new DuplicateWayCollector()); + + splitOuterWays.removeAll(duplicates); + splitInnerWays.removeAll(duplicates); + + preparedWays.addAll(markWayInsideSide(splitOuterWays, false)); + preparedWays.addAll(markWayInsideSide(splitInnerWays, true)); // Find boundary ways - List discardedWays = new ArrayList<>(); + List discardedWays = new ArrayList<>(duplicates); List boundaries = findBoundaryPolygons(preparedWays, discardedWays); @@ -839,166 +911,61 @@ */ private static List markWayInsideSide(List parts, boolean isInner) { - - //prepare next map - Map nextWayMap = new HashMap<>(); - - for (int pos = 0; pos < parts.size(); pos++) { - - if (!parts.get(pos).lastNode().equals(parts.get((pos + 1) % parts.size()).firstNode())) - throw new IllegalArgumentException("Way not circular"); - - nextWayMap.put(parts.get(pos), parts.get((pos + 1) % parts.size())); - } - - //find the node with minimum y - it's guaranteed to be outer. (What about the south pole?) - Way topWay = null; - Node topNode = null; - int topIndex = 0; - double minY = Double.POSITIVE_INFINITY; - - for (Way way : parts) { - for (int pos = 0; pos < way.getNodesCount(); pos++) { - Node node = way.getNode(pos); - - if (node.getEastNorth().getY() < minY) { - minY = node.getEastNorth().getY(); - topWay = way; - topNode = node; - topIndex = pos; - } - } - } - - if (topWay == null || topNode == null) { - throw new IllegalArgumentException(); - } - - //get the upper way and it's orientation. - - boolean wayClockwise; // orientation of the top way. - - if (topNode.equals(topWay.firstNode()) || topNode.equals(topWay.lastNode())) { - Node headNode; // the node at junction - Node prevNode; // last node from previous path - - //node is in split point - find the outermost way from this point - - headNode = topNode; - //make a fake node that is downwards from head node (smaller Y). It will be a division point between paths. - prevNode = new Node(new EastNorth(headNode.getEastNorth().getX(), headNode.getEastNorth().getY() - 1e5)); - - topWay = null; - wayClockwise = false; - Node bestWayNextNode = null; - - for (Way way : parts) { - if (way.firstNode().equals(headNode)) { - Node nextNode = way.getNode(1); - - if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { - //the new way is better - topWay = way; - wayClockwise = true; - bestWayNextNode = nextNode; + // the data is prepared so that all ways are split at possible intersection points. + // 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. + // Computation is done in East/North space. + // We use a ray at a fixed yRay coordinate that ends at xRay; + // we need to make sure this ray does not go into the same direction the way is going. + // This is done by rotating by 90° if we need to. + + return parts.stream().map(way -> { + int intersections = 0; + // Use some random start point on the way + EastNorth rayNode1 = way.getNode(0).getEastNorth(); + EastNorth rayNode2 = way.getNode(1).getEastNorth(); + EastNorth rayFrom = rayNode1.getCenter(rayNode2); + + // Now find the x/y mapping function. We need to ensure that rayNode1->rayNode2 is not parallel to our x axis. + ToDoubleFunction x; + ToDoubleFunction y; + if (Math.abs(rayNode1.east() - rayNode2.east()) < Math.abs(rayNode1.north() - rayNode2.north())) { + x = en -> en.east(); + y = en -> en.north(); + } else { + x = en -> -en.north(); + y = en -> en.east(); + } + + double xRay = x.applyAsDouble(rayFrom); + double yRay = y.applyAsDouble(rayFrom); + + for(Way part : parts) { + // intersect against all way segments + for (int i = 0; i < part.getNodesCount() - 1; i++) { + EastNorth n1 = part.getNode(i).getEastNorth(); + EastNorth n2 = part.getNode(i + 1).getEastNorth(); + if ((rayNode1.equals(n1) && rayNode2.equals(n2)) || (rayNode2.equals(n1) && rayNode1.equals(n2))) { + // This is the segment we are starting the ray from. + // We ignore this to avoid rounding errors. + continue; } - } - - if (way.lastNode().equals(headNode)) { - //end adjacent to headNode - Node nextNode = way.getNode(way.getNodesCount() - 2); - - if (topWay == null || !Geometry.isToTheRightSideOfLine(prevNode, headNode, bestWayNextNode, nextNode)) { - //the new way is better - topWay = way; - wayClockwise = false; - bestWayNextNode = nextNode; + + double x1 = x.applyAsDouble(n1); + double x2 = x.applyAsDouble(n2); + double y1 = y.applyAsDouble(n1); + double y2 = y.applyAsDouble(n2); + + if (!(y1 <= yRay && yRay < y2 || y2 <= yRay && yRay < y1)) { + // No intersection, since segment is above/below ray + continue; } - } - } - } else { - //node is inside way - pick the clockwise going end. - Node prev = topWay.getNode(topIndex - 1); - Node next = topWay.getNode(topIndex + 1); - - //there will be no parallel segments in the middle of way, so all fine. - wayClockwise = Geometry.angleIsClockwise(prev, topNode, next); - } - - Way curWay = topWay; - boolean curWayInsideToTheRight = wayClockwise ^ isInner; - List result = new ArrayList<>(); - - //iterate till full circle is reached - while (curWay != null) { - - //add cur way - WayInPolygon resultWay = new WayInPolygon(curWay, curWayInsideToTheRight); - result.add(resultWay); - - //process next way - Way nextWay = nextWayMap.get(curWay); - Node prevNode = curWay.getNode(curWay.getNodesCount() - 2); - Node headNode = curWay.lastNode(); - Node nextNode = nextWay.getNode(1); - - if (nextWay == topWay) { - //full loop traversed - all done. - break; - } - - //find intersecting segments - // the intersections will look like this: - // - // ^ - // | - // X wayBNode - // | - // wayB | - // | - // curWay | nextWay - //----X----------------->X----------------------X----> - // prevNode ^headNode nextNode - // | - // | - // wayA | - // | - // X wayANode - // | - - int intersectionCount = 0; - - for (Way wayA : parts) { - - if (wayA == curWay) { - continue; - } - - if (wayA.lastNode().equals(headNode)) { - - Way wayB = nextWayMap.get(wayA); - - //test if wayA is opposite wayB relative to curWay and nextWay - - Node wayANode = wayA.getNode(wayA.getNodesCount() - 2); - Node wayBNode = wayB.getNode(1); - - boolean wayAToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayANode); - boolean wayBToTheRight = Geometry.isToTheRightSideOfLine(prevNode, headNode, nextNode, wayBNode); - - if (wayAToTheRight != wayBToTheRight) { - intersectionCount++; + double xIntersect = x1 + (x2 - x1) * (yRay - y1) / (y2 - y1); + if (xIntersect < xRay) { + intersections++; } } } - //if odd number of crossings, invert orientation - if (intersectionCount % 2 != 0) { - curWayInsideToTheRight = !curWayInsideToTheRight; - } - - curWay = nextWay; - } - - return result; + return new WayInPolygon(way, (intersections % 2 == 0) ^ isInner ^ (y.applyAsDouble(rayNode1) > yRay)); + }).collect(Collectors.toList()); } @@ -1149,23 +1116,31 @@ // This seems to appear when is apply over invalid way like #9911 test-case // Remove all of these way to make the next work. - List cleanMultigonWays = new ArrayList<>(); - for (WayInPolygon way: multigonWays) { - if (way.way.getNodesCount() != 2 || !way.way.isClosed()) - cleanMultigonWays.add(way); - } - + List cleanMultigonWays = multigonWays.stream() + .filter(way -> way.way.getNodesCount() != 2 || !way.way.isClosed()) + .collect(Collectors.toList()); WayTraverser traverser = new WayTraverser(cleanMultigonWays); List result = new ArrayList<>(); - WayInPolygon startWay; - while ((startWay = traverser.startNewWay()) != null) { - List path = new ArrayList<>(); - List startWays = new ArrayList<>(); + try { + WayInPolygon startWay; + while ((startWay = traverser.startNewWay()) != null) { + findBoundaryPolygonsStartingWith(discardedResult, traverser, result, startWay); + } + } catch (Throwable t) { + throw BugReport.intercept(t).put("traverser", traverser); + } + + return fixTouchingPolygons(result); + } + + private static void findBoundaryPolygonsStartingWith(List discardedResult, WayTraverser traverser, List result, + WayInPolygon startWay) { + List path = new ArrayList<>(); + List startWays = new ArrayList<>(); + try { path.add(startWay); while (true) { - WayInPolygon leftComing; - while ((leftComing = traverser.leftComingWay()) != null) { - if (startWays.contains(leftComing)) - break; + WayInPolygon leftComing = traverser.leftComingWay(); + if (leftComing != null && !startWays.contains(leftComing)) { // Need restart traverser walk path.clear(); @@ -1173,9 +1148,9 @@ traverser.setStartWay(leftComing); startWays.add(leftComing); - break; } WayInPolygon nextWay = traverser.walk(); - if (nextWay == null) - throw new JosmRuntimeException("Join areas internal error."); + if (nextWay == null) { + throw new JosmRuntimeException("Join areas internal error: traverser could not find a next way."); + } if (path.get(0) == nextWay) { // path is closed -> stop here @@ -1208,7 +1183,7 @@ } } - } - - return fixTouchingPolygons(result); + } catch (Throwable t) { + throw BugReport.intercept(t).put("path", path); + } }