Repository: graphhopper/graphhopper
Pull request #1485 (2018-10-16 10:55:23)

add LocationIndexTree.query(BBox)
This PR adds a new query(BBox) method. Currently we can fetch only nodes from one leaf and so with this querying areas is inefficient. Related to #1127 and #1324.

Furthermore a possibility to visualize the index 

![image](https://user-images.githubusercontent.com/129644/47011326-f9461800-d141-11e8-8f89-da3dd2419730.png)

and some description for the index is added. The description now makes clear that we have a Quadtree implementation with some special tuning. E.g. for bigger areas one node branches not only into 4 subtrees but can branch into 16. Previously also 64 was possible, but we removed this as this has no advantages in terms of storage, query or creation speed. (Measured it for Germany and world wide)

TODOs:

 - [x] ~~to make this correct we need to add +1/2 cell on every side of the BBox. The problem is that we do not add the node to both cells due to the [bresenham line to cell limitation](http://stackoverflow.com/q/24679963/194609)~~ Does not seem to be necessary (no problems e.g. in #1572).
 - [ ] make it working with Polygon too (use JTS Polygon e.g. via embedding in ours so that we can implement `Shape`)
 - [x] use PrepareGeometry  -> #1589
 - [ ] use intersect and contains!
 - [ ] use quality vs. speed properties like UNIQUE_NODES (just make sure nodes come to the Visitor just once), FILTERED_NODES (unique nodes plus filtered again through the shape), HIGH_PRECISION (filtered node but use fetchGeometry instead of just junction nodes)

michaz: Nice, this closes some open ends for me. Is the current state mergeable, meaning, do we think that the bounding-box query does more or less what it should? Because I'd like to.
karussell: Well, this is not fully ready unfortunately. Currently all nodes are returned where the tile intersects with the shape. This is ok for visualisation, but for other use cases we have to filter these nodes and call "shape.contains(node)" as a post processing step. Now the problem is that this could be done cheap like this or in a more expensive manner if we need high precision via "shape.intersects(edge.fetchWayGeometry)". Currently exploring the options on how to do this so that this also works for a Polygon (which basically means using JTS Polygon behind our Polygon class). But we could also bring it into a mergable state faster and I'll create a new issue for the open tasks.
michaz: Oh, that's exactly what I need: "May include more nodes than are contained, but never fails to return something that _is_ contained". I think that's also how other implementations work.
karussell: > Oh, that's exactly what I need: "May include more nodes than are contained, but never fails to return return a node that is contained". I think that's also how other implementations work.

Ah, ok. I think there are indeed two use cases. This one, which you need and we need for fast visualization. But also the other to e.g. block certain edges but not too many!

Maybe I'll bring this PR in a mergable form for the first use case and explicitly mention this and work later on the second "high precision" use case?
michaz: > Maybe I'll bring this PR in a mergable form for the first use case and explicitly mention this and work later on the second "high precision" use case?

Yes, please! For me, this doesn't even mean that this is currently "unfinished" -- _filtering_ the result to the desired level of exclusivity is a _second_ task, and can happen outside of the current method. This one is finished.
michaz: And this method can still narrow down what it returns later on without changing its promise.
karussell: > filtering the result to the desired level of exclusivity is a second task

This is exactly where I'm unsure because the method `index.query(shape)` could also imply that this should be an exact filter and no post-processing work needs to be done.
michaz: Well, "query" as a method name is vague enough that I think it can't be misunderstood as promising anything specific. ;-)

Let's add a Javadoc which explains what this method does and does not (not _how_ it does that), and it'll be fine.
karussell: Ok :D 

Will do this ... let me just do some minor stuff.
karussell: I did the following changes (let me know if this was too much):

 * moved the Visitor interfaces to the LocationIndex interface
 * moved the query method to the interface
 * removed the extra visualize method and made it possible via the Visitor setting isTileInfo (now Visitor has to be an abtract class as default methods are not possible in 7). onTile now directly includes the depth not the too-visualization-specific `width`.
 * avoid duplicate nodes (and edges for the EdgeVisitor)
 * introduced a new "queryBBox.contains" branch to avoid bbox checks on greater depths, should make the query slightly faster
 * renamed Shape.intersect to intersects, also to make later migrations to JTS easier
 * renamed `*cell*` to `*tile*`
 * made some methods non-public

Patch:
diff --git a/api/src/main/java/com/graphhopper/util/shapes/BBox.java b/api/src/main/java/com/graphhopper/util/shapes/BBox.java
index ed716f56d..9a73055f9 100644
--- a/api/src/main/java/com/graphhopper/util/shapes/BBox.java
+++ b/api/src/main/java/com/graphhopper/util/shapes/BBox.java
@@ -19,6 +19,7 @@ package com.graphhopper.util.shapes;
 
 import com.graphhopper.util.Helper;
 import com.graphhopper.util.NumHelper;
+import org.locationtech.jts.geom.Envelope;
 
 import java.util.ArrayList;
 import java.util.List;
@@ -46,7 +47,7 @@ public class BBox implements Shape, Cloneable {
     public double maxEle;
 
     public BBox(double[] coords) {
-        this(coords[0],coords[2],coords[1],coords[3]);
+        this(coords[0], coords[2], coords[1], coords[3]);
     }
 
     public BBox(double minLon, double maxLon, double minLat, double maxLat) {
@@ -122,7 +123,7 @@ public class BBox implements Shape, Cloneable {
      * @return the intersecting BBox or null if not intersecting
      */
     public BBox calculateIntersection(BBox bBox) {
-        if (!this.intersect(bBox))
+        if (!this.intersects(bBox))
             return null;
 
         double minLon = Math.max(this.minLon, bBox.minLon);
@@ -139,11 +140,11 @@ public class BBox implements Shape, Cloneable {
     }
 
     @Override
-    public boolean intersect(Shape s) {
+    public boolean intersects(Shape s) {
         if (s instanceof BBox) {
-            return intersect((BBox) s);
+            return intersects((BBox) s);
         } else if (s instanceof Circle) {
-            return ((Circle) s).intersect(this);
+            return ((Circle) s).intersects(this);
         }
 
         throw new UnsupportedOperationException("unsupported shape");
@@ -160,14 +161,24 @@ public class BBox implements Shape, Cloneable {
         throw new UnsupportedOperationException("unsupported shape");
     }
 
-    public boolean intersect(Circle s) {
-        return ((Circle) s).intersect(this);
+    public boolean intersects(Circle s) {
+        return s.intersects(this);
     }
 
-    public boolean intersect(BBox o) {
+    /**
+     * This method calculates if this BBox intersects with the specified BBox
+     */
+    public boolean intersects(double minLon, double maxLon, double minLat, double maxLat) {
+        return this.minLon < maxLon && this.minLat < maxLat && minLon < this.maxLon && minLat < this.maxLat;
+    }
+
+    /**
+     * This method calculates if this BBox intersects with the specified BBox
+     */
+    public boolean intersects(BBox o) {
         // return (o.minLon < minLon && o.maxLon > minLon || o.minLon < maxLon && o.minLon >= minLon)
         //  && (o.maxLat < maxLat && o.maxLat >= minLat || o.maxLat >= maxLat && o.minLat < maxLat);
-        return minLon < o.maxLon && minLat < o.maxLat && o.minLon < maxLon && o.minLat < maxLat;
+        return this.minLon < o.maxLon && this.minLat < o.maxLat && o.minLon < this.maxLon && o.minLat < this.maxLat;
     }
 
     @Override
@@ -272,6 +283,10 @@ public class BBox implements Shape, Cloneable {
         return list;
     }
 
+    public static BBox fromEnvelope(Envelope envelope) {
+        return new BBox(envelope.getMinX(), envelope.getMaxX(), envelope.getMinY(), envelope.getMaxY());
+    }
+
     /**
      * @return an estimated area in m^2 using the mean value of latitudes for longitude distance
      */
diff --git a/api/src/main/java/com/graphhopper/util/shapes/Circle.java b/api/src/main/java/com/graphhopper/util/shapes/Circle.java
index 0bf6a57b8..bbb38ee33 100644
--- a/api/src/main/java/com/graphhopper/util/shapes/Circle.java
+++ b/api/src/main/java/com/graphhopper/util/shapes/Circle.java
@@ -73,14 +73,14 @@ public class Circle implements Shape {
     }
 
     @Override
-    public boolean intersect(Shape o) {
+    public boolean intersects(Shape o) {
         if (o instanceof Circle) {
-            return intersect((Circle) o);
+            return intersects((Circle) o);
         } else if (o instanceof BBox) {
-            return intersect((BBox) o);
+            return intersects((BBox) o);
         }
 
-        return o.intersect(this);
+        return o.intersects(this);
     }
 
     @Override
@@ -94,8 +94,8 @@ public class Circle implements Shape {
         throw new UnsupportedOperationException("unsupported shape");
     }
 
-    public boolean intersect(BBox b) {
-        // test top intersect
+    public boolean intersects(BBox b) {
+        // test top intersects
         if (lat > b.maxLat) {
             if (lon < b.minLon) {
                 return normDist(b.maxLat, b.minLon) <= normedDist;
@@ -106,7 +106,7 @@ public class Circle implements Shape {
             return b.maxLat - bbox.minLat > 0;
         }
 
-        // test bottom intersect
+        // test bottom intersects
         if (lat < b.minLat) {
             if (lon < b.minLon) {
                 return normDist(b.minLat, b.minLon) <= normedDist;
@@ -117,7 +117,7 @@ public class Circle implements Shape {
             return bbox.maxLat - b.minLat > 0;
         }
 
-        // test middle intersect
+        // test middle intersects
         if (lon < b.minLon) {
             return bbox.maxLon - b.minLon > 0;
         }
@@ -127,9 +127,9 @@ public class Circle implements Shape {
         return true;
     }
 
-    public boolean intersect(Circle c) {
+    public boolean intersects(Circle c) {
         // necessary to improve speed?
-        if (!getBounds().intersect(c.getBounds())) {
+        if (!getBounds().intersects(c.getBounds())) {
             return false;
         }
 
diff --git a/api/src/main/java/com/graphhopper/util/shapes/Polygon.java b/api/src/main/java/com/graphhopper/util/shapes/Polygon.java
index 52d94115e..abf7c731c 100644
--- a/api/src/main/java/com/graphhopper/util/shapes/Polygon.java
+++ b/api/src/main/java/com/graphhopper/util/shapes/Polygon.java
@@ -100,7 +100,7 @@ public class Polygon implements Shape {
     }
 
     @Override
-    public boolean intersect(Shape o) {
+    public boolean intersects(Shape o) {
         throw new UnsupportedOperationException("Not supported yet.");
     }
 
diff --git a/api/src/main/java/com/graphhopper/util/shapes/Shape.java b/api/src/main/java/com/graphhopper/util/shapes/Shape.java
index dd0f71e5f..7962c6761 100644
--- a/api/src/main/java/com/graphhopper/util/shapes/Shape.java
+++ b/api/src/main/java/com/graphhopper/util/shapes/Shape.java
@@ -27,7 +27,7 @@ public interface Shape {
     /**
      * @return true if edges or areas of this and the specified shapes overlap
      */
-    boolean intersect(Shape o);
+    boolean intersects(Shape o);
 
     /**
      * @return true only if lat and lon are inside (or on the edge) of this shape
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java
index 005c2538a..b44e2baea 100644
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java
+++ b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java
@@ -23,11 +23,11 @@ import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.util.DistanceCalc;
 import com.graphhopper.util.Helper;
+import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.Circle;
 
 /**
  * Very slow O(n) LocationIndex but no RAM/disc required.
- * <p>
  *
  * @author Peter Karich
  */
@@ -102,6 +102,11 @@ public class Location2IDFullIndex implements LocationIndex {
         return res;
     }
 
+    @Override
+    public void query(BBox queryBBox, Visitor function) {
+        throw new IllegalArgumentException("not implemented");
+    }
+
     @Override
     public LocationIndex create(long size) {
         return this;
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java
index 653f666a5..6d822a44c 100644
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java
+++ b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java
@@ -23,6 +23,7 @@ import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.util.DistanceCalc;
 import com.graphhopper.util.Helper;
+import com.graphhopper.util.shapes.BBox;
 
 /**
  * Same as full index but calculates distance to all edges too
@@ -125,6 +126,11 @@ public class Location2IDFullWithEdgesIndex implements LocationIndex {
         return res;
     }
 
+    @Override
+    public void query(BBox queryBBox, Visitor function) {
+        throw new IllegalArgumentException("not implemented");
+    }
+
     @Override
     public LocationIndex create(long size) {
         return this;
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java
index 2ae3f58ca..59445254a 100644
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java
+++ b/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java
@@ -337,6 +337,11 @@ class Location2IDQuadtree implements LocationIndex {
         return res;
     }
 
+    @Override
+    public void query(BBox queryBBox, Visitor function) {
+        throw new IllegalArgumentException("not implemented");
+    }
+
     public void goFurtherHook(int n) {
     }
 
diff --git a/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java b/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java
index a95d49f0d..071744645 100644
--- a/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java
+++ b/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java
@@ -17,8 +17,13 @@
  */
 package com.graphhopper.storage.index;
 
+import com.carrotsearch.hppc.IntHashSet;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.storage.Storable;
+import com.graphhopper.util.EdgeExplorer;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.shapes.BBox;
 
 /**
  * Provides a way to map real world data "lat,lon" to internal ids/indices of a memory efficient graph
@@ -62,4 +67,56 @@ public interface LocationIndex extends Storable<LocationIndex> {
     LocationIndex setApproximation(boolean approxDist);
 
     void setSegmentSize(int bytes);
+
+    /**
+     * This method explores the nodes in this LocationIndex with the specified Visitor. It guarantees to visit all
+     * unique nodes included in the queryBBox but it could visit more.
+     */
+    void query(BBox queryBBox, Visitor function);
+
+    /**
+     * This interface allows to visit every node stored in the leafs of a LocationIndex.
+     */
+    abstract class Visitor {
+        public boolean isTileInfo() {
+            return false;
+        }
+
+        /**
+         * This method is called if isTileInfo is enabled.
+         */
+        public void onTile(BBox bbox, int depth) {
+        }
+
+        public abstract void onNode(int nodeId);
+    }
+
+    /**
+     * This abstract class allows to visit every edge from the stored nodes in the leafs of the tree for a requested
+     * area. It guarantees to visit all unique edges included in the queryBBox but it could be more.
+     */
+    abstract class EdgeVisitor extends Visitor {
+
+        private final IntHashSet edgeIds = new IntHashSet();
+        private final IntHashSet nodeIds = new IntHashSet();
+        private final EdgeExplorer edgeExplorer;
+
+        public EdgeVisitor(EdgeExplorer edgeExplorer) {
+            this.edgeExplorer = edgeExplorer;
+        }
+
+        public final void onNode(int nodeId) {
+            if (!nodeIds.add(nodeId))
+                return;
+
+            EdgeIterator iter = edgeExplorer.setBaseNode(nodeId);
+            while (iter.next()) {
+                if (!edgeIds.add(iter.getEdge()))
+                    continue;
+                onEdge(iter, nodeId, iter.getAdjNode());
+            }
+        }
+
+        public abstract void onEdge(EdgeIteratorState edge, int nodeA, int nodeB);
+    }
 }
diff --git a/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java b/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java
index 7d4d374b4..1eb58fcc2 100644
--- a/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java
+++ b/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java
@@ -18,6 +18,7 @@
 package com.graphhopper.storage.index;
 
 import com.carrotsearch.hppc.IntArrayList;
+import com.carrotsearch.hppc.IntHashSet;
 import com.carrotsearch.hppc.cursors.IntCursor;
 import com.carrotsearch.hppc.predicates.IntPredicate;
 import com.graphhopper.coll.GHBitSet;
@@ -29,18 +30,30 @@ import com.graphhopper.storage.*;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
+import com.graphhopper.util.shapes.Shape;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
 import java.util.*;
 
 /**
- * This implementation implements an n-tree to get the closest node or edge from GPS coordinates.
- * <p>
- * All leafs are at the same depth, otherwise it is quite complicated to calculate the Bresenham
- * line for different resolutions, especially if a leaf node could be split into a tree-node and
- * resolution changes.
- * <p>
+ * This class implements a Quadtree to get the closest node or edge from GPS coordinates.
+ * The following properties are different to an ordinary implementation:
+ * <ol>
+ * <li>To reduce overall size it can use 16 instead of just 4 cell if required</li>
+ * <li>Still all leafs are at the same depth, otherwise it is too complicated to calculate the Bresenham line for different
+ * resolutions, especially if a leaf node could be split into a tree-node and resolution changes.</li>
+ * <li>To further reduce size this Quadtree avoids storing the bounding box of every cell and calculates this per request instead.</li>
+ * <li>To simplify this querying and avoid a slow down for the most frequent queries ala "lat,lon" it encodes the point
+ * into a reverse spatial key {@see SpatialKeyAlgo} and can the use the resulting raw bits as cell index to recurse
+ * into the subtrees. E.g. if there are 3 layers with 16, 4 and 4 cells each, then the reverse spatial key has
+ * three parts: 4 bits for the cellIndex into the 16 cells, 2 bits for the next layer and 2 bits for the last layer.
+ * It is the reverse spatial key and not the forward spatial key as we need the start of the index for the current
+ * layer at index 0</li>
+ * <li>An array structure (DataAccess) is internally used and stores the offset to the next cell.
+ * E.g. in case of 4 cells, the offset is 0,1,2 or 3. Except when the leaf-depth is reached, then the value
+ * is the number of node IDs stored in the cell or, if negative, just a single node ID.</li>
+ * </ol>
  *
  * @author Peter Karich
  */
@@ -84,7 +97,7 @@ public class LocationIndexTree implements LocationIndex {
         if (g instanceof CHGraph)
             throw new IllegalArgumentException("Use base graph for LocationIndexTree instead of CHGraph");
 
-        MAGIC_INT = Integer.MAX_VALUE / 22316;
+        MAGIC_INT = Integer.MAX_VALUE / 22317;
         this.graph = g;
         this.nodeAccess = g.getNodeAccess();
         dataAccess = dir.find("location_index", DAType.getPreferredInt(dir.getDefaultType()));
@@ -145,9 +158,7 @@ public class LocationIndexTree implements LocationIndex {
         tmp /= 4;
         while (tmp > 1) {
             int tmpNo;
-            if (tmp >= 64) {
-                tmpNo = 64;
-            } else if (tmp >= 16) {
+            if (tmp >= 16) {
                 tmpNo = 16;
             } else if (tmp >= 4) {
                 tmpNo = 4;
@@ -335,17 +346,19 @@ public class LocationIndexTree implements LocationIndex {
         return IntArrayList.from(entries);
     }
 
-    // fill node IDs according to how they are stored
+    /**
+     * This method fills the set with stored node IDs from the given spatial key part (a latitude-longitude prefix).
+     */
     final void fillIDs(long keyPart, int intIndex, GHIntHashSet set, int depth) {
         long pointer = (long) intIndex << 2;
         if (depth == entries.length) {
-            int value = dataAccess.getInt(pointer);
-            if (value < 0) {
+            int nextIntPointer = dataAccess.getInt(pointer);
+            if (nextIntPointer < 0) {
                 // single data entries (less disc space)
-                set.add(-(value + 1));
+                set.add(-(nextIntPointer + 1));
             } else {
-                long max = (long) value * 4;
-                // leaf entry => value is maxPointer
+                long max = (long) nextIntPointer * 4;
+                // leaf entry => nextIntPointer is maxPointer
                 for (long leafIndex = pointer + 4; leafIndex < max; leafIndex += 4) {
                     set.add(dataAccess.getInt(leafIndex));
                 }
@@ -353,10 +366,10 @@ public class LocationIndexTree implements LocationIndex {
             return;
         }
         int offset = (int) (bitmasks[depth] & keyPart) << 2;
-        int value = dataAccess.getInt(pointer + offset);
-        if (value > 0) {
+        int nextIntPointer = dataAccess.getInt(pointer + offset);
+        if (nextIntPointer > 0) {
             // tree entry => negative value points to subentries
-            fillIDs(keyPart >>> shifts[depth], value, set, depth + 1);
+            fillIDs(keyPart >>> shifts[depth], nextIntPointer, set, depth + 1);
         }
     }
 
@@ -429,12 +442,76 @@ public class LocationIndexTree implements LocationIndex {
         return deltaLon;
     }
 
-    GHPoint getCenter(double lat, double lon) {
-        GHPoint query = new GHPoint(lat, lon);
-        long key = keyAlgo.encode(query);
-        GHPoint center = new GHPoint();
-        keyAlgo.decode(key, center);
-        return center;
+    public void query(BBox queryShape, final Visitor function) {
+        BBox bbox = graph.getBounds();
+        final IntHashSet set = new IntHashSet();
+        query(START_POINTER, queryShape,
+                bbox.minLat, bbox.minLon, bbox.maxLat - bbox.minLat, bbox.maxLon - bbox.minLon,
+                new Visitor() {
+                    @Override
+                    public boolean isTileInfo() {
+                        return function.isTileInfo();
+                    }
+
+                    @Override
+                    public void onTile(BBox bbox, int width) {
+                        function.onTile(bbox, width);
+                    }
+
+                    @Override
+                    public void onNode(int nodeId) {
+                        if (set.add(nodeId))
+                            function.onNode(nodeId);
+                    }
+                }, 0);
+    }
+
+    final void query(int intPointer, Shape queryBBox,
+                     double minLat, double minLon,
+                     double deltaLatPerDepth, double deltaLonPerDepth,
+                     Visitor function, int depth) {
+        long pointer = (long) intPointer << 2;
+        if (depth == entries.length) {
+            int nextIntPointer = dataAccess.getInt(pointer);
+            if (nextIntPointer < 0) {
+                // single data entries (less disc space)
+                function.onNode(-(nextIntPointer + 1));
+            } else {
+                long maxPointer = (long) nextIntPointer * 4;
+                // loop through every leaf entry => nextIntPointer is maxPointer
+                for (long leafPointer = pointer + 4; leafPointer < maxPointer; leafPointer += 4) {
+                    // we could read the whole info at once via getBytes instead of getInt
+                    function.onNode(dataAccess.getInt(leafPointer));
+                }
+            }
+            return;
+        }
+        int max = (1 << shifts[depth]);
+        int factor = max == 4 ? 2 : 4;
+        deltaLonPerDepth /= factor;
+        deltaLatPerDepth /= factor;
+        for (int cellIndex = 0; cellIndex < max; cellIndex++) {
+            int nextIntPointer = dataAccess.getInt(pointer + cellIndex * 4);
+            if (nextIntPointer <= 0)
+                continue;
+            // this bit magic does two things for the 4 and 16 tiles case:
+            // 1. it assumes the cellIndex is a reversed spatial key and so it reverses it
+            // 2. it picks every second bit (e.g. for just latitudes) and interprets the result as an integer
+            int latCount = max == 4 ? (cellIndex & 1) : (cellIndex & 1) * 2 + ((cellIndex & 4) == 0 ? 0 : 1);
+            int lonCount = max == 4 ? (cellIndex >> 1) : (cellIndex & 2) + ((cellIndex & 8) == 0 ? 0 : 1);
+            double tmpMinLon = minLon + deltaLonPerDepth * lonCount,
+                    tmpMinLat = minLat + deltaLatPerDepth * latCount;
+
+            BBox bbox = (queryBBox != null || function.isTileInfo()) ? new BBox(tmpMinLon, tmpMinLon + deltaLonPerDepth, tmpMinLat, tmpMinLat + deltaLatPerDepth) : null;
+            if (function.isTileInfo())
+                function.onTile(bbox, depth);
+            if (queryBBox == null || queryBBox.contains(bbox)) {
+                // fill without a restriction!
+                query(nextIntPointer, null, tmpMinLat, tmpMinLon, deltaLatPerDepth, deltaLonPerDepth, function, depth + 1);
+            } else if (queryBBox.intersects(bbox)) {
+                query(nextIntPointer, queryBBox, tmpMinLat, tmpMinLon, deltaLatPerDepth, deltaLonPerDepth, function, depth + 1);
+            }
+        }
     }
 
     /**
@@ -446,8 +523,8 @@ public class LocationIndexTree implements LocationIndex {
      * @return true if no further call of this method is required. False otherwise, ie. a next
      * iteration is necessary and no early finish possible.
      */
-    public final boolean findNetworkEntries(double queryLat, double queryLon,
-                                            GHIntHashSet foundEntries, int iteration) {
+    final boolean findNetworkEntries(double queryLat, double queryLon,
+                                     GHIntHashSet foundEntries, int iteration) {
         // find entries in border of searchbox
         for (int yreg = -iteration; yreg <= iteration; yreg++) {
             double subqueryLat = queryLat + yreg * deltaLat;
@@ -502,7 +579,7 @@ public class LocationIndexTree implements LocationIndex {
         return min;
     }
 
-    public final void findNetworkEntriesSingleRegion(GHIntHashSet storedNetworkEntryIds, double queryLat, double queryLon) {
+    final void findNetworkEntriesSingleRegion(GHIntHashSet storedNetworkEntryIds, double queryLat, double queryLon) {
         long keyPart = createReverseKey(queryLat, queryLon);
         fillIDs(keyPart, START_POINTER, storedNetworkEntryIds, 0);
     }
@@ -711,9 +788,6 @@ public class LocationIndexTree implements LocationIndex {
 
     // Space efficient sorted integer set. Suited for only a few entries.
     static class SortedIntSet extends IntArrayList {
-        public SortedIntSet() {
-        }
-
         public SortedIntSet(int capacity) {
             super(capacity);
         }
@@ -851,7 +925,7 @@ public class LocationIndexTree implements LocationIndex {
 
         Collection<InMemEntry> getEntriesOf(int selectDepth) {
             List<InMemEntry> list = new ArrayList<>();
-            fillLayer(list, selectDepth, 0, ((InMemTreeEntry) root).getSubEntriesForDebug());
+            fillLayer(list, selectDepth, 0, root.getSubEntriesForDebug());
             return list;
         }
 
@@ -895,48 +969,48 @@ public class LocationIndexTree implements LocationIndex {
         }
 
         // store and freezes tree
-        int store(InMemEntry entry, int intIndex) {
-            long refPointer = (long) intIndex * 4;
+        int store(InMemEntry entry, int intPointer) {
+            long pointer = (long) intPointer * 4;
             if (entry.isLeaf()) {
                 InMemLeafEntry leaf = ((InMemLeafEntry) entry);
                 IntArrayList entries = leaf.getResults();
                 int len = entries.size();
                 if (len == 0) {
-                    return intIndex;
+                    return intPointer;
                 }
                 size += len;
-                intIndex++;
+                intPointer++;
                 leafs++;
-                dataAccess.ensureCapacity((long) (intIndex + len + 1) * 4);
+                dataAccess.ensureCapacity((long) (intPointer + len + 1) * 4);
                 if (len == 1) {
                     // less disc space for single entries
-                    dataAccess.setInt(refPointer, -entries.get(0) - 1);
+                    dataAccess.setInt(pointer, -entries.get(0) - 1);
                 } else {
-                    for (int index = 0; index < len; index++, intIndex++) {
-                        dataAccess.setInt((long) intIndex * 4, entries.get(index));
+                    for (int index = 0; index < len; index++, intPointer++) {
+                        dataAccess.setInt((long) intPointer * 4, entries.get(index));
                     }
-                    dataAccess.setInt(refPointer, intIndex);
+                    dataAccess.setInt(pointer, intPointer);
                 }
             } else {
                 InMemTreeEntry treeEntry = ((InMemTreeEntry) entry);
                 int len = treeEntry.subEntries.length;
-                intIndex += len;
-                for (int subCounter = 0; subCounter < len; subCounter++, refPointer += 4) {
+                intPointer += len;
+                for (int subCounter = 0; subCounter < len; subCounter++, pointer += 4) {
                     InMemEntry subEntry = treeEntry.subEntries[subCounter];
                     if (subEntry == null) {
                         continue;
                     }
-                    dataAccess.ensureCapacity((long) (intIndex + 1) * 4);
-                    int beforeIntIndex = intIndex;
-                    intIndex = store(subEntry, beforeIntIndex);
-                    if (intIndex == beforeIntIndex) {
-                        dataAccess.setInt(refPointer, 0);
+                    dataAccess.ensureCapacity((long) (intPointer + 1) * 4);
+                    int prevIntPointer = intPointer;
+                    intPointer = store(subEntry, prevIntPointer);
+                    if (intPointer == prevIntPointer) {
+                        dataAccess.setInt(pointer, 0);
                     } else {
-                        dataAccess.setInt(refPointer, beforeIntIndex);
+                        dataAccess.setInt(pointer, prevIntPointer);
                     }
                 }
             }
-            return intIndex;
+            return intPointer;
         }
     }
 
diff --git a/reader-gtfs/src/main/java/com/graphhopper/reader/gtfs/EmptyLocationIndex.java b/reader-gtfs/src/main/java/com/graphhopper/reader/gtfs/EmptyLocationIndex.java
index 4226826ea..fa317e853 100644
--- a/reader-gtfs/src/main/java/com/graphhopper/reader/gtfs/EmptyLocationIndex.java
+++ b/reader-gtfs/src/main/java/com/graphhopper/reader/gtfs/EmptyLocationIndex.java
@@ -21,6 +21,7 @@ package com.graphhopper.reader.gtfs;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.QueryResult;
+import com.graphhopper.util.shapes.BBox;
 
 class EmptyLocationIndex implements LocationIndex {
     @Override
@@ -38,6 +39,10 @@ class EmptyLocationIndex implements LocationIndex {
         return new QueryResult(lat, lon);
     }
 
+    @Override
+    public void query(BBox queryBBox, Visitor function) {
+    }
+
     @Override
     public LocationIndex setApproximation(boolean approxDist) {
         return this;
@@ -45,7 +50,6 @@ class EmptyLocationIndex implements LocationIndex {
 
     @Override
     public void setSegmentSize(int bytes) {
-
     }
 
     @Override
@@ -60,12 +64,10 @@ class EmptyLocationIndex implements LocationIndex {
 
     @Override
     public void flush() {
-
     }
 
     @Override
     public void close() {
-
     }
 
     @Override
diff --git a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
index 725af9b51..c2ccb4612 100644
--- a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
+++ b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
@@ -199,7 +199,7 @@ public class MiniGraphUI {
             Random rand = new Random();
 
             @Override
-            public void paintComponent(Graphics2D g2) {
+            public void paintComponent(final Graphics2D g2) {
                 clearGraphics(g2);
                 int locs = graph.getNodes();
                 Rectangle d = getBounds();
@@ -275,13 +275,38 @@ public class MiniGraphUI {
                     boolean fwd = edge.get(accessEnc);
                     boolean bwd = edge.getReverse(accessEnc);
                     float width = speed > 90 ? 1f : 0.8f;
-                    if (fwd && !bwd) {
-                        mg.plotDirectedEdge(g2, lat, lon, lat2, lon2, width);
-                    } else {
-                        mg.plotEdge(g2, lat, lon, lat2, lon2, width);
+                    PointList pl = edge.fetchWayGeometry(3);
+                    for (int i = 1; i < pl.size(); i++) {
+                        if (fwd && !bwd) {
+                            mg.plotDirectedEdge(g2, pl.getLatitude(i - 1), pl.getLongitude(i - 1), pl.getLatitude(i), pl.getLongitude(i), width);
+                        } else {
+                            mg.plotEdge(g2, pl.getLatitude(i - 1), pl.getLongitude(i - 1), pl.getLatitude(i), pl.getLongitude(i), width);
+                        }
                     }
                 }
 
+                index.query(graph.getBounds(), new LocationIndexTree.Visitor() {
+                    @Override
+                    public boolean isTileInfo() {
+                        return true;
+                    }
+
+                    @Override
+                    public void onTile(BBox bbox, int depth) {
+                        int width = Math.max(1, Math.min(4, 4 - depth));
+                        g2.setColor(Color.GRAY);
+                        mg.plotEdge(g2, bbox.minLat, bbox.minLon, bbox.minLat, bbox.maxLon, width);
+                        mg.plotEdge(g2, bbox.minLat, bbox.maxLon, bbox.maxLat, bbox.maxLon, width);
+                        mg.plotEdge(g2, bbox.maxLat, bbox.maxLon, bbox.maxLat, bbox.minLon, width);
+                        mg.plotEdge(g2, bbox.maxLat, bbox.minLon, bbox.minLat, bbox.minLon, width);
+                    }
+
+                    @Override
+                    public void onNode(int node) {
+                        // mg.plotNode(g2, node, Color.BLUE);
+                    }
+                });
+
                 g2.setColor(Color.WHITE);
                 g2.fillRect(0, 0, 1000, 20);
                 for (int i = 4; i < speedColors.length; i++) {
diff --git a/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java b/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java
index 9a39461cd..9b96379d2 100644
--- a/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java
+++ b/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java
@@ -33,6 +33,7 @@ import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.QueryResult;
 import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.Parameters;
+import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
 import org.locationtech.jts.geom.*;
 import org.locationtech.jts.index.strtree.STRtree;
@@ -58,7 +59,6 @@ public class PtIsochroneResource {
     private EncodingManager encodingManager;
     private GraphHopperStorage graphHopperStorage;
     private LocationIndex locationIndex;
-//    private final STRtree spatialIndex;
 
     private final Function<Label, Double> z = label -> (double) label.currentTime;
 
@@ -67,15 +67,6 @@ public class PtIsochroneResource {
         this.encodingManager = encodingManager;
         this.graphHopperStorage = graphHopperStorage;
         this.locationIndex = locationIndex;
-//        spatialIndex = new STRtree();
-//        PtFlagEncoder ptFlagEncoder = (PtFlagEncoder) encodingManager.getEncoder("pt");
-//        AllEdgesIterator allEdges = graphHopperStorage.getAllEdges();
-//        while (allEdges.next()) {
-//            if (ptFlagEncoder.getEdgeType(allEdges.getFlags()) == GtfsStorage.EdgeType.HIGHWAY) {
-//                LineString geom = allEdges.fetchWayGeometry(3).toLineString(false);
-//                spatialIndex.insert(geom.getEnvelopeInternal(), allEdges.getEdge());
-//            }
-//        }
     }
 
     public static class Response {
@@ -133,17 +124,16 @@ public class PtIsochroneResource {
             router.calcLabelsAndNeighbors(queryResult.getClosestNode(), -1, initialTime, blockedRouteTypes, sptVisitor, label -> label.currentTime <= targetZ);
             MultiPoint exploredPointsAndNeighbors = geometryFactory.createMultiPointFromCoords(z1.keySet().toArray(new Coordinate[0]));
 
-            // This is what we need to do once we can do bounding-box queries on our spatial index.
-            // Then it should be impossible for unreachable encroaching points to not be found.
-
-//            spatialIndex.query(exploredPointsAndNeighbors.getEnvelopeInternal(), edgeId -> {
-//                EdgeIteratorState e = graphHopperStorage.getEdgeIteratorState((int) edgeId, Integer.MIN_VALUE);
-//                Coordinate nodeCoordinate = new Coordinate(nodeAccess.getLongitude(e.getBaseNode()), nodeAccess.getLatitude(e.getBaseNode()));
-//                z1.merge(nodeCoordinate, Double.MAX_VALUE, Math::min);
-//                nodeCoordinate = new Coordinate(nodeAccess.getLongitude(e.getAdjNode()), nodeAccess.getLatitude(e.getAdjNode()));
-//                z1.merge(nodeCoordinate, Double.MAX_VALUE, Math::min);
-//            });
-//            exploredPointsAndNeighbors = geometryFactory.createMultiPointFromCoords(z1.keySet().toArray(new Coordinate[0]));
+            // Get at least all nodes within our bounding box (I think convex hull would be enough.)
+            // I think then we should have all possible encroaching points. (Proof needed.)
+            locationIndex.query(BBox.fromEnvelope(exploredPointsAndNeighbors.getEnvelopeInternal()), new LocationIndex.Visitor() {
+                @Override
+                public void onNode(int nodeId) {
+                    Coordinate nodeCoordinate = new Coordinate(nodeAccess.getLongitude(nodeId), nodeAccess.getLatitude(nodeId));
+                    z1.merge(nodeCoordinate, Double.MAX_VALUE, Math::min);
+                }
+            });
+            exploredPointsAndNeighbors = geometryFactory.createMultiPointFromCoords(z1.keySet().toArray(new Coordinate[0]));
 
             CoordinateList siteCoords = DelaunayTriangulationBuilder.extractUniqueCoordinates(exploredPointsAndNeighbors);
             List<ConstraintVertex> constraintVertices = new ArrayList<>();


Test patch:
diff --git a/api/src/test/java/com/graphhopper/util/shapes/BBoxTest.java b/api/src/test/java/com/graphhopper/util/shapes/BBoxTest.java
index dc77fb80d..321e473b5 100644
--- a/api/src/test/java/com/graphhopper/util/shapes/BBoxTest.java
+++ b/api/src/test/java/com/graphhopper/util/shapes/BBoxTest.java
@@ -71,18 +71,18 @@ public class BBoxTest {
         //
 
         // use ISO 19115 standard (minLon, maxLon followed by minLat(south!),maxLat)
-        assertTrue(new BBox(12, 15, 12, 15).intersect(new BBox(13, 14, 11, 16)));
-        // assertFalse(new BBox(15, 12, 12, 15).intersect(new BBox(16, 15, 11, 14)));
+        assertTrue(new BBox(12, 15, 12, 15).intersects(new BBox(13, 14, 11, 16)));
+        // assertFalse(new BBox(15, 12, 12, 15).intersects(new BBox(16, 15, 11, 14)));
 
         // DOES NOT WORK: use bottom to top coord for lat
-        // assertFalse(new BBox(6, 2, 11, 6).intersect(new BBox(5, 3, 12, 5)));
+        // assertFalse(new BBox(6, 2, 11, 6).intersects(new BBox(5, 3, 12, 5)));
         // so, use bottom-left and top-right corner!
-        assertTrue(new BBox(2, 6, 6, 11).intersect(new BBox(3, 5, 5, 12)));
+        assertTrue(new BBox(2, 6, 6, 11).intersects(new BBox(3, 5, 5, 12)));
 
         // DOES NOT WORK: use bottom to top coord for lat and right to left for lon
-        // assertFalse(new BBox(6, 11, 11, 6).intersect(new BBox(5, 10, 12, 7)));
+        // assertFalse(new BBox(6, 11, 11, 6).intersects(new BBox(5, 10, 12, 7)));
         // so, use bottom-right and top-left corner
-        assertTrue(new BBox(6, 11, 6, 11).intersect(new BBox(7, 10, 5, 12)));
+        assertTrue(new BBox(6, 11, 6, 11).intersects(new BBox(7, 10, 5, 12)));
     }
 
     @Test
@@ -109,37 +109,37 @@ public class BBoxTest {
     public void testBasicJavaOverload() {
         new BBox(2, 4, 0, 1) {
             @Override
-            public boolean intersect(Circle c) {
+            public boolean intersects(Circle c) {
                 assertTrue(true);
-                return super.intersect(c);
+                return super.intersects(c);
             }
 
             @Override
-            public boolean intersect(Shape c) {
+            public boolean intersects(Shape c) {
                 assertTrue(false);
                 return true;
             }
 
             @Override
-            public boolean intersect(BBox c) {
+            public boolean intersects(BBox c) {
                 assertTrue(false);
                 return true;
             }
-        }.intersect(new Circle(1, 2, 3) {
+        }.intersects(new Circle(1, 2, 3) {
             @Override
-            public boolean intersect(Circle c) {
+            public boolean intersects(Circle c) {
                 assertTrue(false);
                 return true;
             }
 
             @Override
-            public boolean intersect(Shape b) {
+            public boolean intersects(Shape b) {
                 assertTrue(false);
                 return true;
             }
 
             @Override
-            public boolean intersect(BBox b) {
+            public boolean intersects(BBox b) {
                 assertTrue(true);
                 return true;
             }
diff --git a/api/src/test/java/com/graphhopper/util/shapes/CircleTest.java b/api/src/test/java/com/graphhopper/util/shapes/CircleTest.java
index 819a944be..eaf6e1809 100644
--- a/api/src/test/java/com/graphhopper/util/shapes/CircleTest.java
+++ b/api/src/test/java/com/graphhopper/util/shapes/CircleTest.java
@@ -29,17 +29,17 @@ import static org.junit.Assert.assertTrue;
 public class CircleTest {
     @Test
     public void testIntersectCircleCircle() {
-        assertTrue(new Circle(0, 0, 80000).intersect(new Circle(1, 1, 80000)));
-        assertFalse(new Circle(0, 0, 75000).intersect(new Circle(1, 1, 80000)));
+        assertTrue(new Circle(0, 0, 80000).intersects(new Circle(1, 1, 80000)));
+        assertFalse(new Circle(0, 0, 75000).intersects(new Circle(1, 1, 80000)));
     }
 
     @Test
     public void testIntersectCircleBBox() {
-        assertTrue(new Circle(10, 10, 120000).intersect(new BBox(9, 11, 8, 9)));
-        assertTrue(new BBox(9, 11, 8, 9).intersect(new Circle(10, 10, 120000)));
+        assertTrue(new Circle(10, 10, 120000).intersects(new BBox(9, 11, 8, 9)));
+        assertTrue(new BBox(9, 11, 8, 9).intersects(new Circle(10, 10, 120000)));
 
-        assertFalse(new Circle(10, 10, 110000).intersect(new BBox(9, 11, 8, 9)));
-        assertFalse(new BBox(9, 11, 8, 9).intersect(new Circle(10, 10, 110000)));
+        assertFalse(new Circle(10, 10, 110000).intersects(new BBox(9, 11, 8, 9)));
+        assertFalse(new BBox(9, 11, 8, 9).intersects(new Circle(10, 10, 110000)));
     }
 
     @Test
diff --git a/client-hc/src/test/java/com/graphhopper/api/GraphHopperWebIT.java b/client-hc/src/test/java/com/graphhopper/api/GraphHopperWebIT.java
index 5cc0612da..cad859052 100644
--- a/client-hc/src/test/java/com/graphhopper/api/GraphHopperWebIT.java
+++ b/client-hc/src/test/java/com/graphhopper/api/GraphHopperWebIT.java
@@ -87,7 +87,7 @@ public class GraphHopperWebIT {
         path = paths.get(0);
         isBetween(20, 30, path.getPoints().size());
         isBetween(800, 900, path.getDistance());
-        assertTrue("expected: " + path.getDescription().get(0), Arrays.asList("Jacobistraße", "Ludwig-Gercke-Straße", "Eichendorffplatz").contains(path.getDescription().get(0)));
+        assertTrue("expected: " + path.getDescription().get(0), Arrays.asList("Jacobistraße", "Bismarckstraße", "Ludwig-Gercke-Straße", "Eichendorffplatz").contains(path.getDescription().get(0)));
     }
 
     @Test
diff --git a/core/src/test/java/com/graphhopper/routing/PathTest.java b/core/src/test/java/com/graphhopper/routing/PathTest.java
index 294510d7a..dab93e442 100644
--- a/core/src/test/java/com/graphhopper/routing/PathTest.java
+++ b/core/src/test/java/com/graphhopper/routing/PathTest.java
@@ -93,7 +93,7 @@ public class PathTest {
         assertEquals("continue", tmp.getTurnDescription(tr));
 //        assertEquals("[0, 6]", tmp.get("interval").toString());
         assertEquals(6, tmp.getLength());
-        System.out.println(tmp.getPoints());
+//        System.out.println(tmp.getPoints());
 
 
         tmp = instr.get(1);
@@ -102,7 +102,7 @@ public class PathTest {
         assertEquals("arrive at destination", tmp.getTurnDescription(tr));
 //        assertEquals("[6, 6]", tmp.get("interval").toString());
         assertEquals(0, tmp.getLength());
-        System.out.println(tmp.getPoints());
+//        System.out.println(tmp.getPoints());
 
         int acc = 0;
         for (Instruction instruction : instr) {
diff --git a/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java b/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java
index bc35fe84d..729c4e255 100644
--- a/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java
+++ b/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java
@@ -26,6 +26,7 @@ import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.storage.RAMDirectory;
 import com.graphhopper.util.*;
+import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
 import org.junit.Test;
 
@@ -34,8 +35,7 @@ import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
 
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.*;
 
 /**
  * @author Peter Karich
@@ -104,6 +104,22 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         assertEquals(new GHPoint(-0.441624, 0.317259), res.getSnappedPoint());
     }
 
+    @Test
+    public void testQuery() {
+        Graph graph = createTestGraph2();
+        LocationIndexTree index = createIndex(graph, 500);
+        final ArrayList set = new ArrayList();
+        index.query(new BBox(11.57314, 11.57614, 49.94553, 49.94853), new LocationIndex.Visitor() {
+            @Override
+            public void onNode(int nodeId) {
+                set.add(nodeId);
+            }
+        });
+        assertEquals(17, set.size());
+        assertTrue(set.containsAll(Arrays.asList(2, 3, 4, 5, 6)));
+        assertFalse(set.containsAll(Arrays.asList(17, 18, 25, 30)));
+    }
+
     @Test
     public void testInMemIndex() {
         Graph graph = createTestGraph(encodingManager);
@@ -196,11 +212,12 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         LocationIndexTree index = createIndexNoPrepare(createTestGraph(encodingManager), 10000);
         index.prepareAlgo();
         LocationIndexTree.InMemConstructionIndex inMemIndex = index.getPrepareInMemIndex();
-        assertEquals(IntArrayList.from(new int[]{64, 4}), index.getEntries());
+        assertEquals(IntArrayList.from(new int[]{16, 4, 4}), index.getEntries());
 
-        assertEquals(33, inMemIndex.getEntriesOf(0).size());
-        assertEquals(69, inMemIndex.getEntriesOf(1).size());
-        assertEquals(0, inMemIndex.getEntriesOf(2).size());
+        assertEquals(13, inMemIndex.getEntriesOf(0).size());
+        assertEquals(33, inMemIndex.getEntriesOf(1).size());
+        assertEquals(69, inMemIndex.getEntriesOf(2).size());
+        assertEquals(0, inMemIndex.getEntriesOf(3).size());
 
         index.dataAccess.create(1024);
         inMemIndex.store(inMemIndex.root, LocationIndexTree.START_POINTER);
@@ -213,7 +230,7 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     @Test
     public void testReverseSpatialKey() {
         LocationIndexTree index = createIndex(createTestGraph(encodingManager), 200);
-        assertEquals(IntArrayList.from(new int[]{64, 64, 64, 4}), index.getEntries());
+        assertEquals(IntArrayList.from(new int[]{16, 16, 16, 16, 4, 4}), index.getEntries());
 
         // 10111110111110101010
         String str44 = "00000000000000000000000000000000000000000000";
diff --git a/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java b/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
index d2a20ba24..31a5fed24 100644
--- a/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
+++ b/reader-osm/src/test/java/com/graphhopper/reader/osm/GraphHopperOSMTest.java
@@ -32,11 +32,10 @@ import com.graphhopper.routing.weighting.AbstractWeighting;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.*;
-import com.graphhopper.util.CmdArgs;
-import com.graphhopper.util.Helper;
-import com.graphhopper.util.Instruction;
-import com.graphhopper.util.Parameters;
+import com.graphhopper.storage.index.LocationIndexTree;
+import com.graphhopper.util.*;
 import com.graphhopper.util.Parameters.Routing;
+import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
 import org.junit.After;
 import org.junit.Before;
@@ -44,10 +43,7 @@ import org.junit.Test;
 
 import java.io.File;
 import java.io.IOException;
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.HashMap;
-import java.util.List;
+import java.util.*;
 import java.util.concurrent.CountDownLatch;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicInteger;
@@ -149,6 +145,60 @@ public class GraphHopperOSMTest {
         gh.close();
     }
 
+    @Test
+    public void testQueryLocationIndexWithBBox() {
+        GraphHopper gh = new GraphHopperOSM().setStoreOnFlush(true).
+                setEncodingManager(EncodingManager.create("car")).
+                setCHEnabled(false).
+                setGraphHopperLocation("./target/monacotmp-gh").
+                setDataReaderFile("../core/files/monaco.osm.gz");
+        gh.importOrLoad();
+
+        final NodeAccess na = gh.getGraphHopperStorage().getNodeAccess();
+        final Collection<Integer> indexNodeList = new TreeSet<>();
+        LocationIndexTree index = (LocationIndexTree) gh.getLocationIndex();
+        final EdgeExplorer edgeExplorer = gh.getGraphHopperStorage().createEdgeExplorer();
+        final BBox bbox = new BBox(7.422, 7.429, 43.729, 43.734);
+        index.query(bbox, new LocationIndexTree.EdgeVisitor(edgeExplorer) {
+            @Override
+            public void onTile(BBox bbox, int width) {
+            }
+
+            @Override
+            public void onEdge(EdgeIteratorState edge, int nodeA, int nodeB) {
+                for (int i = 0; i < 2; i++) {
+                    int nodeId = i == 0 ? nodeA : nodeB;
+                    double lat = na.getLatitude(nodeId);
+                    double lon = na.getLongitude(nodeId);
+                    if (bbox.contains(lat, lon))
+                        indexNodeList.add(nodeId);
+                }
+            }
+        });
+
+        assertEquals(57, indexNodeList.size());
+        for (int nodeId : indexNodeList) {
+            if (!bbox.contains(na.getLatitude(nodeId), na.getLongitude(nodeId)))
+                fail("bbox " + bbox + " should contain " + nodeId);
+        }
+
+        final Collection<Integer> bfsNodeList = new TreeSet<>();
+        new BreadthFirstSearch() {
+            @Override
+            protected boolean goFurther(int nodeId) {
+                double lat = na.getLatitude(nodeId);
+                double lon = na.getLongitude(nodeId);
+                if (bbox.contains(lat, lon))
+                    bfsNodeList.add(nodeId);
+
+                return true;
+            }
+        }.start(edgeExplorer, index.findClosest(43.731, 7.425, EdgeFilter.ALL_EDGES).getClosestNode());
+
+        assertTrue("index size: " + indexNodeList.size() + ", bfs size: " + bfsNodeList.size(), indexNodeList.size() >= bfsNodeList.size());
+        assertTrue("index size: " + indexNodeList.size() + ", bfs size: " + bfsNodeList.size(), indexNodeList.containsAll(bfsNodeList));
+    }
+
     @Test
     public void testLoadingWithDifferentCHConfig_issue471() {
         // with CH should not be loadable without CH configured