Repository: graphhopper/graphhopper
Pull request #2305 (2021-05-06 09:06:06)

Skip shapes which don't block any edges
BlockArea currently treats an empty GHIntHashSet the same way as a non-existing cache for blocked edges. But a small shape which doesn't cover edges in the graph would also yield an empty GHIntHashSet. For those cases BlockArea would resort to the more expensive bbox/shape intersection logic:

https://github.com/graphhopper/graphhopper/blob/0522c495ccad5f22fe19c6e858a40a7bd6f74eae/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java#L198-L223

I changed the logic to explicitly store `null` as the cache for blocked edges if the shape is to large so we can properly determine if we have no cache or if it's just empty.

karussell: If a shape does not cover edges - maybe we should even throw an exception? (it might be too ugly?)

Did you had a chance to measure the query difference? Because this API is kind of legacy and if the difference is huge it will be critical to implement this for the new option via custom model too.
otbutz: ![Screenshot_20210506_111718](https://user-images.githubusercontent.com/22315436/117273952-e2c94e80-ae5c-11eb-92d0-b7a4a18415e9.png)

otbutz: Noticed this while benchmarking requests with a few blocked points. And e.g a point might not always cover an edge in the graph if the road is not present in OSM.
otbutz: We could also drop these kind of shapes. There's no point to do the checks if we know that we won't find any intersections?
karussell: Yes, either this or throwing an exception.
otbutz: Apart from `GraphHopperTest:556` everything seems to work. 
otbutz: Shouldn't have skipped my :coffee: Readded the `continue` statement in the intersect check loop and everything is working as expected

Patch:
diff --git a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
index cffb13feb..22ce3ab78 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
@@ -28,6 +28,7 @@ import org.locationtech.jts.algorithm.RectangleLineIntersector;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
+import java.util.Objects;
 
 import static com.graphhopper.util.shapes.BBox.toEnvelope;
 
@@ -38,7 +39,7 @@ import static com.graphhopper.util.shapes.BBox.toEnvelope;
  */
 public class GraphEdgeIdFinder {
 
-    private final static int P_RADIUS = 5;
+    private static final int P_RADIUS = 5;
     private final Graph graph;
     private final LocationIndex locationIndex;
 
@@ -47,6 +48,16 @@ public class GraphEdgeIdFinder {
         this.locationIndex = locationIndex;
     }
 
+    static double calculateArea(Shape shape) {
+        if (shape instanceof BBox)
+            return calculateArea((BBox) shape);
+        if (shape instanceof Polygon)
+            return calculateArea((Polygon) shape);
+        if (shape instanceof Circle)
+            return calculateArea((Circle) shape);
+        throw new IllegalStateException("Unsupported shape: " + shape);
+    }
+    
     /**
      * @param bBox
      * @return an estimated area in m^2 using the mean value of latitudes for longitude distance
@@ -68,9 +79,10 @@ public class GraphEdgeIdFinder {
     }
 
     /**
-     * This method fills the edgeIds hash with edgeIds found inside the specified shape
+     * This method creates an edgeIds hashset with edgeIds found inside the specified shape
      */
-    public void findEdgesInShape(final GHIntHashSet edgeIds, final Shape shape, EdgeFilter filter) {
+    private GHIntHashSet findEdgesInShape(final Shape shape, EdgeFilter filter) {
+        GHIntHashSet edgeIds = new GHIntHashSet();
         locationIndex.query(shape.getBounds(), new LocationIndex.Visitor() {
             @Override
             public void onEdge(int edgeId) {
@@ -79,6 +91,7 @@ public class GraphEdgeIdFinder {
                     edgeIds.add(edge.getEdge());
             }
         });
+        return edgeIds;
     }
 
     public static GraphEdgeIdFinder.BlockArea createBlockArea(Graph graph, LocationIndex locationIndex,
@@ -110,43 +123,44 @@ public class GraphEdgeIdFinder {
                 String objectAsString = blockedCircularAreasArr[i];
                 String[] splittedObject = objectAsString.split(innerObjSep);
 
+                Shape shape;
+                boolean point = false;
                 // always add the shape as we'll need this for virtual edges and for debugging.
                 if (splittedObject.length > 4) {
-                    final Polygon polygon = Polygon.parsePoints(objectAsString);
-                    GHIntHashSet blockedEdges = blockArea.add(polygon);
-                    if (calculateArea(polygon) <= useEdgeIdsUntilAreaSize)
-                        findEdgesInShape(blockedEdges, polygon, filter);
+                    shape = Polygon.parsePoints(objectAsString);
                 } else if (splittedObject.length == 4) {
                     final BBox bbox = BBox.parseTwoPoints(objectAsString);
                     final RectangleLineIntersector cachedIntersector = new RectangleLineIntersector(toEnvelope(bbox));
-                    BBox preparedBBox = new BBox(bbox.minLon, bbox.maxLon, bbox.minLat, bbox.maxLat) {
+                    shape = new BBox(bbox.minLon, bbox.maxLon, bbox.minLat, bbox.maxLat) {
                         @Override
                         public boolean intersects(PointList pointList) {
                             return BBox.intersects(cachedIntersector, pointList);
                         }
                     };
-                    GHIntHashSet blockedEdges = blockArea.add(preparedBBox);
-                    if (calculateArea(bbox) <= useEdgeIdsUntilAreaSize)
-                        findEdgesInShape(blockedEdges, preparedBBox, filter);
                 } else if (splittedObject.length == 3) {
                     double lat = Double.parseDouble(splittedObject[0]);
                     double lon = Double.parseDouble(splittedObject[1]);
                     int radius = Integer.parseInt(splittedObject[2]);
-                    Circle circle = new Circle(lat, lon, radius);
-                    GHIntHashSet blockedEdges = blockArea.add(circle);
-                    if (calculateArea(circle) <= useEdgeIdsUntilAreaSize)
-                        findEdgesInShape(blockedEdges, circle, filter);
-
+                    shape = new Circle(lat, lon, radius);
                 } else if (splittedObject.length == 2) {
                     double lat = Double.parseDouble(splittedObject[0]);
                     double lon = Double.parseDouble(splittedObject[1]);
-                    Circle circle = new Circle(lat, lon, P_RADIUS);
-                    GHIntHashSet blockedEdges = blockArea.add(circle);
-                    findEdgesInShape(blockedEdges, circle, filter);
+                    shape = new Circle(lat, lon, P_RADIUS);
+                    point = true;
                 } else {
                     throw new IllegalArgumentException(objectAsString + " at index " + i + " need to be defined as lat,lon "
                             + "or as a circle lat,lon,radius or rectangular lat1,lon1,lat2,lon2");
                 }
+                
+                
+                if (point || calculateArea(shape) <= useEdgeIdsUntilAreaSize) {
+                    GHIntHashSet blockedEdges = findEdgesInShape(shape, filter);
+                    if (!blockedEdges.isEmpty()) {
+                        blockArea.add(shape, blockedEdges);
+                    }
+                } else {
+                    blockArea.add(shape);
+                }
             }
         }
         return blockArea;
@@ -176,12 +190,14 @@ public class GraphEdgeIdFinder {
             Collections.sort(returnList);
             return returnList.toString();
         }
+        
+        public void add(Shape shape) {
+            add(shape, new GHIntHashSet());
+        }
 
-        public GHIntHashSet add(Shape shape) {
+        public void add(Shape shape, GHIntHashSet blockedEdgeIds) {
             blockedShapes.add(shape);
-            GHIntHashSet set = new GHIntHashSet();
-            edgesList.add(set);
-            return set;
+            edgesList.add(Objects.requireNonNull(blockedEdgeIds));
         }
 
         public final boolean contains(GHPoint point) {
diff --git a/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java b/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java
index bf4f0185d..b3ad7ae85 100644
--- a/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java
+++ b/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java
@@ -242,7 +242,7 @@ public class MapMatching {
                         if (seenEdges.add(edgeId) && edgeFilter.accept(edge)) {
                             Snap snap = new Snap(queryLat, queryLon);
                             locationIndex.traverseEdge(queryLat, queryLon, edge, (node, normedDist, wayIndex, pos) -> {
-                                if ((pos != Snap.Position.TOWER || seenNodes.add(node)) && normedDist < snap.getQueryDistance()) {
+                                if (normedDist < snap.getQueryDistance()) {
                                     snap.setQueryDistance(normedDist);
                                     snap.setClosestNode(node);
                                     snap.setWayIndex(wayIndex);
@@ -252,7 +252,7 @@ public class MapMatching {
                             double dist = DIST_PLANE.calcDenormalizedDist(snap.getQueryDistance());
                             snap.setClosestEdge(edge);
                             snap.setQueryDistance(dist);
-                            if (snap.isValid()) {
+                            if (snap.isValid() && (snap.getSnappedPosition() != Snap.Position.TOWER || seenNodes.add(snap.getClosestNode()))) {
                                 snap.calcSnappedPoint(DistanceCalcEarth.DIST_EARTH);
                                 if (queryShape.contains(snap.getSnappedPoint().lat, snap.getSnappedPoint().lon)) {
                                     snaps.add(snap);


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java b/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
index f2e10e596..dd4077c9c 100644
--- a/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/weighting/BlockAreaWeightingTest.java
@@ -48,8 +48,9 @@ public class BlockAreaWeightingTest {
         BlockAreaWeighting instance = new BlockAreaWeighting(new FastestWeighting(encoder), bArea);
         assertEquals(94.35, instance.calcEdgeWeight(edge, false), .01);
 
-        GHIntHashSet set = bArea.add(null);
+        GHIntHashSet set = new GHIntHashSet();
         set.add(0);
+        bArea.add(null, set);
         instance = new BlockAreaWeighting(new FastestWeighting(encoder), bArea);
         assertEquals(Double.POSITIVE_INFINITY, instance.calcEdgeWeight(edge, false), .01);
     }
@@ -75,8 +76,9 @@ public class BlockAreaWeightingTest {
     public void testBlockVirtualEdges_QueryGraph() {
         GraphEdgeIdFinder.BlockArea bArea = new GraphEdgeIdFinder.BlockArea(graph);
         // add base graph edge to fill caches and trigger edgeId cache search (without virtual edges)
-        GHIntHashSet set = bArea.add(new Circle(0.0025, 0.0025, 1));
+        GHIntHashSet set = new GHIntHashSet();
         set.add(0);
+        bArea.add(new Circle(0.0025, 0.0025, 1), set);
 
         LocationIndex index = new LocationIndexTree(graph, graph.getDirectory()).prepareIndex();
         Snap snap = index.findClosest(0.005, 0.005, EdgeFilter.ALL_EDGES);