Repository: graphhopper/graphhopper
Pull request #2216 (2020-12-18 00:10:27)

LocationIndexTree cleanup
Project:

- [x] - Store edge ids, not node ids, because that's what's conceptually already happening
- [x] - Remove findNClosest; use the much better defined bounding box query instead. It doesn't matter at all that the query shape is then a square, not a circle. A ton of code goes away.
- [ ] - Clarify what the parameters mean, particularly "precision" and "maxRegionSearch". I mean, if you have high precision aka super-small tiles, then you possibly have to search many tiles to find a nearest neighbor. You can't have it both ways. But that's okay because if there are no bugs, a low "precision" doesn't actually change the results, it just changes the performance. Etc. Actually, "precision" and "maxRegionSearch" *together* are something like a precision, because that determines how far away from a street I can click and still get a result.
- [x] - Possibly:
- [x]   - Use the line scan algorithm that we want to be using (put the line in all the tiles that it intersects)
- [x]   - Why don't we do the calculations for that in pixels, like the original line scan algorithms? We are already using fixed-size cells, aka pixels, with fixed-length spatial keys, aka pixel coordinates. Our line scan can just take point a and point b directly as spatial keys, and emit all pixels on the line as spatial keys as well.

michaz: Done -- LocationIndex now stores edgeIds, and `findNClosest` is gone. MapMatching now does a bounding box query (expecting that it's correct, so modulo the open Bresenham problem), and does the "snapping" in its own code. It's even a bit faster, apparently.
easbar: This sounds great :+1: . We probably need to adjust/fix measurement as well. Currently it fails with this:

```sh
2020-12-20 02:59:49,335 [main] ERROR com.graphhopper.tools.Measurement - Problem while measuring /ext_data/tmp/measurement-small-gh
java.lang.ArrayIndexOutOfBoundsException: Index 35 out of bounds for length 32
	at com.graphhopper.storage.RAMIntDataAccess.getInt(RAMIntDataAccess.java:208)
	at com.graphhopper.storage.GHNodeAccess.getLatitude(GHNodeAccess.java:66)
	at com.graphhopper.storage.GHNodeAccess.getLat(GHNodeAccess.java:89)
	at com.graphhopper.storage.index.LocationIndexTree.calcMinDistance(LocationIndexTree.java:565)
	at com.graphhopper.storage.index.LocationIndexTree.findNetworkEntries(LocationIndexTree.java:545)
	at com.graphhopper.storage.index.LocationIndexTree.findClosest(LocationIndexTree.java:589)
	at com.graphhopper.tools.Measurement.lambda$printLocationIndexQuery$1(Measurement.java:461)
	at com.graphhopper.util.MiniPerfTest.start(MiniPerfTest.java:46)
	at com.graphhopper.tools.Measurement.printLocationIndexQuery(Measurement.java:458)
	at com.graphhopper.tools.Measurement.start(Measurement.java:207)
	at com.graphhopper.tools.Measurement.main(Measurement.java:93)
```

See `Measurement#printLocationIndexQuery`.
michaz: Oops! No, that was a proper mistake by me, which is only found by the measurement and not by the tests. :-} Will fix.
michaz: One round trip routing test now finds a slightly different round trip, but that's okay, I guess, if it's also a nice round trip.

Patch:
diff --git a/core/src/main/java/com/graphhopper/coll/CompressedArray.java b/core/src/main/java/com/graphhopper/coll/CompressedArray.java
deleted file mode 100644
index e0fa131f6..000000000
--- a/core/src/main/java/com/graphhopper/coll/CompressedArray.java
+++ /dev/null
@@ -1,186 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.coll;
-
-import com.graphhopper.geohash.SpatialKeyAlgo;
-import com.graphhopper.storage.VLongStorage;
-import com.graphhopper.util.Helper;
-import com.graphhopper.util.shapes.GHPoint;
-
-import java.io.ByteArrayOutputStream;
-import java.util.ArrayList;
-import java.util.List;
-import java.util.zip.DataFormatException;
-import java.util.zip.Deflater;
-import java.util.zip.Inflater;
-
-/**
- * Stores the entries in compressed segments. The methods de(compress) are taken from Lucene
- * CompressionTools. Before accessing the stored values be sure you called flush.
- * <p>
- *
- * @author Peter Karich
- */
-public class CompressedArray {
-    private int compressionLevel = 5;
-    private VLongStorage currentWriter;
-    private int currentEntry = 0;
-    private List<byte[]> segments;
-    private int entriesPerSegment;
-    private int approxBytesPerEntry;
-    private SpatialKeyAlgo algo;
-
-    public CompressedArray() {
-        this(100, 200, 4);
-    }
-
-    /**
-     * @param _segments           initialize with this number of segments
-     * @param entriesPerSeg       a static number which sets the entries per segment
-     * @param approxBytesPerEntry an *approximate* number (as entries can have different lengths)
-     */
-    public CompressedArray(int _segments, int entriesPerSeg, int approxBytesPerEntry) {
-        if (entriesPerSeg < 1) {
-            throw new IllegalArgumentException("at least one entry should be per segment");
-        }
-        this.entriesPerSegment = entriesPerSeg;
-        this.approxBytesPerEntry = approxBytesPerEntry;
-        segments = new ArrayList<>(_segments);
-        algo = new SpatialKeyAlgo(63);
-    }
-
-    /**
-     * Compresses the specified byte range using the specified compressionLevel (constants are
-     * defined in java.util.zip.Deflater).
-     */
-    public static byte[] compress(byte[] value, int offset, int length, int compressionLevel) {
-        /* Create an expandable byte array to hold the compressed data.
-         * You cannot use an array that's the same size as the original because
-         * there is no guarantee that the compressed data will be smaller than
-         * the uncompressed data. */
-        ByteArrayOutputStream bos = new ByteArrayOutputStream(length);
-        Deflater compressor = new Deflater();
-        try {
-            compressor.setLevel(compressionLevel);
-            compressor.setInput(value, offset, length);
-            compressor.finish();
-            final byte[] buf = new byte[1024];
-            while (!compressor.finished()) {
-                int count = compressor.deflate(buf);
-                bos.write(buf, 0, count);
-            }
-        } finally {
-            compressor.end();
-        }
-        return bos.toByteArray();
-    }
-
-    /**
-     * Decompress the byte array previously returned by compress
-     */
-    public static byte[] decompress(byte[] value) throws DataFormatException {
-        // Create an expandable byte array to hold the decompressed data
-        ByteArrayOutputStream bos = new ByteArrayOutputStream(value.length);
-        Inflater decompressor = new Inflater();
-        try {
-            decompressor.setInput(value);
-            final byte[] buf = new byte[1024];
-            while (!decompressor.finished()) {
-                int count = decompressor.inflate(buf);
-                bos.write(buf, 0, count);
-            }
-        } finally {
-            decompressor.end();
-        }
-
-        return bos.toByteArray();
-    }
-
-    public CompressedArray setCompressionLevel(int compressionLevel) {
-        this.compressionLevel = compressionLevel;
-        return this;
-    }
-
-    public void write(double lat, double lon) {
-        try {
-            if (currentWriter == null)
-                currentWriter = new VLongStorage(entriesPerSegment * approxBytesPerEntry);
-
-            long latlon = algo.encode(new GHPoint(lat, lon));
-            // we cannot use delta encoding as vlong does not support negative numbers
-            // but compression of vlong is much more efficient than directly storing the integers
-            currentWriter.writeVLong(latlon);
-            currentEntry++;
-            if (currentEntry >= entriesPerSegment) {
-                flush();
-            }
-        } catch (Exception ex) {
-            throw new RuntimeException(ex);
-        }
-    }
-
-    public GHPoint get(long index) {
-        int segmentNo = (int) (index / entriesPerSegment);
-        int entry = (int) (index % entriesPerSegment);
-        try {
-            if (segmentNo >= segments.size()) {
-                return null;
-            }
-            byte[] bytes = segments.get(segmentNo);
-            VLongStorage store = new VLongStorage(decompress(bytes));
-            long len = store.getLength();
-            for (int i = 0; store.getPosition() < len; i++) {
-                long latlon = store.readVLong();
-                if (i == entry) {
-                    GHPoint point = new GHPoint();
-                    algo.decode(latlon, point);
-                    return point;
-                }
-            }
-            return null;
-        } catch (ArrayIndexOutOfBoundsException ex) {
-            throw new RuntimeException("index " + index + "=> segNo:" + segmentNo + ", entry=" + entry
-                    + ", segments:" + segments.size(), ex);
-        } catch (Exception ex) {
-            throw new RuntimeException(ex);
-        }
-    }
-
-    public void flush() {
-        if (currentWriter == null) {
-            return;
-        }
-        try {
-            currentWriter.trimToSize();
-            byte[] input = currentWriter.getBytes();
-            segments.add(compress(input, 0, input.length, compressionLevel));
-            currentWriter = null;
-            currentEntry = 0;
-        } catch (Exception ex) {
-            throw new RuntimeException(ex);
-        }
-    }
-
-    public float calcMemInMB() {
-        long bytes = 0;
-        for (int i = 0; i < segments.size(); i++) {
-            bytes += segments.get(i).length;
-        }
-        return (float) (segments.size() * 4 + bytes) / Helper.MB;
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/geohash/KeyAlgo.java b/core/src/main/java/com/graphhopper/geohash/KeyAlgo.java
deleted file mode 100644
index a7feef11c..000000000
--- a/core/src/main/java/com/graphhopper/geohash/KeyAlgo.java
+++ /dev/null
@@ -1,41 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.geohash;
-
-import com.graphhopper.util.shapes.GHPoint;
-
-/**
- * Defines the mapping between a one dimensional 'number' and a point (lat, lon) which is limited to
- * a defined bounds.
- * <p>
- *
- * @author Peter Karich
- */
-public interface KeyAlgo {
-
-    /**
-     * Sets the bounds of the underlying key algorithm.
-     */
-    KeyAlgo setBounds(double minLonInit, double maxLonInit, double minLatInit, double maxLatInit);
-
-    long encode(GHPoint coord);
-
-    long encode(double lat, double lon);
-
-    void decode(long spatialKey, GHPoint latLon);
-}
diff --git a/core/src/main/java/com/graphhopper/geohash/LinearKeyAlgo.java b/core/src/main/java/com/graphhopper/geohash/LinearKeyAlgo.java
deleted file mode 100644
index 67ec354eb..000000000
--- a/core/src/main/java/com/graphhopper/geohash/LinearKeyAlgo.java
+++ /dev/null
@@ -1,112 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.geohash;
-
-import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
-
-/**
- * This class maps lat,lon to a (tile)number unlike SpatialKeyAlgo.
- * <p>
- *
- * @author Peter Karich
- */
-// A 4*3 precision linear key will look like
-//  
-//     |----|----|----|----|
-//     |   0|   1|   2|   3|
-//     |----|----|----|----|
-// lat |   4|   5|   6|   7|
-//     |----|----|----|----|
-//     |   8|   9|  10|  11|
-//     |----|----|----|----|
-//
-//              lon
-public class LinearKeyAlgo implements KeyAlgo {
-    private static final double C = 1 - 1e-15;
-    private final int latUnits, lonUnits;
-    private BBox bounds;
-    private double latDelta, lonDelta;
-
-    public LinearKeyAlgo(int latUnits, int lonUnits) {
-        this.latUnits = latUnits;
-        this.lonUnits = lonUnits;
-        setWorldBounds();
-    }
-
-    @Override
-    public LinearKeyAlgo setBounds(double minLonInit, double maxLonInit, double minLatInit, double maxLatInit) {
-        bounds = new BBox(minLonInit, maxLonInit, minLatInit, maxLatInit);
-        latDelta = (bounds.maxLat - bounds.minLat) / latUnits;
-        lonDelta = (bounds.maxLon - bounds.minLon) / lonUnits;
-        return this;
-    }
-
-    public LinearKeyAlgo setBounds(BBox bounds) {
-        setBounds(bounds.minLon, bounds.maxLon, bounds.minLat, bounds.maxLat);
-        return this;
-    }
-
-    protected void setWorldBounds() {
-        setBounds(-180, 180, -90, 90);
-    }
-
-    @Override
-    public long encode(GHPoint coord) {
-        return encode(coord.lat, coord.lon);
-    }
-
-    /**
-     * Take latitude and longitude as input.
-     * <p>
-     *
-     * @return the linear key
-     */
-    @Override
-    public final long encode(double lat, double lon) {
-        lat = Math.min(Math.max(lat, bounds.minLat), bounds.maxLat);
-        lon = Math.min(Math.max(lon, bounds.minLon), bounds.maxLon);
-        // introduce a minor correction to round to lower grid entry!
-        long latIndex = (long) ((lat - bounds.minLat) / latDelta * C);
-        long lonIndex = (long) ((lon - bounds.minLon) / lonDelta * C);
-        return latIndex * lonUnits + lonIndex;
-    }
-
-    /**
-     * This method returns latitude and longitude via latLon - calculated from specified linearKey
-     * <p>
-     *
-     * @param linearKey is the input
-     */
-    @Override
-    public final void decode(long linearKey, GHPoint latLon) {
-        double lat = linearKey / lonUnits * latDelta + bounds.minLat;
-        double lon = linearKey % lonUnits * lonDelta + bounds.minLon;
-        latLon.lat = lat + latDelta / 2;
-        latLon.lon = lon + lonDelta / 2;
-    }
-
-    public double getLatDelta() {
-        return latDelta;
-    }
-
-    public double getLonDelta() {
-        return lonDelta;
-    }
-
-}
diff --git a/core/src/main/java/com/graphhopper/geohash/SpatialKeyAlgo.java b/core/src/main/java/com/graphhopper/geohash/SpatialKeyAlgo.java
index 96cfe144a..b5d0aa4ac 100644
--- a/core/src/main/java/com/graphhopper/geohash/SpatialKeyAlgo.java
+++ b/core/src/main/java/com/graphhopper/geohash/SpatialKeyAlgo.java
@@ -18,47 +18,34 @@
 package com.graphhopper.geohash;
 
 import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
 
 /**
- * This class implements the idea of a geohash but in 'binary form' - to avoid confusion this is
- * called 'spatial key'. The idea of mixing the latitude and longitude is also taken to allow
- * removing the insignificant (right side) bits to make a geo-query or the coordinate less precise.
- * E.g. for a 3 bit precision the spatial key would need 6 bits and look like:
- * <p>
- * lat0 lon0 | lat1 lon1 | lat2 lon2
- * <p>
- * This works similar to how BIG endianness works for bytes to int packing. Detailed information is
- * available in this blog post:
+ * This class implements the idea of a geohash but without a string representation - to avoid confusion, this is
+ * called 'spatial key'.
+ *
+ * Detailed information is available in this blog post:
+ *
  * http://karussell.wordpress.com/2012/05/23/spatial-keys-memory-efficient-geohashes/
  * <p>
- * The bits are usable as key for hash tables like our SpatialKeyHashtable or for a spatial tree
- * like QuadTreeSimple. Also the binary form makes it relative simple for implementations using this
- * encoding scheme to expand to arbitrary dimension (e.g. shifting n-times if n would be the
- * dimension).
+ * The hash can be used as a key for hash tables. When you organize the grid as a quad tree,
+ * it resembles the path down the tree to reach the cell that it encodes. That's how it is used in
+ * LocationIndexTree.
  * <p>
  * A 32 bit representation has a precision of approx 600 meters = 40000/2^16
  * <p>
- * There are different possibilities how to handle different precision and order of bits. Either:
- * <p>
- * lat0 lon0 | lat1 lon1 | lat2 lon2
- * <p>
- * 0 0 | lat0 lon0 | lat1 lon1
- * <p>
- * as it is done now. Advantage: A single shift is only necessary to make it less precise. Or:
- * <p>
- * lat2 lon2 | lat1 lon1 | lat0 lon0
- * <p>
- * 0 0 | lat1 lon1 | lat0 lon0
- * <p>
- * Advantage: the bit mask to get lat0 lon0 is simple: 000..0011 and independent of the precision!
- * But when stored e.g. as int one would need to (left) shift several times if precision is only
- * 3bits.
- * <p>
+ *
+ * Implementation:
+ * - From the query point and the grid parameters, calculate (integer) coordinates (x,y) of the cell
+ *   the query point is in, using simple arithmetics.
+ * - Use a lookup table to interleave the bits of (x,y) to get the cell number, which is the spatial key.
+ *   See the drawing below. This is called a Z-order curve (because of the path you get when you follow
+ *   increasing cell numbers through the grid), or Morton code.
  *
  * @author Peter Karich
+ * @author Michael Zilske
  */
-// A 2 bit precision spatial key could look like
+
+// A 2 bit (per axis) spatial key could look like
 // 
 //  |----|----|----|----|
 //  |1010|1011|1110|1111|
@@ -71,30 +58,28 @@ import com.graphhopper.util.shapes.GHPoint;
 //  |----|----|----|----|
 //            |
 //  lon0 == 0 | lon0 == 1
-public class SpatialKeyAlgo implements KeyAlgo {
-    private BBox bbox;
-    private int allBits;
-    private long initialBits;
+public class SpatialKeyAlgo {
+    private final int parts;
+    private final int allBits;
+    private final BBox bbox;
+    private final double deltaY;
+    private final double deltaX;
 
     /**
      * @param allBits how many bits should be used for the spatial key when encoding/decoding
      */
-    public SpatialKeyAlgo(int allBits) {
-        myinit(allBits);
-    }
-
-    private void myinit(int allBits) {
-        if (allBits > 64)
-            throw new IllegalStateException("allBits is too big and does not fit into 8 bytes");
+    public SpatialKeyAlgo(int allBits, BBox bounds) {
+        if (allBits > 48)
+            throw new IllegalStateException("allBits is too big for this implementation");
 
         if (allBits <= 0)
             throw new IllegalStateException("allBits must be positive");
 
-//        if ((allBits & 0x1) == 1)
-//            throw new IllegalStateException("allBits needs to be even to use the same amount for lat and lon");
         this.allBits = allBits;
-        initialBits = 1L << (allBits - 1);
-        setWorldBounds();
+        parts = (int) Math.pow(2, allBits / 2);
+        bbox = bounds;
+        deltaY = (bbox.maxLat - bbox.minLat) / parts;
+        deltaX = (bbox.maxLon - bbox.minLon) / parts;
     }
 
     /**
@@ -104,132 +89,148 @@ public class SpatialKeyAlgo implements KeyAlgo {
         return allBits;
     }
 
-    public int getExactPrecision() {
-        // 360 / 2^(allBits/2) = 1/precision
-        int p = (int) (Math.pow(2, allBits) / 360);
-        // no rounding error
-        p++;
-        return (int) Math.log10(p);
+    public final long encodeLatLon(double lat, double lon) {
+        return encode(x(lon), y(lat));
     }
 
-    public SpatialKeyAlgo bounds(BBox box) {
-        bbox = box.clone();
-        return this;
+    public int y(double lat) {
+        // Bounding this with parts - 1 or 0 only concerns the case where we are exactly on the bounding box.
+        // (The next cell would already start there..)
+        // (Or other situations, mostly in tests, where we actually run out of the bounding box.)
+        return Math.max(0, Math.min((int) ((lat - bbox.minLat) / deltaY), parts - 1));
     }
 
-    @Override
-    public SpatialKeyAlgo setBounds(double minLonInit, double maxLonInit, double minLatInit, double maxLatInit) {
-        bounds(new BBox(minLonInit, maxLonInit, minLatInit, maxLatInit));
-        return this;
+    public int x(double lon) {
+        // Bounding this with parts - 1 or 0 only concerns the case where we are exactly on the bounding box.
+        // (The next cell would already start there..)
+        // (Or other situations, mostly in tests, where we actually run out of the bounding box.)
+        return Math.max(0, Math.min((int) ((lon - bbox.minLon) / deltaX), parts - 1));
     }
 
-    protected void setWorldBounds() {
-        setBounds(-180, 180, -90, 90);
+    // https://github.com/eren-ck/MortonLib/blob/master/src/main/java/com/erenck/mortonlib/Morton2D.java
+
+    private final int MortonTable256[]
+            = {
+            0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
+            0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
+            0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
+            0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
+            0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
+            0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
+            0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
+            0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
+            0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
+            0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
+            0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
+            0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
+            0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
+            0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
+            0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
+            0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
+            0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
+            0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
+            0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
+            0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
+            0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
+            0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
+            0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
+            0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
+            0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
+            0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
+            0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
+            0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
+            0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
+            0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
+            0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
+            0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
+    };
+
+    private final int MortonTable256DecodeX[] = {
+            0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
+            4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
+            0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
+            4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
+            8, 9, 8, 9, 10, 11, 10, 11, 8, 9, 8, 9, 10, 11, 10, 11,
+            12, 13, 12, 13, 14, 15, 14, 15, 12, 13, 12, 13, 14, 15, 14, 15,
+            8, 9, 8, 9, 10, 11, 10, 11, 8, 9, 8, 9, 10, 11, 10, 11,
+            12, 13, 12, 13, 14, 15, 14, 15, 12, 13, 12, 13, 14, 15, 14, 15,
+            0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
+            4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
+            0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3,
+            4, 5, 4, 5, 6, 7, 6, 7, 4, 5, 4, 5, 6, 7, 6, 7,
+            8, 9, 8, 9, 10, 11, 10, 11, 8, 9, 8, 9, 10, 11, 10, 11,
+            12, 13, 12, 13, 14, 15, 14, 15, 12, 13, 12, 13, 14, 15, 14, 15,
+            8, 9, 8, 9, 10, 11, 10, 11, 8, 9, 8, 9, 10, 11, 10, 11,
+            12, 13, 12, 13, 14, 15, 14, 15, 12, 13, 12, 13, 14, 15, 14, 15
+    };
+
+    private final int MortonTable256DecodeY[] = {
+            0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
+            0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
+            4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
+            4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
+            0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
+            0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 3, 3,
+            4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
+            4, 4, 5, 5, 4, 4, 5, 5, 6, 6, 7, 7, 6, 6, 7, 7,
+            8, 8, 9, 9, 8, 8, 9, 9, 10, 10, 11, 11, 10, 10, 11, 11,
+            8, 8, 9, 9, 8, 8, 9, 9, 10, 10, 11, 11, 10, 10, 11, 11,
+            12, 12, 13, 13, 12, 12, 13, 13, 14, 14, 15, 15, 14, 14, 15, 15,
+            12, 12, 13, 13, 12, 12, 13, 13, 14, 14, 15, 15, 14, 14, 15, 15,
+            8, 8, 9, 9, 8, 8, 9, 9, 10, 10, 11, 11, 10, 10, 11, 11,
+            8, 8, 9, 9, 8, 8, 9, 9, 10, 10, 11, 11, 10, 10, 11, 11,
+            12, 12, 13, 13, 12, 12, 13, 13, 14, 14, 15, 15, 14, 14, 15, 15,
+            12, 12, 13, 13, 12, 12, 13, 13, 14, 14, 15, 15, 14, 14, 15, 15
+    };
+
+    public long encode(int x, int y) {
+        int EIGHTBITMASK = 0xff;
+        return (MortonTable256[(y >> 8) & EIGHTBITMASK] << 17
+                | MortonTable256[(x >> 8) & EIGHTBITMASK] << 16
+                | MortonTable256[y & EIGHTBITMASK] << 1
+                | MortonTable256[x & EIGHTBITMASK]);
     }
 
-    @Override
-    public long encode(GHPoint coord) {
-        return encode(coord.lat, coord.lon);
+    public int[] decode(long z) {
+        int[] result = new int[2];
+        // Morton codes up to 48 bits
+        if (z < Math.pow(2, 48)) {
+            result[0] = decodeHelper(z, MortonTable256DecodeX);
+            result[1] = decodeHelper(z, MortonTable256DecodeY);
+        }
+        return result;
     }
 
-    /**
-     * Take latitude and longitude as input.
-     * <p>
-     *
-     * @return the spatial key
-     */
-    @Override
-    public final long encode(double lat, double lon) {
-        // PERFORMANCE: int operations would be faster than double (for further comparison etc)
-        // but we would need 'long' because 'int factorForPrecision' is not enough (problem: coord!=decode(encode(coord)) see testBijection)
-        // and 'long'-ops are more expensive than double (at least on 32bit systems)
-        long hash = 0;
-        double minLatTmp = bbox.minLat;
-        double maxLatTmp = bbox.maxLat;
-        double minLonTmp = bbox.minLon;
-        double maxLonTmp = bbox.maxLon;
-        int i = 0;
-        while (true) {
-            if (minLatTmp < maxLatTmp) {
-                double midLat = (minLatTmp + maxLatTmp) / 2;
-                if (lat < midLat) {
-                    maxLatTmp = midLat;
-                } else {
-                    hash |= 1;
-                    minLatTmp = midLat;
-                }
-            }
-            i++;
-
-            if (i < allBits)
-                hash <<= 1;
-            else
-                // if allBits is an odd number
-                break;
-
-            if (minLonTmp < maxLonTmp) {
-                double midLon = (minLonTmp + maxLonTmp) / 2;
-                if (lon < midLon) {
-                    maxLonTmp = midLon;
-                } else {
-                    hash |= 1;
-                    minLonTmp = midLon;
-                }
-            }
-            i++;
-            if (i < allBits)
-                hash <<= 1;
-            else
-                break;
+    private static int decodeHelper(long z, int coord[]) {
+        long a = 0;
+        long EIGHTBITMASK = 0x000000ff;
+        long loops = (long) Math.floor(64.0f / 9.0f);
+        for (long i = 0; i < loops; ++i) {
+            a |= (coord[(int) ((z >> (i * 8)) & EIGHTBITMASK)] << (4 * i));
         }
-        return hash;
+        return (int) a;
     }
 
-    /**
-     * This method returns latitude and longitude via latLon - calculated from specified spatialKey
-     * <p>
-     *
-     * @param spatialKey is the input
-     */
-    @Override
-    public final void decode(long spatialKey, GHPoint latLon) {
-        // Performance: calculating 'midLon' and 'midLat' on the fly is not slower than using 
-        // precalculated values from arrays and for 'bits' a precalculated array is even slightly slower!
-
-        // Use the value in the middle => start from "min" use "max" as initial step-size
-        double midLat = (bbox.maxLat - bbox.minLat) / 2;
-        double midLon = (bbox.maxLon - bbox.minLon) / 2;
-        double lat = bbox.minLat;
-        double lon = bbox.minLon;
-        long bits = initialBits;
-        while (true) {
-            if ((spatialKey & bits) != 0) {
-                lat += midLat;
-            }
-
-            midLat /= 2;
-            bits >>>= 1;
-            if ((spatialKey & bits) != 0) {
-                lon += midLon;
-            }
-
-            midLon /= 2;
-            if (bits > 1) {
-                bits >>>= 1;
-            } else {
-                break;
-            }
-        }
+    // https://en.wikipedia.org/wiki/Z-order_curve
+
+    public long up(long z) {
+        return (((z | 0b0101010101010101010101010101010101010101010101010101010101010101L) + 1) &
+                0b1010101010101010101010101010101010101010101010101010101010101010L) | (z & 0b0101010101010101010101010101010101010101010101010101010101010101L);
+    }
 
-        // stable rounding - see testBijection
-        lat += midLat;
-        lon += midLon;
-        latLon.lat = lat;
-        latLon.lon = lon;
+    public long down(long z) {
+        return (((z & 0b1010101010101010101010101010101010101010101010101010101010101010L) - 1) &
+                0b1010101010101010101010101010101010101010101010101010101010101010L) | (z & 0b0101010101010101010101010101010101010101010101010101010101010101L);
     }
 
-    @Override
-    public String toString() {
-        return "bits:" + allBits + ", bounds:" + bbox;
+    public long right(long z) {
+        return (((z | 0b1010101010101010101010101010101010101010101010101010101010101010L) + 1)
+                & 0b0101010101010101010101010101010101010101010101010101010101010101L) | (z & 0b1010101010101010101010101010101010101010101010101010101010101010L);
     }
+
+    public long left(long z) {
+        return (((z & 0b0101010101010101010101010101010101010101010101010101010101010101L) - 1) &
+                0b0101010101010101010101010101010101010101010101010101010101010101L) | (z & 0b1010101010101010101010101010101010101010101010101010101010101010L);
+    }
+
 }
diff --git a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
index d2983e22e..8de7ba677 100644
--- a/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
+++ b/core/src/main/java/com/graphhopper/storage/GraphEdgeIdFinder.java
@@ -72,10 +72,11 @@ public class GraphEdgeIdFinder {
      * This method fills the edgeIds hash with edgeIds found inside the specified shape
      */
     public void findEdgesInShape(final GHIntHashSet edgeIds, final Shape shape, EdgeFilter filter) {
-        locationIndex.query(shape.getBounds(), new LocationIndex.EdgeVisitor(graph.createEdgeExplorer(filter)) {
+        locationIndex.query(shape.getBounds(), new LocationIndex.Visitor() {
             @Override
-            public void onEdge(EdgeIteratorState edge, int nodeA, int nodeB) {
-                if (shape.intersects(edge.fetchWayGeometry(FetchMode.ALL).makeImmutable()))
+            public void onEdge(int edgeId) {
+                EdgeIteratorState edge = graph.getEdgeIteratorStateForKey(edgeId * 2);
+                if (filter.accept(edge) && shape.intersects(edge.fetchWayGeometry(FetchMode.ALL).makeImmutable()))
                     edgeIds.add(edge.getEdge());
             }
         });
diff --git a/core/src/main/java/com/graphhopper/storage/index/BresenhamLine.java b/core/src/main/java/com/graphhopper/storage/index/BresenhamLine.java
deleted file mode 100644
index 76074076e..000000000
--- a/core/src/main/java/com/graphhopper/storage/index/BresenhamLine.java
+++ /dev/null
@@ -1,83 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-/**
- * We need the supercover line. The best algorithm is a 'voxel grid traversal algorithm' and
- * described in "A Fast Voxel Traversal Algorithm for Ray Tracing" by John Amanatides and Andrew Woo
- * (1987): http://www.cse.yorku.ca/~amana/research/grid.pdf
- * <p>
- * Other methods we used are Bresenham (only integer start and end values) and Xiaolin Wu (anti
- * aliasing). See some discussion here: http://stackoverflow.com/a/3234074/194609 and here
- * http://stackoverflow.com/q/24679963/194609
- * <p>
- *
- * @author Peter Karich
- */
-public class BresenhamLine {
-    public static void calcPoints(int y1, int x1, int y2, int x2, PointEmitter emitter) {
-        bresenham(y1, x1, y2, x2, emitter);
-    }
-
-    public static void bresenham(int y1, int x1, int y2, int x2, PointEmitter emitter) {
-        boolean latIncreasing = y1 < y2;
-        boolean lonIncreasing = x1 < x2;
-        int dLat = Math.abs(y2 - y1), sLat = latIncreasing ? 1 : -1;
-        int dLon = Math.abs(x2 - x1), sLon = lonIncreasing ? 1 : -1;
-        int err = dLon - dLat;
-
-        while (true) {
-            emitter.set(y1, x1);
-            if (y1 == y2 && x1 == x2)
-                break;
-
-            int tmpErr = 2 * err;
-            if (tmpErr > -dLat) {
-                err -= dLat;
-                x1 += sLon;
-            }
-
-            if (tmpErr < dLon) {
-                err += dLon;
-                y1 += sLat;
-            }
-        }
-    }
-
-    /**
-     * Calls the Bresenham algorithm but make it working for double values
-     */
-    public static void calcPoints(final double lat1, final double lon1,
-                                  final double lat2, final double lon2,
-                                  final PointEmitter emitter,
-                                  final double offsetLat, final double offsetLon,
-                                  final double deltaLat, final double deltaLon) {
-        // round to make results of bresenham closer to correct solution
-        int y1 = (int) ((lat1 - offsetLat) / deltaLat);
-        int x1 = (int) ((lon1 - offsetLon) / deltaLon);
-        int y2 = (int) ((lat2 - offsetLat) / deltaLat);
-        int x2 = (int) ((lon2 - offsetLon) / deltaLon);
-        bresenham(y1, x1, y2, x2, new PointEmitter() {
-            @Override
-            public void set(double lat, double lon) {
-                // +.1 to move more near the center of the tile
-                emitter.set((lat + .1) * deltaLat + offsetLat, (lon + .1) * deltaLon + offsetLon);
-            }
-        });
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java
deleted file mode 100644
index 0cfd14a51..000000000
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullIndex.java
+++ /dev/null
@@ -1,138 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.util.AllEdgesIterator;
-import com.graphhopper.routing.util.EdgeFilter;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.NodeAccess;
-import com.graphhopper.util.DistanceCalc;
-import com.graphhopper.util.DistanceCalcEarth;
-import com.graphhopper.util.DistancePlaneProjection;
-import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.Circle;
-
-/**
- * Very slow O(n) LocationIndex but no RAM/disc required.
- *
- * @author Peter Karich
- */
-public class Location2IDFullIndex implements LocationIndex {
-    private final Graph graph;
-    private final NodeAccess nodeAccess;
-    private DistanceCalc calc = DistancePlaneProjection.DIST_PLANE;
-    private boolean closed = false;
-
-    public Location2IDFullIndex(Graph g) {
-        this.graph = g;
-        this.nodeAccess = g.getNodeAccess();
-    }
-
-    @Override
-    public boolean loadExisting() {
-        return true;
-    }
-
-    @Override
-    public LocationIndex setApproximation(boolean approxDist) {
-        if (approxDist)
-            calc = DistancePlaneProjection.DIST_PLANE;
-        else
-            calc = DistanceCalcEarth.DIST_EARTH;
-
-        return this;
-    }
-
-    @Override
-    public LocationIndex setResolution(int resolution) {
-        return this;
-    }
-
-    @Override
-    public LocationIndex prepareIndex() {
-        return this;
-    }
-
-    @Override
-    public Snap findClosest(double queryLat, double queryLon, EdgeFilter edgeFilter) {
-        if (isClosed())
-            throw new IllegalStateException("You need to create a new LocationIndex instance as it is already closed");
-
-        Snap res = new Snap(queryLat, queryLon);
-        Circle circle = null;
-        AllEdgesIterator iter = graph.getAllEdges();
-        while (iter.next()) {
-            if (!edgeFilter.accept(iter))
-                continue;
-
-            for (int node, i = 0; i < 2; i++) {
-                if (i == 0) {
-                    node = iter.getBaseNode();
-                } else {
-                    node = iter.getAdjNode();
-                }
-                double tmpLat = nodeAccess.getLatitude(node);
-                double tmpLon = nodeAccess.getLongitude(node);
-                double dist = calc.calcDist(tmpLat, tmpLon, queryLat, queryLon);
-                if (circle == null || dist < calc.calcDist(circle.getLat(), circle.getLon(), queryLat, queryLon)) {
-                    res.setClosestEdge(iter.detach(false));
-                    res.setClosestNode(node);
-                    res.setQueryDistance(dist);
-                    if (dist <= 0)
-                        break;
-
-                    circle = new Circle(tmpLat, tmpLon, dist, calc);
-                }
-            }
-        }
-        return res;
-    }
-
-    @Override
-    public void query(BBox queryBBox, Visitor function) {
-        throw new IllegalArgumentException("not implemented");
-    }
-
-    @Override
-    public LocationIndex create(long size) {
-        return this;
-    }
-
-    @Override
-    public void flush() {
-    }
-
-    @Override
-    public void close() {
-        closed = true;
-    }
-
-    @Override
-    public boolean isClosed() {
-        return closed;
-    }
-
-    @Override
-    public long getCapacity() {
-        return 0;
-    }
-
-    @Override
-    public void setSegmentSize(int bytes) {
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java
deleted file mode 100644
index 7275080b9..000000000
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndex.java
+++ /dev/null
@@ -1,162 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.util.AllEdgesIterator;
-import com.graphhopper.routing.util.EdgeFilter;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.NodeAccess;
-import com.graphhopper.util.DistanceCalc;
-import com.graphhopper.util.DistanceCalcEarth;
-import com.graphhopper.util.DistancePlaneProjection;
-import com.graphhopper.util.shapes.BBox;
-
-/**
- * Same as full index but calculates distance to all edges too
- * <p>
- *
- * @author Peter Karich
- */
-public class Location2IDFullWithEdgesIndex implements LocationIndex {
-    private final Graph graph;
-    private final NodeAccess nodeAccess;
-    private DistanceCalc calc = DistanceCalcEarth.DIST_EARTH;
-    private boolean closed = false;
-
-    public Location2IDFullWithEdgesIndex(Graph g) {
-        this.graph = g;
-        this.nodeAccess = g.getNodeAccess();
-    }
-
-    @Override
-    public boolean loadExisting() {
-        return true;
-    }
-
-    @Override
-    public LocationIndex setResolution(int resolution) {
-        return this;
-    }
-
-    @Override
-    public LocationIndex setApproximation(boolean approxDist) {
-        if (approxDist) {
-            calc = DistancePlaneProjection.DIST_PLANE;
-        } else {
-            calc = DistanceCalcEarth.DIST_EARTH;
-        }
-        return this;
-    }
-
-    @Override
-    public LocationIndex prepareIndex() {
-        return this;
-    }
-
-    @Override
-    public Snap findClosest(double queryLat, double queryLon, EdgeFilter filter) {
-        if (isClosed())
-            throw new IllegalStateException("You need to create a new LocationIndex instance as it is already closed");
-
-        Snap res = new Snap(queryLat, queryLon);
-        double foundDist = Double.MAX_VALUE;
-        AllEdgesIterator iter = graph.getAllEdges();
-        while (iter.next()) {
-            if (!filter.accept(iter)) {
-                continue;
-            }
-            for (int i = 0, node; i < 2; i++) {
-                if (i == 0) {
-                    node = iter.getBaseNode();
-                } else {
-                    node = iter.getAdjNode();
-                }
-
-                double fromLat = nodeAccess.getLatitude(node);
-                double fromLon = nodeAccess.getLongitude(node);
-                double fromDist = calc.calcDist(fromLat, fromLon, queryLat, queryLon);
-                if (fromDist < 0)
-                    continue;
-
-                if (fromDist < foundDist) {
-                    res.setQueryDistance(fromDist);
-                    res.setClosestEdge(iter.detach(false));
-                    res.setClosestNode(node);
-                    foundDist = fromDist;
-                }
-
-                // process the next stuff only for baseNode
-                if (i > 0)
-                    continue;
-
-                int toNode = iter.getAdjNode();
-                double toLat = nodeAccess.getLatitude(toNode);
-                double toLon = nodeAccess.getLongitude(toNode);
-
-                if (calc.validEdgeDistance(queryLat, queryLon,
-                        fromLat, fromLon, toLat, toLon)) {
-                    double distEdge = calc.calcDenormalizedDist(calc.calcNormalizedEdgeDistance(queryLat, queryLon,
-                            fromLat, fromLon, toLat, toLon));
-                    if (distEdge < foundDist) {
-                        res.setQueryDistance(distEdge);
-                        res.setClosestNode(node);
-                        res.setClosestEdge(iter);
-                        if (fromDist > calc.calcDist(toLat, toLon, queryLat, queryLon))
-                            res.setClosestNode(toNode);
-
-                        foundDist = distEdge;
-                    }
-                }
-            }
-        }
-        return res;
-    }
-
-    @Override
-    public void query(BBox queryBBox, Visitor function) {
-        throw new IllegalArgumentException("not implemented");
-    }
-
-    @Override
-    public LocationIndex create(long size) {
-        return this;
-    }
-
-    @Override
-    public void flush() {
-    }
-
-    @Override
-    public void close() {
-        closed = true;
-    }
-
-    @Override
-    public boolean isClosed() {
-        return closed;
-    }
-
-    @Override
-    public long getCapacity() {
-        return 0;
-    }
-
-    @Override
-    public void setSegmentSize(int bytes) {
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java b/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java
deleted file mode 100644
index d041ef0e4..000000000
--- a/core/src/main/java/com/graphhopper/storage/index/Location2IDQuadtree.java
+++ /dev/null
@@ -1,368 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.coll.GHBitSet;
-import com.graphhopper.coll.GHBitSetImpl;
-import com.graphhopper.coll.GHTBitSet;
-import com.graphhopper.geohash.KeyAlgo;
-import com.graphhopper.geohash.LinearKeyAlgo;
-import com.graphhopper.routing.util.EdgeFilter;
-import com.graphhopper.storage.*;
-import com.graphhopper.util.*;
-import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
-import java.util.Arrays;
-
-/**
- * This class implements map matching and returns a node index from lat,lon coordinate. This
- * implementation is the a very memory efficient representation for areas with lots of node and
- * edges, but lacks precision. No edge distances are measured.
- * <p>
- *
- * @author Peter Karich
- * @see LocationIndexTree which is more precise but more complicated and also slightly slower
- * implementation of LocationIndex.
- * <p>
- */
-class Location2IDQuadtree implements LocationIndex {
-    private final static int MAGIC_INT = Integer.MAX_VALUE / 12306;
-    private final Logger logger = LoggerFactory.getLogger(getClass());
-    private final DataAccess index;
-    private final Graph graph;
-    private final NodeAccess nodeAccess;
-    protected DistanceCalc distCalc = DistancePlaneProjection.DIST_PLANE;
-    private KeyAlgo keyAlgo;
-    private double maxRasterWidth2InMeterNormed;
-    private int lonSize, latSize;
-
-    public Location2IDQuadtree(Graph g, Directory dir) {
-        this.graph = g;
-        this.nodeAccess = g.getNodeAccess();
-        index = dir.find("loc2id_index");
-        setResolution(100 * 100);
-    }
-
-    @Override
-    public LocationIndex setApproximation(boolean approxDist) {
-        if (approxDist)
-            distCalc = DistancePlaneProjection.DIST_PLANE;
-        else
-            distCalc = DistanceCalcEarth.DIST_EARTH;
-
-        return this;
-    }
-
-    @Override
-    public long getCapacity() {
-        return index.getCapacity() / 4;
-    }
-
-    /**
-     * Loads the index from disc if exists. Make sure you are using the identical graph which was
-     * used while flushing this index.
-     * <p>
-     *
-     * @return if loading from file was successfully.
-     */
-    @Override
-    public boolean loadExisting() {
-        if (!index.loadExisting())
-            return false;
-
-        if (index.getHeader(0) != MAGIC_INT)
-            throw new IllegalStateException("incorrect loc2id index version");
-
-        int lat = index.getHeader(1 * 4);
-        int lon = index.getHeader(2 * 4);
-        int checksum = index.getHeader(3 * 4);
-        if (checksum != graph.getNodes())
-            throw new IllegalStateException("index was created from a different graph with "
-                    + checksum + ". Current nodes:" + graph.getNodes());
-
-        initAlgo(lat, lon);
-        return true;
-    }
-
-    @Override
-    public LocationIndex create(long size) {
-        throw new UnsupportedOperationException("Not supported. Use prepareIndex instead.");
-    }
-
-    @Override
-    public LocationIndex setResolution(int resolution) {
-        initLatLonSize(resolution);
-        return this;
-    }
-
-    /**
-     * Fill quadtree which will span a raster over the entire specified graph g. But do this in a
-     * pre-defined resolution which is controlled via capacity. This data structure then uses approx.
-     * capacity * 4 bytes. So maximum capacity is 2^30 where the quadtree would cover the world
-     * boundaries every 1.3km - IMO enough for EU or US networks.
-     */
-    @Override
-    public LocationIndex prepareIndex() {
-        initBuffer();
-        initAlgo(latSize, lonSize);
-        StopWatch sw = new StopWatch().start();
-        GHBitSet filledIndices = fillQuadtree(latSize * lonSize);
-        int fillQT = filledIndices.getCardinality();
-        float res1 = sw.stop().getSeconds();
-        sw = new StopWatch().start();
-        int counter = fillEmptyIndices(filledIndices);
-        float fillEmpty = sw.stop().getSeconds();
-        logger.info("filled quadtree index array in " + res1 + "s. size is " + getCapacity()
-                + " (" + fillQT + "). filled empty " + counter + " in " + fillEmpty + "s");
-        flush();
-        return this;
-    }
-
-    private void initLatLonSize(int size) {
-        latSize = lonSize = (int) Math.sqrt(size);
-        if (latSize * lonSize < size)
-            lonSize++;
-    }
-
-    private void initBuffer() {
-        // avoid default big segment size and use one segment only:
-        index.setSegmentSize(latSize * lonSize * 4);
-        index.create(latSize * lonSize * 4);
-    }
-
-    void initAlgo(int lat, int lon) {
-        this.latSize = lat;
-        this.lonSize = lon;
-        BBox b = graph.getBounds();
-        keyAlgo = new LinearKeyAlgo(lat, lon).setBounds(b);
-        double max = Math.max(distCalc.calcDist(b.minLat, b.minLon, b.minLat, b.maxLon),
-                distCalc.calcDist(b.minLat, b.minLon, b.maxLat, b.minLon));
-        maxRasterWidth2InMeterNormed = distCalc.calcNormalizedDist(max / Math.sqrt(getCapacity()) * 2);
-
-        // as long as we have "dist < PI*R/2" it is save to compare the normalized distances instead of the real
-        // distances. because sin(x) is only monotonic increasing for x <= PI/2 (and positive for x >= 0)
-    }
-
-    protected double getMaxRasterWidthMeter() {
-        return distCalc.calcDenormalizedDist(maxRasterWidth2InMeterNormed) / 2;
-    }
-
-    private GHBitSet fillQuadtree(int size) {
-        int locs = graph.getNodes();
-        if (locs <= 0) {
-            throw new IllegalStateException("check your graph - it is empty!");
-        }
-
-        GHBitSet filledIndices = new GHBitSetImpl(size);
-        GHPoint coord = new GHPoint();
-        for (int nodeId = 0; nodeId < locs; nodeId++) {
-            double lat = nodeAccess.getLatitude(nodeId);
-            double lon = nodeAccess.getLongitude(nodeId);
-            int key = (int) keyAlgo.encode(lat, lon);
-            long bytePos = (long) key * 4;
-            if (filledIndices.contains(key)) {
-                int oldNodeId = index.getInt(bytePos);
-                keyAlgo.decode(key, coord);
-                // decide which one is closer to 'key'
-                double distNew = distCalc.calcNormalizedDist(coord.lat, coord.lon, lat, lon);
-                double oldLat = nodeAccess.getLatitude(oldNodeId);
-                double oldLon = nodeAccess.getLongitude(oldNodeId);
-                double distOld = distCalc.calcNormalizedDist(coord.lat, coord.lon, oldLat, oldLon);
-                // new point is closer to quad tree point (key) so overwrite old
-                if (distNew < distOld) {
-                    index.setInt(bytePos, nodeId);
-                }
-            } else {
-                index.setInt(bytePos, nodeId);
-                filledIndices.add(key);
-            }
-        }
-        return filledIndices;
-    }
-
-    private int fillEmptyIndices(GHBitSet filledIndices) {
-        int len = latSize * lonSize;
-        DataAccess indexCopy = new RAMDirectory().find("temp_index_copy");
-        indexCopy.setSegmentSize(index.getSegmentSize()).create(index.getCapacity());
-        GHBitSet indicesCopy = new GHBitSetImpl(len);
-        int initializedCounter = filledIndices.getCardinality();
-        // fan out initialized entries to avoid "nose-artifacts"
-        // we 1. do not use the same index for check and set and iterate until all indices are set
-        // and 2. use a taken-from array to decide which of the colliding should be preferred
-        int[] takenFrom = new int[len];
-        Arrays.fill(takenFrom, -1);
-        for (int i = filledIndices.next(0); i >= 0; i = filledIndices.next(i + 1)) {
-            takenFrom[i] = i;
-        }
-        if (initializedCounter == 0) {
-            throw new IllegalStateException("at least one entry has to be != null, which should have happened in initIndex");
-        }
-        int tmp = initializedCounter;
-        while (initializedCounter < len) {
-            index.copyTo(indexCopy);
-            filledIndices.copyTo(indicesCopy);
-            initializedCounter = filledIndices.getCardinality();
-            for (int i = 0; i < len; i++) {
-                int to = -1, from = -1;
-                if (indicesCopy.contains(i)) {
-                    // check change "initialized to empty"                    
-                    if ((i + 1) % lonSize != 0 && !indicesCopy.contains(i + 1)) {
-                        // set right from current
-                        from = i;
-                        to = i + 1;
-                    } else if (i + lonSize < len && !indicesCopy.contains(i + lonSize)) {
-                        // set below from current
-                        from = i;
-                        to = i + lonSize;
-                    }
-                } else // check change "empty to initialized"
-                    if ((i + 1) % lonSize != 0 && indicesCopy.contains(i + 1)) {
-                        // set from right
-                        from = i + 1;
-                        to = i;
-                    } else if (i + lonSize < len && indicesCopy.contains(i + lonSize)) {
-                        // set from below
-                        from = i + lonSize;
-                        to = i;
-                    }
-                if (to >= 0) {
-                    if (takenFrom[to] >= 0) {
-                        // takenFrom[to] == to -> special case for normedDist == 0
-                        if (takenFrom[to] == to
-                                || getNormedDist(from, to) >= getNormedDist(takenFrom[to], to)) {
-                            continue;
-                        }
-                    }
-
-                    index.setInt(to * 4, indexCopy.getInt(from * 4));
-                    takenFrom[to] = takenFrom[from];
-                    filledIndices.add(to);
-                    initializedCounter++;
-                }
-            }
-        }
-
-        return initializedCounter - tmp;
-    }
-
-    double getNormedDist(int from, int to) {
-        int fromX = from % lonSize;
-        int fromY = from / lonSize;
-        int toX = to % lonSize;
-        int toY = to / lonSize;
-        int dx = (toX - fromX);
-        int dy = (toY - fromY);
-        return dx * dx + dy * dy;
-    }
-
-    @Override
-    public Snap findClosest(final double queryLat, final double queryLon,
-                            final EdgeFilter edgeFilter) {
-        if (isClosed())
-            throw new IllegalStateException("You need to create a new LocationIndex instance as it is already closed");
-
-        if (edgeFilter != EdgeFilter.ALL_EDGES)
-            throw new UnsupportedOperationException("edge filters are not yet implemented for " + Location2IDQuadtree.class.getSimpleName());
-
-        // The following cases (e.g. dead ends or motorways crossing a normal way) could be problematic:
-        // |     |
-        // |  P  | 
-        // |  |  |< --- maxRasterWidth reached
-        // \-----/
-        /*
-         * Problem: use additionally the 8 surrounding quadrants: There an error due to the raster
-         * width. Because this index does not cover 100% of the graph you'll need to traverse the
-         * graph until you find the real matching point or if you reach the raster width limit. And
-         * there is a problem when using the raster limit as 'not found' indication and if you have
-         * arbitrary requests e.g. from other systems (where points do not match exactly): Although
-         * P is the closest point to the request one it could be that the raster limit is too short
-         * to reach it via graph traversal:
-         */
-        long key = keyAlgo.encode(queryLat, queryLon);
-        final int id = index.getInt(key * 4);
-        double mainLat = nodeAccess.getLatitude(id);
-        double mainLon = nodeAccess.getLongitude(id);
-        final Snap res = new Snap(queryLat, queryLon);
-        res.setClosestNode(id);
-        res.setQueryDistance(distCalc.calcNormalizedDist(queryLat, queryLon, mainLat, mainLon));
-        goFurtherHook(id);
-        new BreadthFirstSearch() {
-            @Override
-            protected GHBitSet createBitSet() {
-                return new GHTBitSet(10);
-            }
-
-            @Override
-            protected boolean goFurther(int baseNode) {
-                if (baseNode == id)
-                    return true;
-
-                goFurtherHook(baseNode);
-                double currLat = nodeAccess.getLatitude(baseNode);
-                double currLon = nodeAccess.getLongitude(baseNode);
-                double currNormedDist = distCalc.calcNormalizedDist(queryLat, queryLon, currLat, currLon);
-                if (currNormedDist < res.getQueryDistance()) {
-                    res.setQueryDistance(currNormedDist);
-                    res.setClosestNode(baseNode);
-                    return true;
-                }
-
-                return currNormedDist < maxRasterWidth2InMeterNormed;
-            }
-        }.start(graph.createEdgeExplorer(), id);
-
-        // denormalize distance
-        res.setQueryDistance(distCalc.calcDenormalizedDist(res.getQueryDistance()));
-        return res;
-    }
-
-    @Override
-    public void query(BBox queryBBox, Visitor function) {
-        throw new IllegalArgumentException("not implemented");
-    }
-
-    public void goFurtherHook(int n) {
-    }
-
-    @Override
-    public void flush() {
-        index.setHeader(0, MAGIC_INT);
-        index.setHeader(1 * 4, latSize);
-        index.setHeader(2 * 4, lonSize);
-        index.setHeader(3 * 4, graph.getNodes());
-        index.flush();
-    }
-
-    @Override
-    public void close() {
-        index.close();
-    }
-
-    @Override
-    public boolean isClosed() {
-        return index.isClosed();
-    }
-
-    @Override
-    public void setSegmentSize(int bytes) {
-        index.setSegmentSize(bytes);
-    }
-}
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 5203a224c..7c27923b6 100644
--- a/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java
+++ b/core/src/main/java/com/graphhopper/storage/index/LocationIndex.java
@@ -17,12 +17,8 @@
  */
 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;
 
 /**
@@ -35,16 +31,6 @@ import com.graphhopper.util.shapes.BBox;
  * @author Peter Karich
  */
 public interface LocationIndex extends Storable<LocationIndex> {
-    /**
-     * Integer value to specify the resolution of this location index. The higher the better the
-     * resolution.
-     */
-    LocationIndex setResolution(int resolution);
-
-    /**
-     * Creates this index - to be called once before findID.
-     */
-    LocationIndex prepareIndex();
 
     /**
      * This method returns the closest Snap for the specified location (lat, lon) and only if
@@ -56,28 +42,20 @@ public interface LocationIndex extends Storable<LocationIndex> {
      *                   node into the graph is accessible from a selected vehicle. E.g. if you have a FOOT-query do:
      *                   <pre>DefaultEdgeFilter.allEdges(footFlagEncoder);</pre>
      * @return An object containing the closest node and edge for the specified location. The node id
-     * has at least one edge which is accepted from the specified edgeFilter. If nothing is found
+     * has at least one edge which is accepted by the specified edgeFilter. If nothing is found
      * the method Snap.isValid will return false.
      */
     Snap findClosest(double lat, double lon, EdgeFilter edgeFilter);
 
     /**
-     * @param approxDist false if initialization and querying should be faster but less precise.
-     */
-    LocationIndex setApproximation(boolean approxDist);
-
-    void setSegmentSize(int bytes);
-
-    /**
-     * This method explores the LocationIndex with the specified Visitor. It visits only the stored nodes (and only once)
-     * and limited by the queryBBox. Note that for every edge only one node has to be stored and to get all nodes
-     * (or edges) you should better use EdgeVisitor. Also (a few) more nodes slightly outside of queryBBox could be
+     * This method explores the LocationIndex with the specified Visitor. It visits only the stored edges (and only once)
+     * and limited by the queryBBox. Also (a few) more edges slightly outside of queryBBox could be
      * returned that you can avoid via doing an explicit BBox check of the coordinates.
      */
     void query(BBox queryBBox, Visitor function);
 
     /**
-     * This interface allows to visit nodes stored in the LocationIndex.
+     * This interface allows to visit edges stored in the LocationIndex.
      */
     abstract class Visitor {
         public boolean isTileInfo() {
@@ -90,36 +68,7 @@ public interface LocationIndex extends Storable<LocationIndex> {
         public void onTile(BBox bbox, int depth) {
         }
 
-        public abstract void onNode(int nodeId);
+        public abstract void onEdge(int edgeId);
     }
 
-    /**
-     * This abstract class allows to visit every edge from the stored nodes in the LocationIndex for a requested area.
-     * It visits all edges once and inside the queryBBox. Also (a few) more nodes slightly outside of queryBBox could be
-     * returned that you can avoid via doing an explicit BBox check of the coordinates.
-     */
-    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 43e5c2b95..5d331fd6e 100644
--- a/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java
+++ b/core/src/main/java/com/graphhopper/storage/index/LocationIndexTree.java
@@ -19,22 +19,25 @@ 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;
-import com.graphhopper.coll.GHIntHashSet;
-import com.graphhopper.coll.GHTBitSet;
 import com.graphhopper.geohash.SpatialKeyAlgo;
 import com.graphhopper.routing.util.AllEdgesIterator;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.storage.*;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
+import org.locationtech.jts.geom.Coordinate;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import java.util.function.IntConsumer;
+
+import static com.graphhopper.util.DistanceCalcEarth.C;
+import static com.graphhopper.util.DistanceCalcEarth.DIST_EARTH;
+import static com.graphhopper.util.DistancePlaneProjection.DIST_PLANE;
 
 /**
  * This class implements a Quadtree to get the closest node or edge from GPS coordinates.
@@ -45,11 +48,9 @@ import java.util.*;
  * 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>
+ * into a 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 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.</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>
@@ -63,12 +64,10 @@ public class LocationIndexTree implements LocationIndex {
     protected final Graph graph;
     final DataAccess dataAccess;
     private final Logger logger = LoggerFactory.getLogger(getClass());
-    private final int MAGIC_INT;
+    private final int MAGIC_INT = Integer.MAX_VALUE / 22318;
     private final NodeAccess nodeAccess;
-    protected DistanceCalc distCalc = DistancePlaneProjection.DIST_PLANE;
     SpatialKeyAlgo keyAlgo;
     private int maxRegionSearch = 4;
-    private DistanceCalc preciseDistCalc = DistanceCalcEarth.DIST_EARTH;
     private int[] entries;
     private byte[] shifts;
     // convert spatial key to index for subentry of current depth
@@ -76,23 +75,22 @@ public class LocationIndexTree implements LocationIndex {
     private int minResolutionInMeter = 300;
     private double deltaLat;
     private double deltaLon;
-    private int initSizeLeafEntries = 4;
     private boolean initialized = false;
-    private static final Comparator<Snap> SNAP_COMPARATOR = Comparator.comparingDouble(Snap::getQueryDistance);
+
     /**
      * If normed distance is smaller than this value the node or edge is 'identical' and the
      * algorithm can stop search.
      */
-    private double equalNormedDelta;
+    private final double equalNormedDelta = DIST_PLANE.calcNormalizedDist(0.1); // 0.1 meters
+    private PixelGridTraversal pixelGridTraversal;
 
     /**
      * @param g the graph for which this index should do the lookup based on latitude,longitude.
      */
     public LocationIndexTree(Graph g, Directory dir) {
-        MAGIC_INT = Integer.MAX_VALUE / 22317;
         this.graph = g;
         this.nodeAccess = g.getNodeAccess();
-        dataAccess = dir.find("location_index", DAType.getPreferredInt(dir.getDefaultType()));
+        this.dataAccess = dir.find("location_index", DAType.getPreferredInt(dir.getDefaultType()));
     }
 
     public int getMinResolutionInMeter() {
@@ -110,39 +108,34 @@ public class LocationIndexTree implements LocationIndex {
 
     /**
      * Searches also neighbouring tiles until the maximum distance from the query point is reached
-     * (minResolutionInMeter*regionAround). Set to 1 for to force avoiding a fall back, good if you
-     * have strict performance and lookup-quality requirements. Default is 4.
+     * (minResolutionInMeter*regionAround). Set to 1 to only search one tile. Good if you
+     * have strict performance requirements and want the search to terminate early, and you can tolerate
+     * that edges that may be in neighboring tiles are not found. Default is 4, which means approximately
+     * that a square of three tiles upwards, downwards, leftwards and rightwards from the tile the query tile
+     * is in is searched.
      */
     public LocationIndexTree setMaxRegionSearch(int numTiles) {
         if (numTiles < 1)
             throw new IllegalArgumentException("Region of location index must be at least 1 but was " + numTiles);
-
-        // see #232
-        if (numTiles % 2 == 1)
-            numTiles++;
-
         this.maxRegionSearch = numTiles;
         return this;
     }
 
     void prepareAlgo() {
-        // 0.1 meter should count as 'equal'
-        equalNormedDelta = distCalc.calcNormalizedDist(0.1);
-
         // now calculate the necessary maxDepth d for our current bounds
         // if we assume a minimum resolution like 0.5km for a leaf-tile
         // n^(depth/2) = toMeter(dLon) / minResolution
-        BBox bounds = graph.getBounds();
-        if (graph.getNodes() == 0)
-            throw new IllegalStateException("Cannot create location index of empty graph!");
+        BBox bounds = graph.getBounds().clone();
 
+        // I want to be able to create a location index for the empty graph without error, but for that
+        // I need valid bounds so that the initialization logic works.
         if (!bounds.isValid())
-            throw new IllegalStateException("Cannot create location index when graph has invalid bounds: " + bounds);
+            bounds = new BBox(-10.0,10.0,-10.0,10.0);
 
         double lat = Math.min(Math.abs(bounds.maxLat), Math.abs(bounds.minLat));
         double maxDistInMeter = Math.max(
-                (bounds.maxLat - bounds.minLat) / 360 * DistanceCalcEarth.C,
-                (bounds.maxLon - bounds.minLon) / 360 * preciseDistCalc.calcCircumference(lat));
+                (bounds.maxLat - bounds.minLat) / 360 * C,
+                (bounds.maxLon - bounds.minLon) / 360 * DIST_EARTH.calcCircumference(lat));
         double tmp = maxDistInMeter / minResolutionInMeter;
         tmp = tmp * tmp;
         IntArrayList tmpEntries = new IntArrayList();
@@ -171,10 +164,11 @@ public class LocationIndexTree implements LocationIndex {
         if (shiftSum > 64)
             throw new IllegalStateException("sum of all shifts does not fit into a long variable");
 
-        keyAlgo = new SpatialKeyAlgo(shiftSum).bounds(bounds);
+        keyAlgo = new SpatialKeyAlgo(shiftSum, bounds);
         parts = Math.round(Math.sqrt(parts));
         deltaLat = (bounds.maxLat - bounds.minLat) / parts;
         deltaLon = (bounds.maxLon - bounds.minLon) / parts;
+        pixelGridTraversal = new PixelGridTraversal((int) parts, bounds);
     }
 
     private LocationIndexTree initEntries(int[] entries) {
@@ -221,7 +215,6 @@ public class LocationIndexTree implements LocationIndex {
         return memIndex;
     }
 
-    @Override
     public LocationIndex setResolution(int minResolutionInMeter) {
         if (minResolutionInMeter <= 0)
             throw new IllegalStateException("Negative precision is not allowed!");
@@ -230,15 +223,6 @@ public class LocationIndexTree implements LocationIndex {
         return this;
     }
 
-    @Override
-    public LocationIndex setApproximation(boolean approx) {
-        if (approx)
-            distCalc = DistancePlaneProjection.DIST_PLANE;
-        else
-            distCalc = DistanceCalcEarth.DIST_EARTH;
-        return this;
-    }
-
     @Override
     public LocationIndexTree create(long size) {
         throw new UnsupportedOperationException("Not supported. Use prepareIndex instead.");
@@ -275,7 +259,6 @@ public class LocationIndexTree implements LocationIndex {
         dataAccess.flush();
     }
 
-    @Override
     public LocationIndex prepareIndex() {
         return prepareIndex(EdgeFilter.ALL_EDGES);
     }
@@ -330,109 +313,70 @@ public class LocationIndexTree implements LocationIndex {
         return dataAccess.getCapacity();
     }
 
-    @Override
-    public void setSegmentSize(int bytes) {
-        dataAccess.setSegmentSize(bytes);
-    }
-
-    // just for test
-    IntArrayList getEntries() {
-        return IntArrayList.from(entries);
-    }
-
     /**
-     * This method fills the set with stored node IDs from the given spatial key part (a latitude-longitude prefix).
+     * This method fills the set with stored edge IDs from the given spatial key
      */
-    final void fillIDs(long keyPart, int intPointer, GHIntHashSet set, 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)
-                set.add(-(nextIntPointer + 1));
-            } else {
-                long max = (long) nextIntPointer * 4;
-                // leaf entry => nextIntPointer is maxPointer
-                for (long leafIndex = pointer + 4; leafIndex < max; leafIndex += 4) {
-                    set.add(dataAccess.getInt(leafIndex));
-                }
+    final void fillIDs(long keyPart, IntConsumer consumer) {
+        int intPointer = START_POINTER;
+        for (int depth = 0; depth < entries.length; depth++) {
+            int offset = (int) (keyPart >>> (64 - shifts[depth]));
+            int nextIntPointer = dataAccess.getInt((long) (intPointer + offset) * 4);
+            if (nextIntPointer <= 0) {
+                // empty cell
+                return;
+            }
+            keyPart = keyPart << shifts[depth];
+            intPointer = nextIntPointer;
+        }
+        int data = dataAccess.getInt((long) intPointer * 4);
+        if (data < 0) {
+            // single data entries (less disc space)
+            int edgeId = -(data + 1);
+            consumer.accept(edgeId);
+        } else {
+            // "data" is index of last data item
+            for (int leafIndex = intPointer + 1; leafIndex < data; leafIndex++) {
+                int edgeId = dataAccess.getInt((long) leafIndex * 4);
+                consumer.accept(edgeId);
             }
-            return;
-        }
-        int offset = (int) (bitmasks[depth] & keyPart) << 2;
-        int nextIntPointer = dataAccess.getInt(pointer + offset);
-        if (nextIntPointer > 0) {
-            // tree entry => negative value points to subentries
-            fillIDs(keyPart >>> shifts[depth], nextIntPointer, set, depth + 1);
         }
     }
 
-    // this method returns the spatial key in reverse order for easier right-shifting
-    final long createReverseKey(double lat, double lon) {
-        return BitUtil.BIG.reverse(keyAlgo.encode(lat, lon), keyAlgo.getBits());
-    }
-
-    final long createReverseKey(long key) {
-        return BitUtil.BIG.reverse(key, keyAlgo.getBits());
-    }
-
-    /**
-     * calculate the distance to the nearest tile border for a given lat/lon coordinate in the
-     * context of a spatial key tile.
-     */
-    final double calculateRMin(double lat, double lon) {
-        return calculateRMin(lat, lon, 0);
-    }
-
     /**
      * Calculates the distance to the nearest tile border, where the tile border is the rectangular
      * region with dimension 2*paddingTiles + 1 and where the center tile contains the given lat/lon
      * coordinate
      */
     final double calculateRMin(double lat, double lon, int paddingTiles) {
-        GHPoint query = new GHPoint(lat, lon);
-        long key = keyAlgo.encode(query);
-        GHPoint center = new GHPoint();
-        keyAlgo.decode(key, center);
+        int x = keyAlgo.x(lon);
+        int y = keyAlgo.y(lat);
 
         // deltaLat and deltaLon comes from the LocationIndex:
-        double minLat = center.lat - (0.5 + paddingTiles) * deltaLat;
-        double maxLat = center.lat + (0.5 + paddingTiles) * deltaLat;
-        double minLon = center.lon - (0.5 + paddingTiles) * deltaLon;
-        double maxLon = center.lon + (0.5 + paddingTiles) * deltaLon;
+        double minLat = graph.getBounds().minLat + (y - paddingTiles) * deltaLat;
+        double maxLat = graph.getBounds().minLat + (y + paddingTiles + 1) * deltaLat;
+        double minLon = graph.getBounds().minLon + (x - paddingTiles) * deltaLon;
+        double maxLon = graph.getBounds().minLon + (x + paddingTiles + 1) * deltaLon;
 
-        double dSouthernLat = query.lat - minLat;
-        double dNorthernLat = maxLat - query.lat;
-        double dWesternLon = query.lon - minLon;
-        double dEasternLon = maxLon - query.lon;
+        double dSouthernLat = lat - minLat;
+        double dNorthernLat = maxLat - lat;
+        double dWesternLon = lon - minLon;
+        double dEasternLon = maxLon - lon;
 
         // convert degree deltas into a radius in meter
         double dMinLat, dMinLon;
         if (dSouthernLat < dNorthernLat) {
-            dMinLat = distCalc.calcDist(query.lat, query.lon, minLat, query.lon);
+            dMinLat = DIST_PLANE.calcDist(lat, lon, minLat, lon);
         } else {
-            dMinLat = distCalc.calcDist(query.lat, query.lon, maxLat, query.lon);
+            dMinLat = DIST_PLANE.calcDist(lat, lon, maxLat, lon);
         }
 
         if (dWesternLon < dEasternLon) {
-            dMinLon = distCalc.calcDist(query.lat, query.lon, query.lat, minLon);
+            dMinLon = DIST_PLANE.calcDist(lat, lon, lat, minLon);
         } else {
-            dMinLon = distCalc.calcDist(query.lat, query.lon, query.lat, maxLon);
+            dMinLon = DIST_PLANE.calcDist(lat, lon, lat, maxLon);
         }
 
-        double rMin = Math.min(dMinLat, dMinLon);
-        return rMin;
-    }
-
-    /**
-     * Provide info about tilesize for testing / visualization
-     */
-    public double getDeltaLat() {
-        return deltaLat;
-    }
-
-    public double getDeltaLon() {
-        return deltaLon;
+        return Math.min(dMinLat, dMinLon);
     }
 
     public void query(BBox queryShape, final Visitor function) {
@@ -452,9 +396,9 @@ public class LocationIndexTree implements LocationIndex {
                     }
 
                     @Override
-                    public void onNode(int nodeId) {
-                        if (set.add(nodeId))
-                            function.onNode(nodeId);
+                    public void onEdge(int edgeId) {
+                        if (set.add(edgeId))
+                            function.onEdge(edgeId);
                     }
                 }, 0);
     }
@@ -463,18 +407,18 @@ public class LocationIndexTree implements LocationIndex {
                      double minLat, double minLon,
                      double deltaLatPerDepth, double deltaLonPerDepth,
                      Visitor function, int depth) {
-        long pointer = (long) intPointer << 2;
+        long pointer = (long) intPointer * 4;
         if (depth == entries.length) {
             int nextIntPointer = dataAccess.getInt(pointer);
             if (nextIntPointer < 0) {
                 // single data entries (less disc space)
-                function.onNode(-(nextIntPointer + 1));
+                function.onEdge(-(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));
+                    function.onEdge(dataAccess.getInt(leafPointer));
                 }
             }
             return;
@@ -487,13 +431,9 @@ public class LocationIndexTree implements LocationIndex {
             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;
+            int[] pixelXY = keyAlgo.decode(cellIndex);
+            double tmpMinLon = minLon + deltaLonPerDepth * pixelXY[0];
+            double tmpMinLat = minLat + deltaLatPerDepth * pixelXY[1];
 
             BBox bbox = (queryBBox != null || function.isTileInfo()) ? new BBox(tmpMinLon, tmpMinLon + deltaLonPerDepth, tmpMinLat, tmpMinLat + deltaLatPerDepth) : null;
             if (function.isTileInfo())
@@ -508,73 +448,41 @@ public class LocationIndexTree implements LocationIndex {
     }
 
     /**
-     * This method collects the node indices from the quad tree data structure in a certain order
-     * which makes sure not too many nodes are collected as well as no nodes will be missing. See
-     * discussion at issue #221.
-     * <p>
+     * This method collects edge ids from the neighborhood of a point and puts them into foundEntries.
+     *
+     * If it is called with iteration = 0, it just looks in the tile the query point is in.
+     * If it is called with iteration = 0,1,2,.., it will look in additional tiles further and further
+     * from the start tile. (In a square that grows by one pixel in all four directions per iteration).
      *
-     * @return true if no further call of this method is required. False otherwise, ie. a next
-     * iteration is necessary and no early finish possible.
+     * See discussion at issue #221.
+     * <p>
      */
-    final boolean findNetworkEntries(double queryLat, double queryLon,
-                                     GHIntHashSet foundEntries, int iteration) {
-        // find entries in border of searchbox
+    final void findEdgeIdsInNeighborhood(double queryLat, double queryLon, int iteration, IntConsumer foundEntries) {
+        int x = keyAlgo.x(queryLon);
+        int y = keyAlgo.y(queryLat);
         for (int yreg = -iteration; yreg <= iteration; yreg++) {
-            double subqueryLat = queryLat + yreg * deltaLat;
-            double subqueryLonA = queryLon - iteration * deltaLon;
-            double subqueryLonB = queryLon + iteration * deltaLon;
-            findNetworkEntriesSingleRegion(foundEntries, subqueryLat, subqueryLonA);
-
-            // minor optimization for iteration == 0
-            if (iteration > 0)
-                findNetworkEntriesSingleRegion(foundEntries, subqueryLat, subqueryLonB);
-        }
-
-        for (int xreg = -iteration + 1; xreg <= iteration - 1; xreg++) {
-            double subqueryLon = queryLon + xreg * deltaLon;
-            double subqueryLatA = queryLat - iteration * deltaLat;
-            double subqueryLatB = queryLat + iteration * deltaLat;
-            findNetworkEntriesSingleRegion(foundEntries, subqueryLatA, subqueryLon);
-            findNetworkEntriesSingleRegion(foundEntries, subqueryLatB, subqueryLon);
-        }
-
-        if (iteration % 2 != 0) {
-            // Check if something was found already...
-            if (!foundEntries.isEmpty()) {
-                double rMin = calculateRMin(queryLat, queryLon, iteration);
-                double minDistance = calcMinDistance(queryLat, queryLon, foundEntries);
-
-                if (minDistance < rMin)
-                    // early finish => foundEntries contains a nearest node for sure
-                    return true;
-                // else: continue as an undetected nearer node may sit in a neighbouring tile.
-                // Now calculate how far we have to look outside to find any hidden nearest nodes
-                // and repeat whole process with wider search area until this distance is covered.
+            int subqueryY = y + yreg;
+            int subqueryXA = x - iteration;
+            int subqueryXB = x + iteration;
+            long keyPart1 = keyAlgo.encode(subqueryXA, subqueryY) << (64 - keyAlgo.getBits());
+            fillIDs(keyPart1, foundEntries);
+
+            // When iteration == 0, I just check one tile (the center)
+            if (iteration > 0) {
+                long keyPart = keyAlgo.encode(subqueryXB, subqueryY) << (64 - keyAlgo.getBits());
+                fillIDs(keyPart, foundEntries);
             }
         }
 
-        // no early finish possible
-        return false;
-    }
-
-    final double calcMinDistance(double queryLat, double queryLon, GHIntHashSet pointset) {
-        double min = Double.MAX_VALUE;
-        Iterator<IntCursor> itr = pointset.iterator();
-        while (itr.hasNext()) {
-            int node = itr.next().value;
-            double lat = nodeAccess.getLat(node);
-            double lon = nodeAccess.getLon(node);
-            double dist = distCalc.calcDist(queryLat, queryLon, lat, lon);
-            if (dist < min) {
-                min = dist;
-            }
+        for (int xreg = -iteration + 1; xreg <= iteration - 1; xreg++) {
+            int subqueryX = x + xreg;
+            int subqueryYA = y - iteration;
+            int subqueryYB = y + iteration;
+            long keyPart1 = keyAlgo.encode(subqueryX, subqueryYA) << (64 - keyAlgo.getBits());
+            fillIDs(keyPart1, foundEntries);
+            long keyPart = keyAlgo.encode(subqueryX, subqueryYB) << (64 - keyAlgo.getBits());
+            fillIDs(keyPart, foundEntries);
         }
-        return min;
-    }
-
-    final void findNetworkEntriesSingleRegion(GHIntHashSet storedNetworkEntryIds, double queryLat, double queryLon) {
-        long keyPart = createReverseKey(queryLat, queryLon);
-        fillIDs(keyPart, START_POINTER, storedNetworkEntryIds, 0);
     }
 
     @Override
@@ -582,186 +490,49 @@ public class LocationIndexTree implements LocationIndex {
         if (isClosed())
             throw new IllegalStateException("You need to create a new LocationIndex instance as it is already closed");
 
-        GHIntHashSet allCollectedEntryIds = new GHIntHashSet();
         final Snap closestMatch = new Snap(queryLat, queryLon);
+        IntHashSet seenEdges = new IntHashSet();
         for (int iteration = 0; iteration < maxRegionSearch; iteration++) {
-            GHIntHashSet storedNetworkEntryIds = new GHIntHashSet();
-            boolean earlyFinish = findNetworkEntries(queryLat, queryLon, storedNetworkEntryIds, iteration);
-            storedNetworkEntryIds.removeAll(allCollectedEntryIds);
-            allCollectedEntryIds.addAll(storedNetworkEntryIds);
-
-            // clone storedIds to avoid interference with forEach
-            final GHBitSet checkBitset = new GHTBitSet(new GHIntHashSet(storedNetworkEntryIds));
-            // find nodes from the network entries which are close to 'point'
-            final EdgeExplorer explorer = graph.createEdgeExplorer();
-            storedNetworkEntryIds.forEach(new IntPredicate() {
-                @Override
-                public boolean apply(int networkEntryNodeId) {
-                    new XFirstSearchCheck(queryLat, queryLon, checkBitset, edgeFilter) {
-                        @Override
-                        protected double getQueryDistance() {
-                            return closestMatch.getQueryDistance();
+            findEdgeIdsInNeighborhood(queryLat, queryLon, iteration, edgeId -> {
+                EdgeIteratorState edgeIteratorState = graph.getEdgeIteratorStateForKey(edgeId * 2);
+                if (seenEdges.add(edgeId) && edgeFilter.accept(edgeIteratorState)) { // TODO: or reverse?
+                    traverseEdge(queryLat, queryLon, edgeIteratorState, (node, normedDist, wayIndex, pos) -> {
+                        if (normedDist < closestMatch.getQueryDistance()) {
+                            closestMatch.setQueryDistance(normedDist);
+                            closestMatch.setClosestNode(node);
+                            closestMatch.setClosestEdge(edgeIteratorState.detach(false));
+                            closestMatch.setWayIndex(wayIndex);
+                            closestMatch.setSnappedPosition(pos);
                         }
-
-                        @Override
-                        protected boolean check(int node, double normedDist, int wayIndex, EdgeIteratorState edge, Snap.Position pos) {
-                            if (normedDist < closestMatch.getQueryDistance()) {
-                                closestMatch.setQueryDistance(normedDist);
-                                closestMatch.setClosestNode(node);
-                                closestMatch.setClosestEdge(edge.detach(false));
-                                closestMatch.setWayIndex(wayIndex);
-                                closestMatch.setSnappedPosition(pos);
-                                return true;
-                            }
-                            return false;
-                        }
-                    }.start(explorer, networkEntryNodeId);
-                    return true;
+                    });
                 }
             });
-
-            // do early finish only if something was found (#318)
-            if (earlyFinish && closestMatch.isValid())
-                break;
+            if (closestMatch.isValid()) {
+                // Check if we can stop...
+                double rMin = calculateRMin(queryLat, queryLon, iteration);
+                double minDistance = DIST_PLANE.calcDenormalizedDist(closestMatch.getQueryDistance());
+                if (minDistance < rMin) {
+                    break; // We can (approximately?) guarantee that no closer edges are anywhere else
+                }
+            }
         }
 
-        // denormalize distance and calculate snapping point only if closed match was found
         if (closestMatch.isValid()) {
-            closestMatch.setQueryDistance(distCalc.calcDenormalizedDist(closestMatch.getQueryDistance()));
-            closestMatch.calcSnappedPoint(distCalc);
+            closestMatch.setQueryDistance(DIST_PLANE.calcDenormalizedDist(closestMatch.getQueryDistance()));
+            closestMatch.calcSnappedPoint(DIST_PLANE);
         }
-
         return closestMatch;
     }
 
-    /**
-     * Returns all edges that are within the specified radius around the queried position.
-     * Searches at most 9 cells to avoid performance problems. Hence, if the radius is larger than
-     * the cell width then not all edges might be returned.
-     * <p>
-     * TODO: either clarify the method name and description (to only search e.g. 9 tiles) or
-     * refactor so it can handle a radius larger than 9 tiles. Also remove reference to 'NClosest',
-     * which is misleading, and don't always return at least one value. See map-matching #65.
-     * TODO: tidy up logic - see comments in graphhopper #994.
-     *
-     * @param radius in meters
-     */
-    public List<Snap> findNClosest(final double queryLat, final double queryLon,
-                                   final EdgeFilter edgeFilter, double radius) {
-        // Return ALL results which are very close and e.g. within the GPS signal accuracy.
-        // Also important to get all edges if GPS point is close to a junction.
-        final double returnAllResultsWithin = distCalc.calcNormalizedDist(radius);
-
-        // implement a cheap priority queue via List, sublist and Collections.sort
-        final List<Snap> snaps = new ArrayList<>();
-        GHIntHashSet set = new GHIntHashSet();
-
-        // Doing 2 iterations means searching 9 tiles.
-        for (int iteration = 0; iteration < 2; iteration++) {
-            // should we use the return value of earlyFinish?
-            findNetworkEntries(queryLat, queryLon, set, iteration);
-
-            final GHBitSet exploredNodes = new GHTBitSet(new GHIntHashSet(set));
-            final EdgeExplorer explorer = graph.createEdgeExplorer(edgeFilter);
-
-            set.forEach(new IntPredicate() {
-
-                @Override
-                public boolean apply(int node) {
-                    new XFirstSearchCheck(queryLat, queryLon, exploredNodes, edgeFilter) {
-                        @Override
-                        protected double getQueryDistance() {
-                            // do not skip search if distance is 0 or near zero (equalNormedDelta)
-                            return Double.MAX_VALUE;
-                        }
-
-                        @Override
-                        protected boolean check(int node, double normedDist, int wayIndex, EdgeIteratorState edge, Snap.Position pos) {
-                            if (normedDist < returnAllResultsWithin
-                                    || snaps.isEmpty()
-                                    || snaps.get(0).getQueryDistance() > normedDist) {
-                                // TODO: refactor below:
-                                // - should only add edges within search radius (below allows the
-                                // returning of a candidate outside search radius if it's the only
-                                // one). Removing this test would simplify it a lot and probably
-                                // match the expected behaviour (see method description)
-                                // - create Snap first and the add/set as required - clean up
-                                // the index tracking business.
-
-                                int index = -1;
-                                for (int snapIndex = 0; snapIndex < snaps.size(); snapIndex++) {
-                                    Snap snap = snaps.get(snapIndex);
-                                    // overwrite older snaps which are potentially more far away than returnAllResultsWithin
-                                    if (snap.getQueryDistance() > returnAllResultsWithin) {
-                                        index = snapIndex;
-                                        break;
-                                    }
-
-                                    // avoid duplicate edges
-                                    if (snap.getClosestEdge().getEdge() == edge.getEdge()) {
-                                        if (snap.getQueryDistance() < normedDist) {
-                                            // do not add current edge
-                                            return true;
-                                        } else {
-                                            // overwrite old edge with current
-                                            index = snapIndex;
-                                            break;
-                                        }
-                                    }
-                                }
-
-                                Snap snap = new Snap(queryLat, queryLon);
-                                snap.setQueryDistance(normedDist);
-                                snap.setClosestNode(node);
-                                snap.setClosestEdge(edge.detach(false));
-                                snap.setWayIndex(wayIndex);
-                                snap.setSnappedPosition(pos);
-
-                                if (index < 0) {
-                                    snaps.add(snap);
-                                } else {
-                                    snaps.set(index, snap);
-                                }
-                            }
-                            return true;
-                        }
-                    }.start(explorer, node);
-                    return true;
-                }
-            });
-        }
-
-        // TODO: pass boolean argument for whether or not to sort? Can be expensive if not required.
-        Collections.sort(snaps, SNAP_COMPARATOR);
-
-        for (Snap snap : snaps) {
-            if (snap.isValid()) {
-                // denormalize distance
-                snap.setQueryDistance(distCalc.calcDenormalizedDist(snap.getQueryDistance()));
-                snap.calcSnappedPoint(distCalc);
-            } else {
-                throw new IllegalStateException("Invalid Snap should not happen here: " + snap);
-            }
-        }
-
-        return snaps;
-    }
-
     // make entries static as otherwise we get an additional reference to this class (memory waste)
     interface InMemEntry {
         boolean isLeaf();
     }
 
-    static class InMemLeafEntry extends SortedIntSet implements InMemEntry {
-        // private long key;
+    static class InMemLeafEntry extends IntArrayList implements InMemEntry {
 
-        public InMemLeafEntry(int count, long key) {
+        public InMemLeafEntry(int count) {
             super(count);
-            // this.key = key;
-        }
-
-        public boolean addNode(int nodeId) {
-            return addOnce(nodeId);
         }
 
         @Override
@@ -779,26 +550,6 @@ public class LocationIndexTree implements LocationIndex {
         }
     }
 
-    // Space efficient sorted integer set. Suited for only a few entries.
-    static class SortedIntSet extends IntArrayList {
-        SortedIntSet(int capacity) {
-            super(capacity);
-        }
-
-        /**
-         * Allow adding a value only once
-         */
-        public boolean addOnce(int value) {
-            int foundIndex = Arrays.binarySearch(buffer, 0, size(), value);
-            if (foundIndex >= 0) {
-                return false;
-            }
-            foundIndex = -foundIndex - 1;
-            insert(foundIndex, value);
-            return true;
-        }
-    }
-
     static class InMemTreeEntry implements InMemEntry {
         InMemEntry[] subEntries;
 
@@ -850,6 +601,7 @@ public class LocationIndexTree implements LocationIndex {
                 while (allIter.next()) {
                     if (!edgeFilter.accept(allIter))
                         continue;
+                    int edge = allIter.getEdge();
                     int nodeA = allIter.getBaseNode();
                     int nodeB = allIter.getAdjNode();
                     double lat1 = nodeAccess.getLatitude(nodeA);
@@ -861,13 +613,13 @@ public class LocationIndexTree implements LocationIndex {
                     for (int i = 0; i < len; i++) {
                         lat2 = points.getLatitude(i);
                         lon2 = points.getLongitude(i);
-                        addNode(nodeA, nodeB, lat1, lon1, lat2, lon2);
+                        addEdgeToAllTilesOnLine(edge, lat1, lon1, lat2, lon2);
                         lat1 = lat2;
                         lon1 = lon2;
                     }
                     lat2 = nodeAccess.getLatitude(nodeB);
                     lon2 = nodeAccess.getLongitude(nodeB);
-                    addNode(nodeA, nodeB, lat1, lon1, lat2, lon2);
+                    addEdgeToAllTilesOnLine(edge, lat1, lon1, lat2, lon2);
                 }
             } catch (Exception ex) {
                 logger.error("Problem! base:" + allIter.getBaseNode() + ", adj:" + allIter.getAdjNode()
@@ -875,91 +627,43 @@ public class LocationIndexTree implements LocationIndex {
             }
         }
 
-        void addNode(final int nodeA, final int nodeB,
-                     final double lat1, final double lon1,
-                     final double lat2, final double lon2) {
-            PointEmitter pointEmitter = new PointEmitter() {
-                @Override
-                public void set(double lat, double lon) {
-                    long key = keyAlgo.encode(lat, lon);
-                    long keyPart = createReverseKey(key);
-                    // no need to feed both nodes as we search neighbors in fillIDs
-                    addNode(root, nodeA, 0, keyPart, key);
-                }
-            };
-
-            if (!distCalc.isCrossBoundary(lon1, lon2)) {
-                BresenhamLine.calcPoints(lat1, lon1, lat2, lon2, pointEmitter,
-                        graph.getBounds().minLat, graph.getBounds().minLon,
-                        deltaLat, deltaLon);
+        void addEdgeToAllTilesOnLine(final int edgeId, final double lat1, final double lon1, final double lat2, final double lon2) {
+            if (!DIST_PLANE.isCrossBoundary(lon1, lon2)) {
+                // Find all the tiles on the line from (y1, x1) to (y2, y2) in tile coordinates (y, x)
+                pixelGridTraversal.traverse(new Coordinate(lon1, lat1), new Coordinate(lon2, lat2), p -> {
+                    long key = keyAlgo.encode((int) p.x, (int) p.y);
+                    addEdgeToOneTile(root, edgeId, 0, key << (64 - keyAlgo.getBits()));
+                });
             }
         }
 
-        void addNode(InMemEntry entry, int nodeId, int depth, long keyPart, long key) {
+        void addEdgeToOneTile(InMemEntry entry, int value, int depth, long keyPart) {
             if (entry.isLeaf()) {
                 InMemLeafEntry leafEntry = (InMemLeafEntry) entry;
-                leafEntry.addNode(nodeId);
+                // Avoid adding the same edge id multiple times.
+                // Since each edge id is handled only once, this can only happen when
+                // this method is called several times in a row with the same edge id,
+                // so it is enough to check the last entry.
+                // (It happens when one edge has several segments. Every segment is traversed
+                // on its own, without de-duplicating the tiles that are touched.)
+                if (leafEntry.isEmpty() || leafEntry.get(leafEntry.size()-1) != value) {
+                    leafEntry.add(value);
+                }
             } else {
-                int index = (int) (bitmasks[depth] & keyPart);
-                keyPart = keyPart >>> shifts[depth];
+                int index = (int) (keyPart >>> (64 - shifts[depth]));
+                keyPart = keyPart << shifts[depth];
                 InMemTreeEntry treeEntry = ((InMemTreeEntry) entry);
                 InMemEntry subentry = treeEntry.getSubEntry(index);
                 depth++;
                 if (subentry == null) {
                     if (depth == entries.length) {
-                        subentry = new InMemLeafEntry(initSizeLeafEntries, key);
+                        subentry = new InMemLeafEntry(4);
                     } else {
                         subentry = new InMemTreeEntry(entries[depth]);
                     }
                     treeEntry.setSubEntry(index, subentry);
                 }
-
-                addNode(subentry, nodeId, depth, keyPart, key);
-            }
-        }
-
-        Collection<InMemEntry> getEntriesOf(int selectDepth) {
-            List<InMemEntry> list = new ArrayList<>();
-            fillLayer(list, selectDepth, 0, root.getSubEntriesForDebug());
-            return list;
-        }
-
-        void fillLayer(Collection<InMemEntry> list, int selectDepth, int depth, Collection<InMemEntry> entries) {
-            for (InMemEntry entry : entries) {
-                if (selectDepth == depth) {
-                    list.add(entry);
-                } else if (entry instanceof InMemTreeEntry) {
-                    fillLayer(list, selectDepth, depth + 1, ((InMemTreeEntry) entry).getSubEntriesForDebug());
-                }
-            }
-        }
-
-        String print() {
-            StringBuilder sb = new StringBuilder();
-            print(root, sb, 0, 0);
-            return sb.toString();
-        }
-
-        void print(InMemEntry e, StringBuilder sb, long key, int depth) {
-            if (e.isLeaf()) {
-                InMemLeafEntry leaf = (InMemLeafEntry) e;
-                int bits = keyAlgo.getBits();
-                // print reverse keys
-                sb.append(BitUtil.BIG.toBitString(BitUtil.BIG.reverse(key, bits), bits)).append("  ");
-                IntArrayList entries = leaf.getResults();
-                for (int i = 0; i < entries.size(); i++) {
-                    sb.append(leaf.get(i)).append(',');
-                }
-                sb.append('\n');
-            } else {
-                InMemTreeEntry tree = (InMemTreeEntry) e;
-                key = key << shifts[depth];
-                for (int counter = 0; counter < tree.subEntries.length; counter++) {
-                    InMemEntry sube = tree.subEntries[counter];
-                    if (sube != null) {
-                        print(sube, sb, key | counter, depth + 1);
-                    }
-                }
+                addEdgeToOneTile(subentry, value, depth, keyPart);
             }
         }
 
@@ -1009,105 +713,65 @@ public class LocationIndexTree implements LocationIndex {
         }
     }
 
-    /**
-     * Make it possible to collect nearby location also for other purposes.
-     */
-    protected abstract class XFirstSearchCheck extends BreadthFirstSearch {
-        final double queryLat;
-        final double queryLon;
-        final GHBitSet checkBitset;
-        final EdgeFilter edgeFilter;
-        boolean goFurther = true;
-        double currNormedDist;
-        double currLat;
-        double currLon;
-        int currNode;
-
-        public XFirstSearchCheck(double queryLat, double queryLon, GHBitSet checkBitset, EdgeFilter edgeFilter) {
-            this.queryLat = queryLat;
-            this.queryLon = queryLon;
-            this.checkBitset = checkBitset;
-            this.edgeFilter = edgeFilter;
-        }
-
-        @Override
-        protected GHBitSet createBitSet() {
-            return checkBitset;
-        }
+    public interface EdgeCheck {
+        void check(int node, double normedDist, int wayIndex, Snap.Position pos);
+    }
 
-        @Override
-        protected boolean goFurther(int baseNode) {
-            currNode = baseNode;
-            currLat = nodeAccess.getLatitude(baseNode);
-            currLon = nodeAccess.getLongitude(baseNode);
-            currNormedDist = distCalc.calcNormalizedDist(queryLat, queryLon, currLat, currLon);
-            return goFurther;
-        }
+    public void traverseEdge(double queryLat, double queryLon, EdgeIteratorState currEdge, EdgeCheck edgeCheck) {
+        int baseNode = currEdge.getBaseNode();
+        double currLat = nodeAccess.getLatitude(baseNode);
+        double currLon = nodeAccess.getLongitude(baseNode);
+        double currNormedDist = DIST_PLANE.calcNormalizedDist(queryLat, queryLon, currLat, currLon);
 
-        @Override
-        protected boolean checkAdjacent(EdgeIteratorState currEdge) {
-            goFurther = false;
-            if (!edgeFilter.accept(currEdge)) {
-                // only limit the adjNode to a certain radius as currNode could be the wrong side of a valid edge
-                // goFurther = currDist < minResolution2InMeterNormed;
-                return true;
-            }
+        int tmpClosestNode = baseNode;
+        edgeCheck.check(tmpClosestNode, currNormedDist, 0, Snap.Position.TOWER);
+        if (currNormedDist <= equalNormedDelta)
+            return;
 
-            int tmpClosestNode = currNode;
-            if (check(tmpClosestNode, currNormedDist, 0, currEdge, Snap.Position.TOWER)) {
-                if (currNormedDist <= equalNormedDelta)
-                    return false;
+        int adjNode = currEdge.getAdjNode();
+        double adjLat = nodeAccess.getLatitude(adjNode);
+        double adjLon = nodeAccess.getLongitude(adjNode);
+        double adjDist = DIST_PLANE.calcNormalizedDist(adjLat, adjLon, queryLat, queryLon);
+        // if there are wayPoints this is only an approximation
+        if (adjDist < currNormedDist)
+            tmpClosestNode = adjNode;
+
+        double tmpLat = currLat;
+        double tmpLon = currLon;
+        double tmpNormedDist;
+        PointList pointList = currEdge.fetchWayGeometry(FetchMode.PILLAR_AND_ADJ);
+        int len = pointList.getSize();
+        for (int pointIndex = 0; pointIndex < len; pointIndex++) {
+            double wayLat = pointList.getLatitude(pointIndex);
+            double wayLon = pointList.getLongitude(pointIndex);
+            Snap.Position pos = Snap.Position.EDGE;
+            if (DIST_PLANE.isCrossBoundary(tmpLon, wayLon)) {
+                tmpLat = wayLat;
+                tmpLon = wayLon;
+                continue;
             }
 
-            int adjNode = currEdge.getAdjNode();
-            double adjLat = nodeAccess.getLatitude(adjNode);
-            double adjLon = nodeAccess.getLongitude(adjNode);
-            double adjDist = distCalc.calcNormalizedDist(adjLat, adjLon, queryLat, queryLon);
-            // if there are wayPoints this is only an approximation
-            if (adjDist < currNormedDist)
-                tmpClosestNode = adjNode;
-
-            double tmpLat = currLat;
-            double tmpLon = currLon;
-            double tmpNormedDist;
-            PointList pointList = currEdge.fetchWayGeometry(FetchMode.PILLAR_AND_ADJ);
-            int len = pointList.getSize();
-            for (int pointIndex = 0; pointIndex < len; pointIndex++) {
-                double wayLat = pointList.getLatitude(pointIndex);
-                double wayLon = pointList.getLongitude(pointIndex);
-                Snap.Position pos = Snap.Position.EDGE;
-                if (distCalc.isCrossBoundary(tmpLon, wayLon)) {
-                    tmpLat = wayLat;
-                    tmpLon = wayLon;
-                    continue;
-                }
-
-                if (distCalc.validEdgeDistance(queryLat, queryLon, tmpLat, tmpLon, wayLat, wayLon)) {
-                    tmpNormedDist = distCalc.calcNormalizedEdgeDistance(queryLat, queryLon,
-                            tmpLat, tmpLon, wayLat, wayLon);
-                    check(tmpClosestNode, tmpNormedDist, pointIndex, currEdge, pos);
+            if (DIST_PLANE.validEdgeDistance(queryLat, queryLon, tmpLat, tmpLon, wayLat, wayLon)) {
+                tmpNormedDist = DIST_PLANE.calcNormalizedEdgeDistance(queryLat, queryLon,
+                        tmpLat, tmpLon, wayLat, wayLon);
+                edgeCheck.check(tmpClosestNode, tmpNormedDist, pointIndex, pos);
+            } else {
+                if (pointIndex + 1 == len) {
+                    tmpNormedDist = adjDist;
+                    pos = Snap.Position.TOWER;
                 } else {
-                    if (pointIndex + 1 == len) {
-                        tmpNormedDist = adjDist;
-                        pos = Snap.Position.TOWER;
-                    } else {
-                        tmpNormedDist = distCalc.calcNormalizedDist(queryLat, queryLon, wayLat, wayLon);
-                        pos = Snap.Position.PILLAR;
-                    }
-                    check(tmpClosestNode, tmpNormedDist, pointIndex + 1, currEdge, pos);
+                    tmpNormedDist = DIST_PLANE.calcNormalizedDist(queryLat, queryLon, wayLat, wayLon);
+                    pos = Snap.Position.PILLAR;
                 }
-
-                if (tmpNormedDist <= equalNormedDelta)
-                    return false;
-
-                tmpLat = wayLat;
-                tmpLon = wayLon;
+                edgeCheck.check(tmpClosestNode, tmpNormedDist, pointIndex + 1, pos);
             }
-            return getQueryDistance() > equalNormedDelta;
-        }
 
-        protected abstract double getQueryDistance();
+            if (tmpNormedDist <= equalNormedDelta)
+                return;
 
-        protected abstract boolean check(int node, double normedDist, int wayIndex, EdgeIteratorState iter, Snap.Position pos);
+            tmpLat = wayLat;
+            tmpLon = wayLon;
+        }
     }
+
 }
diff --git a/core/src/main/java/com/graphhopper/storage/index/PixelGridTraversal.java b/core/src/main/java/com/graphhopper/storage/index/PixelGridTraversal.java
new file mode 100644
index 000000000..173f48b51
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/storage/index/PixelGridTraversal.java
@@ -0,0 +1,78 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.storage.index;
+
+import com.graphhopper.util.shapes.BBox;
+import org.locationtech.jts.geom.Coordinate;
+
+import java.util.function.Consumer;
+
+/**
+ * We need all grid cells intersected by a line. The best algorithm is a 'voxel grid traversal algorithm' and
+ * described in "A Fast Voxel Traversal Algorithm for Ray Tracing" by John Amanatides and Andrew Woo
+ * (1987): http://www.cse.yorku.ca/~amana/research/grid.pdf
+ *
+ * @author Michael Zilske
+ */
+public class PixelGridTraversal {
+
+    private final double deltaY;
+    private final double deltaX;
+    int parts;
+    BBox bounds;
+
+    public PixelGridTraversal(int parts, BBox bounds) {
+        this.parts = parts;
+        this.bounds = bounds;
+        deltaY = (bounds.maxLat - bounds.minLat) / parts;
+        deltaX = (bounds.maxLon - bounds.minLon) / parts;
+    }
+
+    public void traverse(Coordinate a, Coordinate b, Consumer<Coordinate> consumer) {
+        double ax = a.x - bounds.minLon;
+        double ay = a.y - bounds.minLat;
+        double bx = b.x - bounds.minLon;
+        double by = b.y - bounds.minLat;
+
+        int stepX = ax < bx ? 1 : -1;
+        int stepY = ay < by ? 1 : -1;
+        double tDeltaX = deltaX / Math.abs(bx - ax);
+        double tDeltaY = deltaY / Math.abs(by - ay);
+
+        // Bounding this with parts - 1 only concerns the case where we are exactly on the bounding box.
+        // (The next cell would already start there..)
+        int x = Math.min((int) (ax / deltaX), parts - 1);
+        int y = Math.min((int) (ay / deltaY), parts - 1);
+        int x2 = Math.min((int) (bx / deltaX), parts - 1);
+        int y2 = Math.min((int) (by / deltaY), parts - 1);
+        double tMaxX =  ((x + (stepX < 0 ? 0 : 1)) * deltaX - ax) / (bx - ax);
+        double tMaxY =  ((y + (stepY < 0 ? 0 : 1)) * deltaY - ay) / (by - ay);
+
+        consumer.accept(new Coordinate(x, y));
+        while (y != y2 || x != x2) {
+            if ((tMaxX < tMaxY || y == y2) && x != x2) {
+                tMaxX += tDeltaX;
+                x += stepX;
+            } else {
+                tMaxY += tDeltaY;
+                y += stepY;
+            }
+            consumer.accept(new Coordinate(x, y));
+        }
+    }
+}
diff --git a/core/src/main/java/com/graphhopper/storage/index/PointEmitter.java b/core/src/main/java/com/graphhopper/storage/index/PointEmitter.java
deleted file mode 100644
index 735dfb590..000000000
--- a/core/src/main/java/com/graphhopper/storage/index/PointEmitter.java
+++ /dev/null
@@ -1,25 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-/**
- * @author Peter Karich
- */
-public interface PointEmitter {
-    void set(double lat, double lon);
-}
diff --git a/core/src/main/java/com/graphhopper/storage/index/Snap.java b/core/src/main/java/com/graphhopper/storage/index/Snap.java
index e97f49c60..3a2e401ab 100644
--- a/core/src/main/java/com/graphhopper/storage/index/Snap.java
+++ b/core/src/main/java/com/graphhopper/storage/index/Snap.java
@@ -76,12 +76,6 @@ public class Snap {
         queryDistance = dist;
     }
 
-    /**
-     * References to a tower node or the index of wayGeometry of the closest edge. If wayGeometry
-     * has length L then the wayIndex 0 refers to the *base* node, 1 to L (inclusive) refer to the
-     * wayGeometry indices (minus one) and L+1 to the *adjacent* node. Currently only initialized if
-     * returned from Location2NodesNtree.
-     */
     public int getWayIndex() {
         return wayIndex;
     }
@@ -102,15 +96,12 @@ public class Snap {
     }
 
     /**
-     * @return true if a close node was found
+     * @return true if a closest node was found
      */
     public boolean isValid() {
         return closestNode >= 0;
     }
 
-    /**
-     * @return the closest matching edge. Will be null if nothing found or call isValid before
-     */
     public EdgeIteratorState getClosestEdge() {
         return closestEdge;
     }
@@ -134,7 +125,7 @@ public class Snap {
     }
 
     /**
-     * Calculates the closet point on the edge from the query point.
+     * Calculates the closest point on the edge from the query point.
      */
     public void calcSnappedPoint(DistanceCalc distCalc) {
         if (closestEdge == null)
@@ -183,7 +174,7 @@ public class Snap {
      *
      * @see DistanceCalc#validEdgeDistance
      */
-    public static enum Position {
+    public enum Position {
         EDGE, TOWER, PILLAR
     }
 }
diff --git a/core/src/main/java/com/graphhopper/util/BitUtil.java b/core/src/main/java/com/graphhopper/util/BitUtil.java
index e7733cbb9..acd38752c 100644
--- a/core/src/main/java/com/graphhopper/util/BitUtil.java
+++ b/core/src/main/java/com/graphhopper/util/BitUtil.java
@@ -148,25 +148,6 @@ public abstract class BitUtil {
 
     public abstract void fromLong(byte[] bytes, long value, int offset);
 
-    /**
-     * The only purpose of this method is to test 'reverse'. toBitString is the reverse and both are
-     * independent of the endianness.
-     */
-    public final long fromBitString2Long(String str) {
-        if (str.length() > 64)
-            throw new UnsupportedOperationException("Strings needs to fit into a 'long' but length was " + str.length());
-
-        long res = 0;
-        int strLen = str.length();
-        for (int charIndex = 0; charIndex < strLen; charIndex++) {
-            res <<= 1;
-            if (str.charAt(charIndex) != '0')
-                res |= 1;
-        }
-        res <<= (64 - strLen);
-        return res;
-    }
-
     public abstract byte[] fromBitString(String str);
 
     public final String toBitString(IntsRef intsRef) {
@@ -223,27 +204,6 @@ public abstract class BitUtil {
      */
     public abstract String toBitString(byte[] bytes);
 
-    /**
-     * Reverses the bits in the specified long value and it removes the remaining higher bits. See
-     * also http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
-     * <p>
-     *
-     * @param maxBits the maximum number of recognized bits for reversal
-     */
-    public final long reverse(long value, int maxBits) {
-        long res = 0;
-        for (; maxBits > 0; value >>>= 1) {
-            res <<= 1;
-            res |= value & 1;
-            maxBits--;
-            if (value == 0) {
-                res <<= maxBits;
-                break;
-            }
-        }
-        return res;
-    }
-
     public final int getIntLow(long longValue) {
         return (int) (longValue & 0xFFFFFFFFL);
     }
@@ -256,21 +216,4 @@ public abstract class BitUtil {
         return ((long) intHigh << 32) | (intLow & 0xFFFFFFFFL);
     }
 
-    public final long reverseLeft(long value, int maxBits) {
-        long res = 0;
-        int delta = 64 - maxBits;
-        long maxBit = 1L << delta;
-        for (; maxBits > 0; res <<= 1) {
-            if ((value & maxBit) != 0)
-                res |= 1;
-
-            maxBit <<= 1;
-            maxBits--;
-            if (maxBit == 0) {
-                res <<= delta;
-                break;
-            }
-        }
-        return res;
-    }
 }
diff --git a/core/src/main/java/com/graphhopper/util/BitUtilBig.java b/core/src/main/java/com/graphhopper/util/BitUtilBig.java
index 0aaffaf3b..d20c98759 100644
--- a/core/src/main/java/com/graphhopper/util/BitUtilBig.java
+++ b/core/src/main/java/com/graphhopper/util/BitUtilBig.java
@@ -115,14 +115,6 @@ public class BitUtilBig extends BitUtil {
         return sb.toString();
     }
 
-    /**
-     * Touches only the specified bits - it does not zero out the higher bits (like reverse does).
-     */
-    final long reversePart(long v, int maxBits) {
-        long rest = v & (~((1L << maxBits) - 1));
-        return rest | reverse(v, maxBits);
-    }
-
     @Override
     public String toString() {
         return "big";
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 d682116b1..2f4decf45 100644
--- a/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java
+++ b/map-matching/src/main/java/com/graphhopper/matching/MapMatching.java
@@ -20,28 +20,37 @@ package com.graphhopper.matching;
 import com.bmw.hmm.SequenceState;
 import com.bmw.hmm.Transition;
 import com.bmw.hmm.ViterbiAlgorithm;
+import com.carrotsearch.hppc.IntHashSet;
 import com.graphhopper.GraphHopper;
 import com.graphhopper.config.LMProfile;
 import com.graphhopper.config.Profile;
-import com.graphhopper.routing.*;
+import com.graphhopper.routing.AStarBidirection;
+import com.graphhopper.routing.BidirRoutingAlgorithm;
+import com.graphhopper.routing.DijkstraBidirectionRef;
+import com.graphhopper.routing.Path;
 import com.graphhopper.routing.lm.LMApproximator;
 import com.graphhopper.routing.lm.LandmarkStorage;
 import com.graphhopper.routing.lm.PrepareLandmarks;
 import com.graphhopper.routing.querygraph.QueryGraph;
 import com.graphhopper.routing.querygraph.VirtualEdgeIteratorState;
 import com.graphhopper.routing.util.DefaultEdgeFilter;
+import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.*;
+import com.graphhopper.util.shapes.BBox;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
 import java.util.*;
 import java.util.stream.Collectors;
 
+import static com.graphhopper.util.DistancePlaneProjection.DIST_PLANE;
+
 /**
  * This class matches real world GPX entries to the digital road network stored
  * in GraphHopper. The Viterbi algorithm is used to compute the most likely
@@ -157,23 +166,17 @@ public class MapMatching {
         List<Observation> filteredObservations = filterObservations(observations);
 
         // Snap observations to links. Generates multiple candidate snaps per observation.
-        // In the next step, we will turn them into splits, but we already call them splits now
-        // because they are modified in place.
-        List<Collection<Snap>> splitsPerObservation = filteredObservations.stream().map(o -> locationIndex.findNClosest(o.getPoint().lat, o.getPoint().lon, DefaultEdgeFilter.allEdges(weighting.getFlagEncoder()), measurementErrorSigma))
+        List<Collection<Snap>> snapsPerObservation = filteredObservations.stream()
+                .map(o -> findCandidateSnaps(o.getPoint().lat, o.getPoint().lon))
                 .collect(Collectors.toList());
 
         // Create the query graph, containing split edges so that all the places where an observation might have happened
         // are a node. This modifies the Snap objects and puts the new node numbers into them.
-        queryGraph = QueryGraph.create(graph, splitsPerObservation.stream().flatMap(Collection::stream).collect(Collectors.toList()));
-
-        // Due to how LocationIndex/QueryGraph is implemented, we can get duplicates when a point is snapped
-        // directly to a tower node instead of creating a split / virtual node. No problem, but we still filter
-        // out the duplicates for performance reasons.
-        splitsPerObservation = splitsPerObservation.stream().map(this::deduplicate).collect(Collectors.toList());
+        queryGraph = QueryGraph.create(graph, snapsPerObservation.stream().flatMap(Collection::stream).collect(Collectors.toList()));
 
         // Creates candidates from the Snaps of all observations (a candidate is basically a
         // Snap + direction).
-        List<ObservationWithCandidateStates> timeSteps = createTimeSteps(filteredObservations, splitsPerObservation);
+        List<ObservationWithCandidateStates> timeSteps = createTimeSteps(filteredObservations, snapsPerObservation);
 
         // Compute the most likely sequence of map matching candidates:
         List<SequenceState<State, Observation, Path>> seq = computeViterbiSequence(timeSteps);
@@ -212,10 +215,39 @@ public class MapMatching {
         return filtered;
     }
 
-    private Collection<Snap> deduplicate(Collection<Snap> splits) {
-        // Only keep one split per node number. Let's say the last one.
-        Map<Integer, Snap> splitsByNodeNumber = splits.stream().collect(Collectors.toMap(Snap::getClosestNode, s -> s, (s1, s2) -> s2));
-        return splitsByNodeNumber.values();
+    public List<Snap> findCandidateSnaps(final double queryLat, final double queryLon) {
+        EdgeFilter edgeFilter = DefaultEdgeFilter.allEdges(weighting.getFlagEncoder());
+        double rLon = (measurementErrorSigma * 360.0 / DistanceCalcEarth.DIST_EARTH.calcCircumference(queryLat));
+        double rLat = measurementErrorSigma / DistanceCalcEarth.METERS_PER_DEGREE;
+        List<Snap> snaps = new ArrayList<>();
+        IntHashSet seenEdges = new IntHashSet();
+        IntHashSet seenNodes = new IntHashSet();
+        locationIndex.query(new BBox(queryLon - rLon, queryLon + rLon, queryLat - rLat, queryLat + rLat),
+                new LocationIndex.Visitor() {
+                    @Override
+                    public void onEdge(int edgeId) {
+                        EdgeIteratorState edge = graph.getEdgeIteratorStateForKey(edgeId * 2).detach(false);
+                        if (seenEdges.add(edgeId) && edgeFilter.accept(edge)) {
+                            Snap snap = new Snap(queryLat, queryLon);
+                            snap.setClosestEdge(edge);
+                            locationIndex.traverseEdge(queryLat, queryLon, edge, (node, normedDist, wayIndex, pos) -> {
+                                if ((pos != Snap.Position.TOWER || seenNodes.add(node)) && normedDist < snap.getQueryDistance()) {
+                                    snap.setQueryDistance(normedDist);
+                                    snap.setClosestNode(node);
+                                    snap.setWayIndex(wayIndex);
+                                    snap.setSnappedPosition(pos);
+                                }
+                            });
+                            double dist = DIST_PLANE.calcDenormalizedDist(snap.getQueryDistance());
+                            if (dist <= measurementErrorSigma) {
+                                snap.setQueryDistance(dist);
+                                snap.calcSnappedPoint(DistanceCalcEarth.DIST_EARTH);
+                                snaps.add(snap);
+                            }
+                        }
+                    }
+                });
+        return snaps;
     }
 
     /**
diff --git a/reader-gtfs/src/main/java/com/graphhopper/gtfs/EmptyLocationIndex.java b/reader-gtfs/src/main/java/com/graphhopper/gtfs/EmptyLocationIndex.java
deleted file mode 100644
index c054e437e..000000000
--- a/reader-gtfs/src/main/java/com/graphhopper/gtfs/EmptyLocationIndex.java
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-
-package com.graphhopper.gtfs;
-
-import com.graphhopper.routing.util.EdgeFilter;
-import com.graphhopper.storage.index.LocationIndex;
-import com.graphhopper.storage.index.Snap;
-import com.graphhopper.util.shapes.BBox;
-
-class EmptyLocationIndex implements LocationIndex {
-    @Override
-    public LocationIndex setResolution(int resolution) {
-        return this;
-    }
-
-    @Override
-    public LocationIndex prepareIndex() {
-        return this;
-    }
-
-    @Override
-    public Snap findClosest(double lat, double lon, EdgeFilter edgeFilter) {
-        return new Snap(lat, lon);
-    }
-
-    @Override
-    public void query(BBox queryBBox, Visitor function) {
-    }
-
-    @Override
-    public LocationIndex setApproximation(boolean approxDist) {
-        return this;
-    }
-
-    @Override
-    public void setSegmentSize(int bytes) {
-    }
-
-    @Override
-    public boolean loadExisting() {
-        return false;
-    }
-
-    @Override
-    public LocationIndex create(long byteCount) {
-        return this;
-    }
-
-    @Override
-    public void flush() {
-    }
-
-    @Override
-    public void close() {
-    }
-
-    @Override
-    public boolean isClosed() {
-        return false;
-    }
-
-    @Override
-    public long getCapacity() {
-        return 0;
-    }
-}
diff --git a/reader-gtfs/src/main/java/com/graphhopper/gtfs/GraphHopperGtfs.java b/reader-gtfs/src/main/java/com/graphhopper/gtfs/GraphHopperGtfs.java
index 208175c15..ea4395b3a 100644
--- a/reader-gtfs/src/main/java/com/graphhopper/gtfs/GraphHopperGtfs.java
+++ b/reader-gtfs/src/main/java/com/graphhopper/gtfs/GraphHopperGtfs.java
@@ -27,7 +27,6 @@ import com.graphhopper.reader.osm.GraphHopperOSM;
 import com.graphhopper.routing.ev.EnumEncodedValue;
 import com.graphhopper.routing.querygraph.QueryGraph;
 import com.graphhopper.routing.util.DefaultEdgeFilter;
-import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.EncodingManager;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.storage.Directory;
@@ -128,15 +127,11 @@ public class GraphHopperGtfs extends GraphHopperOSM {
         if (tmpIndex.loadExisting()) {
             return tmpIndex;
         } else {
-            if (getGraphHopperStorage().getNodes() > 0) {
-                LocationIndexTree locationIndexTree = new LocationIndexTree(getGraphHopperStorage(), new RAMDirectory());
-                if (!locationIndexTree.loadExisting()) {
-                    locationIndexTree.prepareIndex();
-                }
-                return locationIndexTree;
-            } else {
-                return new EmptyLocationIndex();
+            LocationIndexTree locationIndexTree = new LocationIndexTree(getGraphHopperStorage(), new RAMDirectory());
+            if (!locationIndexTree.loadExisting()) {
+                locationIndexTree.prepareIndex();
             }
+            return locationIndexTree;
         }
     }
 
diff --git a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
index 15b5eea05..8cd145b71 100644
--- a/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
+++ b/tools/src/main/java/com/graphhopper/ui/MiniGraphUI.java
@@ -257,7 +257,7 @@ public class MiniGraphUI {
                     }
 
                     @Override
-                    public void onNode(int node) {
+                    public void onEdge(int edgeId) {
                         // mg.plotNode(g2, node, Color.BLUE);
                     }
                 });
diff --git a/web-bundle/src/main/java/com/graphhopper/resources/MVTResource.java b/web-bundle/src/main/java/com/graphhopper/resources/MVTResource.java
index 0beb4299a..c45bb0e37 100644
--- a/web-bundle/src/main/java/com/graphhopper/resources/MVTResource.java
+++ b/web-bundle/src/main/java/com/graphhopper/resources/MVTResource.java
@@ -93,9 +93,10 @@ public class MVTResource {
         final MvtLayerProps layerProps = new MvtLayerProps();
         final VectorTile.Tile.Layer.Builder layerBuilder = MvtLayerBuild.newLayerBuilder("roads", layerParams);
 
-        locationIndex.query(bbox, new LocationIndexTree.EdgeVisitor(edgeExplorer) {
+        locationIndex.query(bbox, new LocationIndexTree.Visitor() {
             @Override
-            public void onEdge(EdgeIteratorState edge, int nodeA, int nodeB) {
+            public void onEdge(int edgeId) {
+                EdgeIteratorState edge = graphHopper.getGraphHopperStorage().getEdgeIteratorStateForKey(edgeId * 2);
                 LineString lineString;
                 RoadClass rc = edge.get(roadClassEnc);
                 if (zInfo >= 14) {
@@ -105,10 +106,10 @@ public class MVTResource {
                         || zInfo > 10 && (rc == RoadClass.PRIMARY || rc == RoadClass.TRUNK)
                         || zInfo > 11 && (rc == RoadClass.SECONDARY)
                         || zInfo > 12) {
-                    double lat = na.getLatitude(nodeA);
-                    double lon = na.getLongitude(nodeA);
-                    double toLat = na.getLatitude(nodeB);
-                    double toLon = na.getLongitude(nodeB);
+                    double lat = na.getLatitude(edge.getBaseNode());
+                    double lon = na.getLongitude(edge.getBaseNode());
+                    double toLat = na.getLatitude(edge.getAdjNode());
+                    double toLon = na.getLongitude(edge.getAdjNode());
                     lineString = geometryFactory.createLineString(new Coordinate[]{new Coordinate(lon, lat), new Coordinate(toLon, toLat)});
                 } else {
                     // skip edge for certain zoom
@@ -140,11 +141,14 @@ public class MVTResource {
                 TileGeomResult tileGeom = JtsAdapter.createTileGeom(lineString, tileEnvelope, geometryFactory, layerParams, acceptAllGeomFilter);
                 List<VectorTile.Tile.Feature> features = JtsAdapter.toFeatures(tileGeom.mvtGeoms, layerProps, converter);
                 layerBuilder.addAllFeatures(features);
-            }
 
+
+
+            }
             @Override
             public void onTile(BBox bbox, int depth) {
             }
+
         });
 
         MvtLayerBuild.writeProps(layerBuilder, layerProps);
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 ce267fba4..970977c29 100644
--- a/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java
+++ b/web-bundle/src/main/java/com/graphhopper/resources/PtIsochroneResource.java
@@ -32,6 +32,7 @@ import com.graphhopper.storage.GraphHopperStorage;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.Snap;
+import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
 import org.locationtech.jts.geom.*;
@@ -128,9 +129,10 @@ public class PtIsochroneResource {
             // I think then we should have all possible encroaching points. (Proof needed.)
             locationIndex.query(BBox.fromEnvelope(exploredPoints.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);
+                public void onEdge(int edgeId) {
+                    EdgeIteratorState edge = queryGraph.getEdgeIteratorStateForKey(edgeId * 2);
+                    z1.merge(new Coordinate(nodeAccess.getLongitude(edge.getBaseNode()), nodeAccess.getLatitude(edge.getBaseNode())), Double.MAX_VALUE, Math::min);
+                    z1.merge(new Coordinate(nodeAccess.getLongitude(edge.getAdjNode()), nodeAccess.getLatitude(edge.getAdjNode())), Double.MAX_VALUE, Math::min);
                 }
             });
             exploredPoints = geometryFactory.createMultiPointFromCoords(z1.keySet().toArray(new Coordinate[0]));
diff --git a/web/src/main/java/com/graphhopper/http/cli/MeasurementCommand.java b/web/src/main/java/com/graphhopper/http/cli/MeasurementCommand.java
index 7c72a4dcf..a34e193da 100644
--- a/web/src/main/java/com/graphhopper/http/cli/MeasurementCommand.java
+++ b/web/src/main/java/com/graphhopper/http/cli/MeasurementCommand.java
@@ -27,9 +27,7 @@ import com.graphhopper.matching.MapMatching;
 import com.graphhopper.matching.MatchResult;
 import com.graphhopper.matching.Observation;
 import com.graphhopper.reader.osm.GraphHopperOSM;
-import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.storage.GraphHopperStorage;
-import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
@@ -96,12 +94,10 @@ public class MeasurementCommand extends ConfiguredCommand<GraphHopperServerConfi
 
         GraphHopperStorage graph = graphHopper.getGraphHopperStorage();
         bbox = graph.getBounds();
-        LocationIndexTree locationIndex = (LocationIndexTree) graphHopper.getLocationIndex();
         MapMatching mapMatching = new MapMatching(graphHopper, new PMap().putObject("profile", profile.getName()));
 
         StopWatch sw = new StopWatch().start();
         try {
-            printLocationIndexMatchQuery(locationIndex);
             printTimeOfMapMatchQuery(graphHopper, mapMatching);
             System.gc();
         } catch (Exception ex) {
@@ -130,23 +126,6 @@ public class MeasurementCommand extends ConfiguredCommand<GraphHopperServerConfi
         }
     }
 
-    /**
-     * Test the performance of finding candidate points for the index (which is run for every GPX
-     * entry).
-     */
-    private void printLocationIndexMatchQuery(final LocationIndexTree idx) {
-        final double latDelta = bbox.maxLat - bbox.minLat;
-        final double lonDelta = bbox.maxLon - bbox.minLon;
-        final Random rand = new Random(seed);
-        MiniPerfTest miniPerf = new MiniPerfTest()
-                .setIterations(count).start((warmup, run) -> {
-                    double lat = rand.nextDouble() * latDelta + bbox.minLat;
-                    double lon = rand.nextDouble() * lonDelta + bbox.minLon;
-                    return idx.findNClosest(lat, lon, EdgeFilter.ALL_EDGES, rand.nextDouble() * 500).size();
-                });
-        print("location_index_match", miniPerf);
-    }
-
     /**
      * Test the time taken for map matching on random routes. Note that this includes the index
      * lookups (previous tests), so will be affected by those. Otherwise this is largely testing the
@@ -176,7 +155,7 @@ public class MeasurementCommand extends ConfiguredCommand<GraphHopperServerConfi
                         if (!r.hasErrors()) {
                             double sampleProportion = rand.nextDouble();
                             GHPoint prev = null;
-                            List<Observation> mock = new ArrayList<>();
+                            List<Observation> observations = new ArrayList<>();
                             PointList points = r.getBest().getPoints();
                             // loop through points and add (approximately) sampleProportion of them:
                             for (GHPoint p : points) {
@@ -185,13 +164,13 @@ public class MeasurementCommand extends ConfiguredCommand<GraphHopperServerConfi
                                     // exactly on the route):
                                     GHPoint randomised = distCalc.projectCoordinate(p.lat, p.lon,
                                             20 * rand.nextDouble(), 360 * rand.nextDouble());
-                                    mock.add(new Observation(randomised));
+                                    observations.add(new Observation(randomised));
                                 }
                                 prev = p;
                             }
                             // now match, provided there are enough points
-                            if (mock.size() > 2) {
-                                MatchResult match = mapMatching.match(mock);
+                            if (observations.size() > 2) {
+                                MatchResult match = mapMatching.match(observations);
                                 // return something non-trivial, to avoid JVM optimizing away
                                 return match.getEdgeMatches().size();
                             }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/coll/CompressedArrayTest.java b/core/src/test/java/com/graphhopper/coll/CompressedArrayTest.java
deleted file mode 100644
index e4034e311..000000000
--- a/core/src/test/java/com/graphhopper/coll/CompressedArrayTest.java
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.coll;
-
-import com.graphhopper.util.shapes.GHPoint;
-import org.junit.Test;
-
-import java.util.Random;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertNull;
-
-/**
- * @author Peter Karich
- */
-public class CompressedArrayTest {
-    @Test
-    public void testCompress() throws Exception {
-        CompressedArray arr = new CompressedArray();
-        arr.write(10, 1);
-        arr.write(11, 2);
-        arr.write(12, 3);
-        arr.flush();
-
-        GHPoint coord = arr.get(0);
-        assertEquals(10, coord.lat, 1e-6);
-        assertEquals(1, coord.lon, 1e-6);
-
-        coord = arr.get(1);
-        assertEquals(11, coord.lat, 1e-6);
-        assertEquals(2, coord.lon, 1e-6);
-
-        coord = arr.get(2);
-        assertEquals(12, coord.lat, 1e-6);
-        assertEquals(3, coord.lon, 1e-6);
-
-        assertNull(arr.get(3));
-        // assertEquals(42, arr.calcMemInMB() * Helper.MB, 1e-3);
-    }
-
-    @Test
-    public void testCompress2() throws Exception {
-        CompressedArray arr = new CompressedArray();
-        Random rand = new Random(0);
-        for (int i = 0; i < 10000; i++) {
-            arr.write(i / 1000.0, rand.nextDouble() * 90);
-        }
-
-        arr.flush();
-        GHPoint coord = arr.get(0);
-        assertEquals(0, coord.lat, 1e-6);
-        assertEquals(65.787100, coord.lon, 1e-6);
-
-        coord = arr.get(999);
-        assertEquals(0.999, coord.lat, 1e-6);
-
-        coord = arr.get(9998);
-        assertEquals(9.998, coord.lat, 1e-6);
-
-        coord = arr.get(9999);
-        assertEquals(9.999, coord.lat, 1e-6);
-
-        assertNull(arr.get(10000));
-
-        // assertEquals(43, arr.calcMemInMB() * Helper.MB, 1e-3);
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/geohash/LinearKeyAlgoTest.java b/core/src/test/java/com/graphhopper/geohash/LinearKeyAlgoTest.java
deleted file mode 100644
index e874a82b3..000000000
--- a/core/src/test/java/com/graphhopper/geohash/LinearKeyAlgoTest.java
+++ /dev/null
@@ -1,86 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.geohash;
-
-import com.graphhopper.util.shapes.BBox;
-import com.graphhopper.util.shapes.GHPoint;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-public class LinearKeyAlgoTest {
-    @Test
-    public void testEncode() {
-        KeyAlgo algo = new LinearKeyAlgo(3, 4).setBounds(-1, 9, -2, 20);
-        assertEquals(2L, algo.encode(-1, 5));
-        assertEquals(11L, algo.encode(14, 7));
-
-        // on grid => lower number
-        assertEquals(5L, algo.encode(8, 4));
-
-        // out of bounds
-        assertEquals(1L, algo.encode(-4, 3));
-        assertEquals(3L, algo.encode(2, 22));
-        assertEquals(0L, algo.encode(-4, -4));
-
-        assertEquals(11L, algo.encode(22, 22));
-    }
-
-    @Test
-    public void testDecode() {
-        KeyAlgo algo = new LinearKeyAlgo(3, 4).setBounds(-1, 9, -2, 20);
-        GHPoint latLon = new GHPoint();
-
-        // decode that we get the center of the grid cell!
-        algo.decode(5, latLon);
-        assertEquals(9, latLon.lat, 1e-7);
-        assertEquals(2.75, latLon.lon, 1e-7);
-
-        algo.decode(2, latLon);
-        assertEquals(1.66666666, latLon.lat, 1e-7);
-        assertEquals(5.25, latLon.lon, 1e-7);
-
-        algo.decode(11, latLon);
-        assertEquals(16.3333333, latLon.lat, 1e-7);
-        assertEquals(7.75, latLon.lon, 1e-7);
-
-        algo.decode(10, latLon);
-        assertEquals(16.3333333, latLon.lat, 1e-7);
-        assertEquals(5.25, latLon.lon, 1e-7);
-    }
-
-    /*
-    * Test if different constructors yield same results
-     */
-    @Test
-    public void testInstantiation() {
-        double minLon = 0;
-        double minLat = 2;
-        double maxLat = 6;
-        double maxLon = 5;
-
-        BBox bounds = new BBox(minLon, maxLon, minLat, maxLat);
-        LinearKeyAlgo algo1 = new LinearKeyAlgo(4, 4).setBounds(bounds);
-        LinearKeyAlgo algo2 = new LinearKeyAlgo(4, 4).setBounds(minLon, maxLon, minLat, maxLat);
-        assertEquals(algo1.getLonDelta(), algo2.getLonDelta(), 1e-7);
-        assertEquals(algo1.getLatDelta(), algo2.getLatDelta(), 1e-7);
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/geohash/SpatialKeyAlgoTest.java b/core/src/test/java/com/graphhopper/geohash/SpatialKeyAlgoTest.java
index 63429358f..8e041b517 100644
--- a/core/src/test/java/com/graphhopper/geohash/SpatialKeyAlgoTest.java
+++ b/core/src/test/java/com/graphhopper/geohash/SpatialKeyAlgoTest.java
@@ -18,12 +18,10 @@
 package com.graphhopper.geohash;
 
 import com.graphhopper.util.BitUtil;
-import com.graphhopper.util.DistanceCalcEarth;
-import com.graphhopper.util.shapes.GHPoint;
+import com.graphhopper.util.shapes.BBox;
 import org.junit.Test;
 
 import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
 
 /**
  * @author Peter Karich
@@ -31,209 +29,62 @@ import static org.junit.Assert.assertTrue;
 public class SpatialKeyAlgoTest {
     @Test
     public void testEncode() {
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(32);
-        long val = algo.encode(-24.235345f, 47.234234f);
+        SpatialKeyAlgo algo = new SpatialKeyAlgo(32, new BBox(-180, 180, -90, 90));
+        long val = algo.encodeLatLon(-24.235345f, 47.234234f);
         assertEquals("01100110101000111100000110010100", BitUtil.BIG.toLastBitString(val, 32));
     }
 
     @Test
-    public void testEncode3BytesPrecision() {
-        // 3 bytes => c / 1^12 = ~10km
-        int bits = 3 * 8;
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(bits);
-        float lat = 24.235345f;
-        float lon = 47.234234f;
-        long val = algo.encode(lat, lon);
-        assertEquals("00000000" + "110011000000100101101011", BitUtil.BIG.toLastBitString(val, 32));
-
-        GHPoint fl = new GHPoint();
-        algo.decode(val, fl);
-        // normally 10km are expected here we have only 100meters ... (?)
-        assertEquals(lat, fl.lat, .1);
-        assertEquals(lon, fl.lon, .1);
-
-        double expectedDist = ((float) DistanceCalcEarth.C / (1 << bits / 2));
-        double d = new DistanceCalcEarth().calcDist(lat, lon, fl.lat, fl.lon);
-        assertTrue("Returned point shouldn't be more far away than " + expectedDist + " -> It was " + d, d < expectedDist);
-    }
-
-    @Test
-    public void testEncode4BytesPrecision() {
-        int bits = 4 * 8;
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(bits);
-        float lat = 24.235345f;
-        float lon = 47.234234f;
-        long val = algo.encode(lat, lon);
-        assertEquals("11001100000010010110101100111110", BitUtil.BIG.toLastBitString(val, bits));
-
-        GHPoint fl = new GHPoint();
-        algo.decode(val, fl);
-        assertEquals(lat, fl.lat, 1e-2);
-        assertEquals(lon, fl.lon, 1e-2);
-
-        double expectedDist = ((float) DistanceCalcEarth.C / (1 << bits / 2));
-        double d = new DistanceCalcEarth().calcDist(lat, lon, fl.lat, fl.lon);
-        assertTrue("Returned point shouldn't be more far away than " + expectedDist + " -> It was " + d, d < expectedDist);
-    }
-
-    @Test
-    public void testEncode6BytesPrecision() {
-        int bits = 6 * 8;
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(bits);
-        float lat = 24.235345f;
-        float lon = 47.234234f;
-        long val = algo.encode(lat, lon);
-        assertEquals("11001100000010010110101100111110" + "11100111" + "01000110", BitUtil.BIG.toLastBitString(val, bits));
-
-        GHPoint fl = new GHPoint();
-        algo.decode(val, fl);
-        assertEquals(lat, fl.lat, 1e-4);
-        assertEquals(lon, fl.lon, 1e-4);
-
-        double expectedDist = ((float) DistanceCalcEarth.C / (1 << bits / 2));
-        double d = new DistanceCalcEarth().calcDist(lat, lon, fl.lat, fl.lon);
-        assertTrue("Returned point shouldn't be more far away than " + expectedDist + " -> It was " + d, d < expectedDist);
+    public void testEdgeCases() {
+        double minLon = -1, maxLon = 1.6;
+        double minLat = -1, maxLat = 0.5;
+        int parts = 4;
+        int bits = (int) (Math.log(parts * parts) / Math.log(2));
+        SpatialKeyAlgo spatialKeyAlgo = new SpatialKeyAlgo(bits, new BBox(minLon, maxLon, minLat, maxLat));
+        // lat border 0.125
+        assertEquals(11, spatialKeyAlgo.encodeLatLon(0.125, -0.2));
+        assertEquals(9, spatialKeyAlgo.encodeLatLon(0.124, -0.2));
+        // lon border -0.35
+        assertEquals(11, spatialKeyAlgo.encodeLatLon(0.2, -0.35));
+        assertEquals(10, spatialKeyAlgo.encodeLatLon(0.2, -0.351));
     }
 
     @Test
-    public void testBijectionBug2() {
-        for (long i = 4; i <= 64; i += 4) {
-            SpatialKeyAlgo algo = new SpatialKeyAlgo((int) i);
-            long keyX = algo.encode(1, 1);
-
-            GHPoint coord = new GHPoint();
-            algo.decode(keyX, coord);
-            long keyY = algo.encode(coord.lat, coord.lon);
-
-            GHPoint coord2 = new GHPoint();
-            algo.decode(keyY, coord2);
-
-            double dist = new DistanceCalcEarth().calcDist(coord.lat, coord.lon, coord2.lat, coord2.lon);
-            assertEquals(0, dist, 1e-5);
-//            System.out.println("\n\n##" + i + "\nkeyX:" + BitUtil.BIG.toBitString(keyX));
-//            System.out.println("keyY:" + BitUtil.BIG.toBitString(keyY));
-//            System.out.println("distanceX:" + dist + " precision:" + precision + " difference:" + (dist - precision) + " factor:" + dist / precision);
+    public void testFourBits() {
+        // This is from the picture in the comments of SpatialKeyAlgo
+        SpatialKeyAlgo spatialKeyAlgo = new SpatialKeyAlgo(4, new BBox(-180, 180, -90, 90));
+        assertEquals(0b0000, spatialKeyAlgo.encode(0, 0));
+        assertEquals(0b0001, spatialKeyAlgo.encode(1, 0));
+        assertEquals(0b0100, spatialKeyAlgo.encode(2, 0));
+        assertEquals(0b0101, spatialKeyAlgo.encode(3, 0));
+        assertEquals(0b0010, spatialKeyAlgo.encode(0, 1));
+        assertEquals(0b1000, spatialKeyAlgo.encode(0, 2));
+        assertEquals(0b1010, spatialKeyAlgo.encode(0, 3));
+        assertEquals(0b1100, spatialKeyAlgo.encode(2, 2));
+
+        for (int x=0; x<4; x++) {
+            for (int y=0; y<4; y++) {
+                int[] xy = spatialKeyAlgo.decode(spatialKeyAlgo.encode(x, y));
+                assertEquals(x, xy[0]);
+                assertEquals(y, xy[1]);
+            }
         }
-    }
-
-    @Test
-    public void testBijection() {
-        // fix bijection precision problem!
-        //
-        // the latitude encoding "10" would result in 1.0 but a rounding error could lead to e.g. 0.99
-        // this new float decodes to an entire different latitude "01" which again could result in 
-        // another different value like 0.49 and so on. 
-        // To avoid this unstable rounding we need to add the half of the next interval in the last 
-        // iteration in decode: else { ... break; }
-        // Now the latitude encoding "10" results in 1.25 and a minor rounding error such as 1.24 
-        // results in the same encoding "10"!
-        //
-        // 0   .5   1.0   1.5  2.0
-        // |--- ^ ---|--- ^ ---|        
-        testBijection(6 * 8);
-        testBijection(7 * 8);
-        testBijection(8 * 8);
-    }
-
-    public void testBijection(int bits) {
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(bits);
-        GHPoint coord11 = new GHPoint();
-        long key = algo.encode(1, 1);
-        algo.decode(key, coord11);
-        long resKey = algo.encode(coord11.lat, coord11.lon);
-        GHPoint coord2 = new GHPoint();
-        algo.decode(resKey, coord2);
-        assertEquals(key, resKey);
-
-        GHPoint coord = new GHPoint(50.022846, 9.2123575);
-        key = algo.encode(coord);
-        algo.decode(key, coord2);
-        assertEquals(key, algo.encode(coord2));
-        double dist = new DistanceCalcEarth().calcDist(coord.lat, coord.lon, coord2.lat, coord2.lon);
-        // and ensure small distance
-        assertTrue(dist + "", dist < 5);
-
-        long queriedKey = 246557819640268L;
-        long storedKey = 246557819640269L;
-        algo.decode(queriedKey, coord);
-        algo.decode(storedKey, coord2);
-
-        // 2. fix bijection precision problem
-        assertEquals(storedKey, algo.encode(coord2));
-        dist = new DistanceCalcEarth().calcDist(coord.lat, coord.lon, coord2.lat, coord2.lon);
-        // and ensure small distance
-        assertTrue(dist + "", dist < 5);
-
-        coord = new GHPoint(50.0606072, 9.6277542);
-        key = algo.encode(coord);
-        algo.decode(key, coord2);
-        assertEquals(key, algo.encode(coord2));
-        dist = new DistanceCalcEarth().calcDist(coord.lat, coord.lon, coord2.lat, coord2.lon);
-        // and ensure small distance
-        assertTrue(dist + "", dist < 5);
-
-        coord = new GHPoint(0.01, 0.01);
-        key = algo.encode(coord);
-        algo.decode(key, coord2);
-        assertEquals(key, algo.encode(coord2));
-        dist = new DistanceCalcEarth().calcDist(coord.lat, coord.lon, coord2.lat, coord2.lon);
-        // and ensure small distance
-        assertTrue(dist + "", dist < 5);
-    }
-
-    @Test
-    public void testNoFurtherIterationIfBitsIs1() {
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(4).setBounds(0, 5, 0, 5);
-        // 1001
-        GHPoint coord = new GHPoint();
-        algo.decode(9, coord);
-        assertEquals(3.125, coord.lat, 1e-4);
-        assertEquals(1.875, coord.lon, 1e-4);
-    }
-
-    @Test
-    public void testOddBits() {
-        GHPoint coord = new GHPoint();
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(8);
-        long key = algo.encode(5, 30);
-        assertEquals("11000001", BitUtil.BIG.toLastBitString(key, 8));
-        algo.decode(key, coord);
-        assertEquals(5.63, coord.lat, 1e-2);
-        assertEquals(33.75, coord.lon, 1e-2);
 
-        algo = new SpatialKeyAlgo(7);
-        key = algo.encode(11.11, 40.66);
-        assertEquals("01100000", BitUtil.BIG.toLastBitString(key, 8));
-        assertEquals(5.63, coord.lat, 1e-2);
-        assertEquals(33.75, coord.lon, 1e-2);
+        assertEquals(spatialKeyAlgo.encode(2, 0), spatialKeyAlgo.right(spatialKeyAlgo.right(spatialKeyAlgo.encode(0, 0))));
     }
 
     @Test
-    public void testDifferentInitialBounds() {
-        SpatialKeyAlgo algo = new SpatialKeyAlgo(8).setBounds(0, 5, 0, 5);
-        assertEquals(1, algo.encode(0, 0.5));
-        assertEquals(5, algo.encode(0, 1));
-
-        GHPoint coord = new GHPoint();
-        algo.decode(5, coord);
-        assertEquals(5, algo.encode(coord));
-
-        algo.decode(1, coord);
-        assertEquals(1, algo.encode(coord));
+    public void testTwentyBits() {
+        SpatialKeyAlgo spatialKeyAlgo = new SpatialKeyAlgo(20, new BBox(-180, 180, -90, 90));
+        assertEquals(0b11111111111111111111L, spatialKeyAlgo.encode(1023, 1023));
+
+        for (int x=0; x<1024; x++) {
+            for (int y=0; y<1024; y++) {
+                int[] xy = spatialKeyAlgo.decode(spatialKeyAlgo.encode(x, y));
+                assertEquals(x, xy[0]);
+                assertEquals(y, xy[1]);
+            }
+        }
     }
 
-    @Test
-    public void testEdgeCases() {
-        double minLon = -1, maxLon = 1.6;
-        double minLat = -1, maxLat = 0.5;
-        int parts = 4;
-        int bits = (int) (Math.log(parts * parts) / Math.log(2));
-        final KeyAlgo keyAlgo = new SpatialKeyAlgo(bits).setBounds(minLon, maxLon, minLat, maxLat);
-        // lat border 0.125
-        assertEquals(11, keyAlgo.encode(0.125, -0.2));
-        assertEquals(9, keyAlgo.encode(0.124, -0.2));
-        // lon border -0.35
-        assertEquals(11, keyAlgo.encode(0.2, -0.35));
-        assertEquals(10, keyAlgo.encode(0.2, -0.351));
-    }
 }
diff --git a/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java b/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java
index 3dadb7fcc..0624b7dfb 100644
--- a/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java
+++ b/core/src/test/java/com/graphhopper/routing/DirectedBidirectionalDijkstraTest.java
@@ -13,7 +13,6 @@ import com.graphhopper.routing.weighting.DefaultTurnCostProvider;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.*;
-import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.EdgeIteratorState;
@@ -486,7 +485,7 @@ public class DirectedBidirectionalDijkstraTest {
         na.setNode(4, 0, 1);
         na.setNode(5, 0, 0);
 
-        LocationIndex locationIndex = new LocationIndexTree(graph, dir);
+        LocationIndexTree locationIndex = new LocationIndexTree(graph, dir);
         locationIndex.prepareIndex();
         Snap snap = locationIndex.findClosest(1.1, 0.5, EdgeFilter.ALL_EDGES);
         QueryGraph queryGraph = QueryGraph.create(graph, snap);
diff --git a/core/src/test/java/com/graphhopper/routing/DirectionResolverOnQueryGraphTest.java b/core/src/test/java/com/graphhopper/routing/DirectionResolverOnQueryGraphTest.java
index a06a1dd24..6d80069ba 100644
--- a/core/src/test/java/com/graphhopper/routing/DirectionResolverOnQueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/DirectionResolverOnQueryGraphTest.java
@@ -24,7 +24,6 @@ import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.GraphBuilder;
 import com.graphhopper.storage.NodeAccess;
 import com.graphhopper.storage.RAMDirectory;
-import com.graphhopper.storage.index.LocationIndex;
 import com.graphhopper.storage.index.LocationIndexTree;
 import com.graphhopper.storage.index.Snap;
 import com.graphhopper.util.EdgeExplorer;
@@ -54,7 +53,7 @@ public class DirectionResolverOnQueryGraphTest {
     private NodeAccess na;
     private FlagEncoder encoder;
     private Graph graph;
-    private LocationIndex locationIndex;
+    private LocationIndexTree locationIndex;
 
     @Before
     public void setup() {
diff --git a/core/src/test/java/com/graphhopper/routing/RoundTripRoutingTest.java b/core/src/test/java/com/graphhopper/routing/RoundTripRoutingTest.java
index aad7c8b2c..a10e69574 100644
--- a/core/src/test/java/com/graphhopper/routing/RoundTripRoutingTest.java
+++ b/core/src/test/java/com/graphhopper/routing/RoundTripRoutingTest.java
@@ -107,16 +107,16 @@ public class RoundTripRoutingTest {
                 qGraph, new RoutingAlgorithmFactorySimple(), new AlgorithmOptions(DIJKSTRA_BI, fastestWeighting, tMode));
         List<Path> paths = RoundTripRouting.calcPaths(Arrays.asList(snap5, snap4, snap5), pathCalculator).paths;
         assertEquals(2, paths.size());
-        assertEquals(IntArrayList.from(5, 6, 3, 4), paths.get(0).calcNodes());
-        assertEquals(IntArrayList.from(4, 8, 7, 6, 5), paths.get(1).calcNodes());
+        assertEquals(IntArrayList.from(5, 6, 3), paths.get(0).calcNodes());
+        assertEquals(IntArrayList.from(3, 2, 9, 1, 5), paths.get(1).calcNodes());
 
         qGraph = QueryGraph.create(g, Arrays.asList(snap4, snap6));
         pathCalculator = new FlexiblePathCalculator(
                 qGraph, new RoutingAlgorithmFactorySimple(), new AlgorithmOptions(DIJKSTRA_BI, fastestWeighting, tMode));
         paths = RoundTripRouting.calcPaths(Arrays.asList(snap6, snap4, snap6), pathCalculator).paths;
         assertEquals(2, paths.size());
-        assertEquals(IntArrayList.from(6, 3, 4), paths.get(0).calcNodes());
-        assertEquals(IntArrayList.from(4, 8, 7, 6), paths.get(1).calcNodes());
+        assertEquals(IntArrayList.from(6, 3), paths.get(0).calcNodes());
+        assertEquals(IntArrayList.from(3, 4, 8, 7, 6), paths.get(1).calcNodes());
     }
 
     private Graph createTestGraph() {
diff --git a/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java b/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
index 8a07cf1ef..6eb523a8f 100644
--- a/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
+++ b/core/src/test/java/com/graphhopper/routing/lm/PrepareLandmarksTest.java
@@ -99,7 +99,7 @@ public class PrepareLandmarksTest {
             }
         }
         Directory dir = new RAMDirectory();
-        LocationIndex index = new LocationIndexTree(graph, dir);
+        LocationIndexTree index = new LocationIndexTree(graph, dir);
         index.prepareIndex();
 
         int lm = 5, activeLM = 2;
diff --git a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
index 1c762c173..257924e13 100644
--- a/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
+++ b/core/src/test/java/com/graphhopper/routing/querygraph/QueryGraphTest.java
@@ -718,7 +718,7 @@ public class QueryGraphTest {
         GHUtility.setSpeed(60, true, true, encoder, g.edge(0, 1).setDistance(10)).
                 setWayGeometry(Helper.createPointList(0.1, 0.1, 0.2, 0.2));
 
-        LocationIndex locationIndex = new LocationIndexTree(g, new RAMDirectory());
+        LocationIndexTree locationIndex = new LocationIndexTree(g, new RAMDirectory());
         locationIndex.prepareIndex();
         Snap snap = locationIndex.findClosest(0.15, 0.15, DefaultEdgeFilter.allEdges(encoder));
         assertTrue(snap.isValid());
@@ -760,7 +760,7 @@ public class QueryGraphTest {
         GHUtility.setSpeed(60, true, true, encoder, g.edge(0, 1).setDistance(10)).
                 setWayGeometry(Helper.createPointList(0.1, 0.1, 0.2, 0.2));
 
-        LocationIndex locationIndex = new LocationIndexTree(g, new RAMDirectory());
+        LocationIndexTree locationIndex = new LocationIndexTree(g, new RAMDirectory());
         locationIndex.prepareIndex();
         Snap snap = locationIndex.findClosest(0.2, 0.21, DefaultEdgeFilter.allEdges(encoder));
         assertTrue(snap.isValid());
diff --git a/core/src/test/java/com/graphhopper/storage/index/AbstractLocationIndexTester.java b/core/src/test/java/com/graphhopper/storage/index/AbstractLocationIndexTester.java
deleted file mode 100644
index 1118fd926..000000000
--- a/core/src/test/java/com/graphhopper/storage/index/AbstractLocationIndexTester.java
+++ /dev/null
@@ -1,355 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.ev.BooleanEncodedValue;
-import com.graphhopper.routing.util.*;
-import com.graphhopper.storage.*;
-import com.graphhopper.util.*;
-import org.junit.After;
-import org.junit.Before;
-import org.junit.Test;
-
-import java.io.Closeable;
-import java.io.File;
-import java.util.Arrays;
-import java.util.List;
-import java.util.Random;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertTrue;
-
-/**
- * @author Peter Karich
- */
-public abstract class AbstractLocationIndexTester {
-    String location = "./target/tmp/";
-    LocationIndex idx;
-
-    public abstract LocationIndex createIndex(Graph g, int resolution);
-
-    GraphHopperStorage createGHStorage(EncodingManager encodingManager) {
-        return AbstractLocationIndexTester.this.createGHStorage(new RAMDirectory(), encodingManager, false);
-    }
-
-    GraphHopperStorage createGHStorage(Directory dir, EncodingManager encodingManager, boolean is3D) {
-        return new GraphHopperStorage(dir, encodingManager, is3D).create(100);
-    }
-
-    protected int findID(LocationIndex index, double lat, double lon) {
-        return index.findClosest(lat, lon, EdgeFilter.ALL_EDGES).getClosestNode();
-    }
-
-    public boolean hasEdgeSupport() {
-        return false;
-    }
-
-    @Before
-    public void setUp() {
-        Helper.removeDir(new File(location));
-    }
-
-    @After
-    public void tearDown() {
-        if (idx != null)
-            idx.close();
-        Helper.removeDir(new File(location));
-    }
-
-    @Test
-    public void testSimpleGraph() {
-        EncodingManager em = EncodingManager.create("car");
-        Graph g = AbstractLocationIndexTester.this.createGHStorage(em);
-        initSimpleGraph(g, em);
-
-        idx = createIndex(g, -1);
-        assertEquals(4, findID(idx, 5, 2));
-        assertEquals(3, findID(idx, 1.5, 2));
-        assertEquals(0, findID(idx, -1, -1));
-
-        if (hasEdgeSupport()) // now get the edge 1-4 and not node 6
-        {
-            assertEquals(4, findID(idx, 4, 0));
-        } else {
-            assertEquals(6, findID(idx, 4, 0));
-        }
-        Helper.close((Closeable) g);
-    }
-
-    public static void initSimpleGraph(Graph g, EncodingManager em) {
-        //  6 |       4
-        //  5 |           
-        //    |     6
-        //  4 |              5
-        //  3 |
-        //  2 |    1  
-        //  1 |          3
-        //  0 |    2      
-        // -1 | 0   
-        // ---|-------------------
-        //    |-2 -1 0 1 2 3 4
-        //
-        NodeAccess na = g.getNodeAccess();
-        na.setNode(0, -1, -2);
-        na.setNode(1, 2, -1);
-        na.setNode(2, 0, 1);
-        na.setNode(3, 1, 2);
-        na.setNode(4, 6, 1);
-        na.setNode(5, 4, 4);
-        na.setNode(6, 4.5, -0.5);
-        List<EdgeIteratorState> list = Arrays.asList(g.edge(0, 1).setDistance(3.5),
-                g.edge(0, 2).setDistance(2.5),
-                g.edge(2, 3).setDistance(1),
-                g.edge(3, 4).setDistance(3.2),
-                g.edge(1, 4).setDistance(2.4),
-                g.edge(3, 5).setDistance(1.5),
-                // make sure 6 is connected
-                g.edge(6, 4).setDistance(1.2));
-        for (FlagEncoder encoder : em.fetchEdgeEncoders()) {
-            double speed = encoder.getMaxSpeed() / 2;
-            GHUtility.setSpeed(speed, speed, encoder, list);
-        }
-    }
-
-    @Test
-    public void testSimpleGraph2() {
-        EncodingManager em = EncodingManager.create("car");
-        Graph g = AbstractLocationIndexTester.this.createGHStorage(em);
-        initSimpleGraph(g, em);
-
-        idx = createIndex(g, -1);
-        assertEquals(4, findID(idx, 5, 2));
-        assertEquals(3, findID(idx, 1.5, 2));
-        assertEquals(0, findID(idx, -1, -1));
-        assertEquals(6, findID(idx, 4.5, -0.5));
-        if (hasEdgeSupport()) {
-            assertEquals(4, findID(idx, 4, 1));
-            assertEquals(4, findID(idx, 4, 0));
-        } else {
-            assertEquals(6, findID(idx, 4, 1));
-            assertEquals(6, findID(idx, 4, 0));
-        }
-        assertEquals(6, findID(idx, 4, -2));
-        assertEquals(5, findID(idx, 3, 3));
-        Helper.close((Closeable) g);
-    }
-
-    @Test
-    public void testGrid() {
-        Graph g = createSampleGraph(EncodingManager.create("car"));
-        int locs = g.getNodes();
-
-        idx = createIndex(g, -1);
-        // if we would use less array entries then some points gets the same key so avoid that for this test
-        // e.g. for 16 we get "expected 6 but was 9" i.e 6 was overwritten by node j9 which is a bit closer to the grid center
-        // go through every point of the graph if all points are reachable
-        NodeAccess na = g.getNodeAccess();
-        for (int i = 0; i < locs; i++) {
-            double lat = na.getLatitude(i);
-            double lon = na.getLongitude(i);
-            assertEquals("nodeId:" + i + " " + (float) lat + "," + (float) lon, i, findID(idx, lat, lon));
-        }
-
-        // hit random lat,lon and compare result to full index
-        Random rand = new Random(12);
-        LocationIndex fullIndex;
-        if (hasEdgeSupport())
-            fullIndex = new Location2IDFullWithEdgesIndex(g);
-        else
-            fullIndex = new Location2IDFullIndex(g);
-
-        DistanceCalc dist = new DistanceCalcEarth();
-        for (int i = 0; i < 100; i++) {
-            double lat = rand.nextDouble() * 5;
-            double lon = rand.nextDouble() * 5;
-            int fullId = findID(fullIndex, lat, lon);
-            double fullLat = na.getLatitude(fullId);
-            double fullLon = na.getLongitude(fullId);
-            float fullDist = (float) dist.calcDist(lat, lon, fullLat, fullLon);
-            int newId = findID(idx, lat, lon);
-            double newLat = na.getLatitude(newId);
-            double newLon = na.getLongitude(newId);
-            float newDist = (float) dist.calcDist(lat, lon, newLat, newLon);
-
-            if (testGridIgnore(i)) {
-                continue;
-            }
-
-            assertTrue(i + " orig:" + (float) lat + "," + (float) lon
-                            + " full:" + fullLat + "," + fullLon + " fullDist:" + fullDist
-                            + " found:" + newLat + "," + newLon + " foundDist:" + newDist,
-                    Math.abs(fullDist - newDist) < 50000);
-        }
-        fullIndex.close();
-        Helper.close((Closeable) g);
-    }
-
-    // our simple index has only one node per tile => problems if multiple subnetworks
-    boolean testGridIgnore(int i) {
-        return false;
-    }
-
-    @Test
-    public void testSinglePoints120() {
-        Graph g = createSampleGraph(EncodingManager.create("car"));
-        idx = createIndex(g, -1);
-
-        assertEquals(1, findID(idx, 1.637, 2.23));
-        assertEquals(10, findID(idx, 3.649, 1.375));
-        assertEquals(9, findID(idx, 3.3, 2.2));
-        assertEquals(6, findID(idx, 3.0, 1.5));
-
-        assertEquals(10, findID(idx, 3.8, 0));
-        assertEquals(10, findID(idx, 3.8466, 0.021));
-        Helper.close((Closeable) g);
-    }
-
-    @Test
-    public void testSinglePoints32() {
-        Graph g = createSampleGraph(EncodingManager.create("car"));
-        idx = createIndex(g, -1);
-
-        // 10 or 6
-        assertEquals(10, findID(idx, 3.649, 1.375));
-        assertEquals(10, findID(idx, 3.8465748, 0.021762699));
-        if (hasEdgeSupport()) {
-            assertEquals(4, findID(idx, 2.485, 1.373));
-        } else {
-            assertEquals(6, findID(idx, 2.485, 1.373));
-        }
-        assertEquals(0, findID(idx, 0.64628404, 0.53006625));
-        Helper.close((Closeable) g);
-    }
-
-    @Test
-    public void testNoErrorOnEdgeCase_lastIndex() {
-        final EncodingManager encodingManager = EncodingManager.create("car");
-        int locs = 10000;
-        Graph g = AbstractLocationIndexTester.this.createGHStorage(new MMapDirectory(location), encodingManager, false);
-        NodeAccess na = g.getNodeAccess();
-        Random rand = new Random(12);
-        for (int i = 0; i < locs; i++) {
-            na.setNode(i, (float) rand.nextDouble() * 10 + 10, (float) rand.nextDouble() * 10 + 10);
-        }
-        idx = createIndex(g, 200);
-        Helper.close((Closeable) g);
-    }
-
-    public Graph createSampleGraph(EncodingManager encodingManager) {
-        Graph graph = AbstractLocationIndexTester.this.createGHStorage(encodingManager);
-        // length does not matter here but lat,lon and outgoing edges do!
-
-//        
-//   lat             /--------\
-//    5   o-        p--------\ q
-//          \  /-----\-----n | |
-//    4       k    /--l--    m/                 
-//           / \  j      \   |              
-//    3     |   g  \  h---i  /             
-//          |       \    /  /             
-//    2     e---------f--  /
-//                   /  \-d
-//    1        /--b--      \               
-//            |    \--------c
-//    0       a                  
-//        
-//   lon: 0   1   2   3   4   5
-        int a0 = 0;
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(0, 0, 1.0001f);
-        int b1 = 1;
-        na.setNode(1, 1, 2);
-        int c2 = 2;
-        na.setNode(2, 0.5f, 4.5f);
-        int d3 = 3;
-        na.setNode(3, 1.5f, 3.8f);
-        int e4 = 4;
-        na.setNode(4, 2.01f, 0.5f);
-        int f5 = 5;
-        na.setNode(5, 2, 3);
-        int g6 = 6;
-        na.setNode(6, 3, 1.5f);
-        int h7 = 7;
-        na.setNode(7, 2.99f, 3.01f);
-        int i8 = 8;
-        na.setNode(8, 3, 4);
-        int j9 = 9;
-        na.setNode(9, 3.3f, 2.2f);
-        int k10 = 10;
-        na.setNode(10, 4, 1);
-        int l11 = 11;
-        na.setNode(11, 4.1f, 3);
-        int m12 = 12;
-        na.setNode(12, 4, 4.5f);
-        int n13 = 13;
-        na.setNode(13, 4.5f, 4.1f);
-        int o14 = 14;
-        na.setNode(14, 5, 0);
-        int p15 = 15;
-        na.setNode(15, 4.9f, 2.5f);
-        int q16 = 16;
-        na.setNode(16, 5, 5);
-        // => 17 locations
-
-        FlagEncoder encoder = encodingManager.getEncoder("car");
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(a0, b1).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(c2, b1).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(c2, d3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, b1).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(e4, f5).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(m12, d3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(e4, k10).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, d3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, i8).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, j9).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, g6).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(j9, l11).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(i8, l11).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(i8, h7).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, n13).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, o14).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(l11, p15).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(m12, p15).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(q16, p15).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(q16, m12).setDistance(1));
-        return graph;
-    }
-
-    @Test
-    public void testDifferentVehicles() {
-        final EncodingManager encodingManager = EncodingManager.create("car,foot");
-        Graph g = AbstractLocationIndexTester.this.createGHStorage(encodingManager);
-        initSimpleGraph(g, encodingManager);
-        idx = createIndex(g, -1);
-        assertEquals(1, findID(idx, 1, -1));
-
-        // now make all edges from node 1 accessible for CAR only
-        EdgeIterator iter = g.createEdgeExplorer().setBaseNode(1);
-        FlagEncoder encoder = encodingManager.getEncoder("foot");
-        BooleanEncodedValue accessEnc = encoder.getAccessEnc();
-        while (iter.next()) {
-            iter.set(accessEnc, false, false);
-        }
-        idx.close();
-
-        idx = createIndex(g, -1);
-        FootFlagEncoder footEncoder = (FootFlagEncoder) encodingManager.getEncoder("foot");
-        assertEquals(2, idx.findClosest(1, -1, DefaultEdgeFilter.allEdges(footEncoder)).getClosestNode());
-        Helper.close((Closeable) g);
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/storage/index/BresenhamLineTest.java b/core/src/test/java/com/graphhopper/storage/index/BresenhamLineTest.java
deleted file mode 100644
index 723ab0511..000000000
--- a/core/src/test/java/com/graphhopper/storage/index/BresenhamLineTest.java
+++ /dev/null
@@ -1,138 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.geohash.KeyAlgo;
-import com.graphhopper.geohash.SpatialKeyAlgo;
-import com.graphhopper.util.Helper;
-import com.graphhopper.util.PointList;
-import org.junit.Before;
-import org.junit.Test;
-
-import java.util.ArrayList;
-import java.util.Arrays;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-public class BresenhamLineTest {
-    final PointList points = new PointList(10, false);
-    PointEmitter emitter = new PointEmitter() {
-        @Override
-        public void set(double lat, double lon) {
-            points.add(lat, lon);
-        }
-    };
-
-    @Before
-    public void setUp() {
-        points.clear();
-    }
-
-    @Test
-    public void testBresenhamLineLeftDown() {
-        BresenhamLine.calcPoints(5, 2, 0, 0, emitter);
-        // 5,2, 4,2, 3,2, 3,1, 2,1, 1,1, 0,0
-        assertEquals(Helper.createPointList(5, 2, 4, 2, 3, 1, 2, 1, 1, 0, 0, 0), points);
-    }
-
-    @Test
-    public void testBresenhamLineRightDown() {
-        BresenhamLine.calcPoints(3, 1, 0, 3, emitter);
-        // 3,1, 2,1, 1,1, 1,2, 0,2, 0,3
-        assertEquals(Helper.createPointList(3, 1, 2, 2, 1, 2, 0, 3), points);
-    }
-
-    @Test
-    public void testBresenhamLineLeftUp() {
-        BresenhamLine.calcPoints(2, 2, 3, 0, emitter);
-        // 2,2, 2,1, 2,0, 3,0
-
-        assertEquals(Helper.createPointList(2, 2, 2, 1, 3, 0), points);
-    }
-
-    @Test
-    public void testBresenhamLineRightUp() {
-        BresenhamLine.calcPoints(0, 0, 2, 3, emitter);
-        // 0,0, 0,1, 1,1, 1,2, 2,2, 2,3
-        assertEquals(Helper.createPointList(0, 0, 1, 1, 1, 2, 2, 3), points);
-    }
-
-    @Test
-    public void testBresenhamBug() {
-        BresenhamLine.calcPoints(0.5, -0.5, -0.6, 1.6, emitter, -1, -1, 0.75, 1.3);
-        assertEquals(Helper.createPointList(0.575, -0.87, -0.175, 0.43, -0.925, 1.73), points);
-    }
-
-    @Test
-    public void testBresenhamHorizontal() {
-        BresenhamLine.calcPoints(.5, -.5, .5, 1, emitter, -1, -1, 0.6, 0.4);
-        assertEquals(Helper.createPointList(.26, -.56, .26, -0.16, .26, .24, .26, .64, .26, 1.04), points);
-    }
-
-    @Test
-    public void testBresenhamVertical() {
-        BresenhamLine.calcPoints(-.5, .5, 1, 0.5, emitter, 0, 0, 0.4, 0.6);
-        assertEquals(Helper.createPointList(-0.36, .06, 0.04, 0.06, 0.44, 0.06, 0.84, 0.06), points);
-    }
-
-    @Test
-    public void testRealBresenham() {
-        int parts = 4;
-        int bits = (int) (Math.log(parts * parts) / Math.log(2));
-        double minLon = -1, maxLon = 1.6;
-        double minLat = -1, maxLat = 0.5;
-        final KeyAlgo keyAlgo = new SpatialKeyAlgo(bits).setBounds(minLon, maxLon, minLat, maxLat);
-        double deltaLat = (maxLat - minLat) / parts;
-        double deltaLon = (maxLon - minLon) / parts;
-        final ArrayList<Long> keys = new ArrayList<>();
-        PointEmitter tmpEmitter = new PointEmitter() {
-            @Override
-            public void set(double lat, double lon) {
-                keys.add(keyAlgo.encode(lat, lon));
-            }
-        };
-        keys.clear();
-        BresenhamLine.calcPoints(.3, -.3, -0.2, 0.2, tmpEmitter, minLat, minLon,
-                deltaLat, deltaLon);
-        assertEquals(Arrays.asList(11L, 9L), keys);
-
-        keys.clear();
-        BresenhamLine.calcPoints(.3, -.1, -0.2, 0.4, tmpEmitter, minLat, minLon,
-                deltaLat, deltaLon);
-
-        // 11, 9, 12
-        assertEquals(Arrays.asList(11L, 12L), keys);
-
-        keys.clear();
-        BresenhamLine.calcPoints(.5, -.5, -0.1, 0.9, tmpEmitter, minLat, minLon,
-                deltaLat, deltaLon);
-        // precise: 10, 11, 14, 12
-        assertEquals(Arrays.asList(10L, 11L, 12L), keys);
-    }
-
-    @Test
-    public void testBresenhamToLeft() {
-        BresenhamLine.calcPoints(
-                47.57383, 9.61984,
-                47.57382, 9.61890, emitter, 47, 9, 0.00647, 0.00964);
-        assertEquals(points.toString(), 1, points.getSize());
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/storage/index/Location2IDFullIndexTest.java b/core/src/test/java/com/graphhopper/storage/index/Location2IDFullIndexTest.java
deleted file mode 100644
index 4506637f6..000000000
--- a/core/src/test/java/com/graphhopper/storage/index/Location2IDFullIndexTest.java
+++ /dev/null
@@ -1,47 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.storage.Graph;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-public class Location2IDFullIndexTest extends AbstractLocationIndexTester {
-    @Override
-    public LocationIndex createIndex(Graph g, int resolution) {
-        return new Location2IDFullIndex(g);
-    }
-
-    @Override
-    public void testGrid() {
-        // do not test against itself
-    }
-
-    @Test
-    public void testFullIndex() {
-        LocationIndex tmpIdx = new Location2IDFullIndex(createSampleGraph(EncodingManager.create("car")));
-        assertEquals(5, findID(tmpIdx, 2, 3));
-        assertEquals(10, findID(tmpIdx, 4, 1));
-        assertEquals(10, findID(tmpIdx, 3.6, 1.4));
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndexTest.java b/core/src/test/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndexTest.java
deleted file mode 100644
index 03ae5d3b8..000000000
--- a/core/src/test/java/com/graphhopper/storage/index/Location2IDFullWithEdgesIndexTest.java
+++ /dev/null
@@ -1,53 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.storage.Graph;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-public class Location2IDFullWithEdgesIndexTest extends AbstractLocationIndexTester {
-    @Override
-    public LocationIndex createIndex(Graph g, int resolution) {
-        return new Location2IDFullWithEdgesIndex(g);
-    }
-
-    @Override
-    public boolean hasEdgeSupport() {
-        return true;
-    }
-
-    @Override
-    public void testGrid() {
-        // do not test against itself
-    }
-
-    @Test
-    public void testFullIndex() {
-        LocationIndex tmpIdx = new Location2IDFullWithEdgesIndex(createSampleGraph(EncodingManager.create("car")));
-        assertEquals(5, findID(tmpIdx, 2, 3));
-        assertEquals(10, findID(tmpIdx, 4, 1));
-        // 6, 9 or 10
-        assertEquals(10, findID(tmpIdx, 3.6, 1.4));
-    }
-}
diff --git a/core/src/test/java/com/graphhopper/storage/index/Location2IDQuadtreeTest.java b/core/src/test/java/com/graphhopper/storage/index/Location2IDQuadtreeTest.java
deleted file mode 100644
index 336e00f91..000000000
--- a/core/src/test/java/com/graphhopper/storage/index/Location2IDQuadtreeTest.java
+++ /dev/null
@@ -1,66 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.storage.index;
-
-import com.graphhopper.routing.util.EncodingManager;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.MMapDirectory;
-import com.graphhopper.storage.RAMDirectory;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-public class Location2IDQuadtreeTest extends AbstractLocationIndexTester {
-    @Override
-    public LocationIndex createIndex(Graph g, int resolution) {
-        if (resolution < 0)
-            resolution = 120;
-        return new Location2IDQuadtree(g, new MMapDirectory(location + "loc2idIndex").create()).
-                setResolution(resolution).prepareIndex();
-    }
-
-    @Test
-    public void testNormedDist() {
-        Location2IDQuadtree index = new Location2IDQuadtree(createGHStorage(EncodingManager.create("car")), new RAMDirectory());
-        index.initAlgo(5, 6);
-        assertEquals(1, index.getNormedDist(0, 1), 1e-6);
-        assertEquals(2, index.getNormedDist(0, 7), 1e-6);
-        assertEquals(2, index.getNormedDist(7, 2), 1e-6);
-        assertEquals(1, index.getNormedDist(7, 1), 1e-6);
-        assertEquals(4, index.getNormedDist(13, 25), 1e-6);
-        assertEquals(8, index.getNormedDist(15, 25), 1e-6);
-    }
-
-    @Override
-    boolean testGridIgnore(int i) {
-        // conceptual limitation where we are stuck in a blind alley limited
-        // to the current tile
-        if (i == 6 || i == 36 || i == 90 || i == 96) {
-            return true;
-        }
-        return false;
-    }
-
-    @Override
-    public void testDifferentVehicles() {
-        // currently unsupported
-    }
-}
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 2007180ba..e8b6d2a96 100644
--- a/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java
+++ b/core/src/test/java/com/graphhopper/storage/index/LocationIndexTreeTest.java
@@ -17,48 +17,68 @@
  */
 package com.graphhopper.storage.index;
 
-import com.carrotsearch.hppc.IntArrayList;
-import com.graphhopper.coll.GHIntHashSet;
 import com.graphhopper.routing.ev.BooleanEncodedValue;
 import com.graphhopper.routing.util.*;
-import com.graphhopper.storage.Directory;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.NodeAccess;
-import com.graphhopper.storage.RAMDirectory;
+import com.graphhopper.storage.*;
 import com.graphhopper.util.*;
 import com.graphhopper.util.shapes.BBox;
 import com.graphhopper.util.shapes.GHPoint;
-import org.junit.Test;
+import org.junit.jupiter.api.Test;
 
+import java.io.Closeable;
 import java.util.*;
 
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
 
 /**
  * @author Peter Karich
  */
-public class LocationIndexTreeTest extends AbstractLocationIndexTester {
+public class LocationIndexTreeTest {
     protected final EncodingManager encodingManager = EncodingManager.create("car");
 
-    @Override
-    public LocationIndexTree createIndex(Graph g, int resolution) {
-        if (resolution < 0)
-            resolution = 500000;
-        return (LocationIndexTree) createIndexNoPrepare(g, resolution).prepareIndex();
+    public static void initSimpleGraph(Graph g, EncodingManager em) {
+        //  6 |       4
+        //  5 |
+        //    |     6
+        //  4 |              5
+        //  3 |
+        //  2 |    1
+        //  1 |          3
+        //  0 |    2
+        // -1 | 0
+        // ---|-------------------
+        //    |-2 -1 0 1 2 3 4
+        //
+        NodeAccess na = g.getNodeAccess();
+        na.setNode(0, -1, -2);
+        na.setNode(1, 2, -1);
+        na.setNode(2, 0, 1);
+        na.setNode(3, 1, 2);
+        na.setNode(4, 6, 1);
+        na.setNode(5, 4, 4);
+        na.setNode(6, 4.5, -0.5);
+        List<EdgeIteratorState> list = Arrays.asList(g.edge(0, 1),
+                g.edge(0, 2),
+                g.edge(2, 3),
+                g.edge(3, 4),
+                g.edge(1, 4),
+                g.edge(3, 5),
+                // make sure 6 is connected
+                g.edge(6, 4));
+        for (FlagEncoder encoder : em.fetchEdgeEncoders()) {
+            double speed = encoder.getMaxSpeed() / 2;
+            GHUtility.setSpeed(speed, speed, encoder, list);
+        }
     }
 
     private LocationIndexTree createIndexNoPrepare(Graph g, int resolution) {
-        Directory dir = new RAMDirectory(location);
+        Directory dir = new RAMDirectory();
         LocationIndexTree tmpIDX = new LocationIndexTree(g, dir);
         tmpIDX.setResolution(resolution);
         return tmpIDX;
     }
 
-    @Override
-    public boolean hasEdgeSupport() {
-        return true;
-    }
-
     //  0------\
     // /|       \
     // |1----3-\|
@@ -66,27 +86,27 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     // 2-------/
     Graph createTestGraph(EncodingManager em) {
         FlagEncoder encoder = em.getEncoder("car");
-        Graph graph = createGHStorage(new RAMDirectory(), em, false);
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), em, false).create(100);
         NodeAccess na = graph.getNodeAccess();
         na.setNode(0, 0.5, -0.5);
         na.setNode(1, -0.5, -0.5);
         na.setNode(2, -1, -1);
         na.setNode(3, -0.4, 0.9);
         na.setNode(4, -0.6, 1.6);
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 1).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 4).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 4).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(3, 4).setDistance(1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 4));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 4));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(3, 4));
         return graph;
     }
 
     @Test
     public void testSnappedPointAndGeometry() {
         Graph graph = createTestGraph(encodingManager);
-        LocationIndex index = createIndex(graph, -1);
+        LocationIndex index = (LocationIndexTree) createIndexNoPrepare(graph, 500000).prepareIndex();
         // query directly the tower node
         Snap res = index.findClosest(-0.4, 0.9, EdgeFilter.ALL_EDGES);
         assertTrue(res.isValid());
@@ -103,174 +123,51 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     }
 
     @Test
-    public void testBoundingBoxQuery1() {
+    public void testBoundingBoxQuery2() {
         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() {
+        LocationIndexTree index = (LocationIndexTree) createIndexNoPrepare(graph, 500).prepareIndex();
+        final HashSet<Integer> edges = new HashSet<>();
+        index.query(graph.getBounds(), new LocationIndex.Visitor() {
             @Override
-            public void onNode(int nodeId) {
-                set.add(nodeId);
+            public void onEdge(int edgeId) {
+                edges.add(edgeId);
             }
         });
-        assertEquals(17, set.size());
-        assertTrue(set.containsAll(Arrays.asList(2, 3, 4, 5, 6)));
-        assertFalse(set.containsAll(Arrays.asList(17, 18, 25, 30)));
+        // All edges (see testgraph2.jpg)
+        assertEquals(edges.size(), graph.getEdges());
     }
 
     @Test
-    public void testBoundingBoxQuery2() {
+    public void testBoundingBoxQuery1() {
         Graph graph = createTestGraph2();
-        LocationIndexTree index = createIndex(graph, 500);
-        final HashSet<Integer> nodes = new HashSet<>();
-        final HashSet<Integer> edges = new HashSet<>();
-        index.query(graph.getBounds(), new LocationIndex.EdgeVisitor(graph.createEdgeExplorer()) {
+        LocationIndexTree index = (LocationIndexTree) createIndexNoPrepare(graph, 500).prepareIndex();
+        final ArrayList edges = new ArrayList();
+        BBox bbox = new BBox(11.57314, 11.57614, 49.94553, 49.94853);
+        index.query(bbox, new LocationIndex.Visitor() {
             @Override
-            public void onEdge(EdgeIteratorState edge, int nodeA, int nodeB) {
-                edges.add(edge.getEdge());
-                nodes.add(nodeA);
-                nodes.add(nodeB);
+            public void onEdge(int edgeId) {
+                edges.add(edgeId);
             }
         });
-        // all nodes 0-34 with edges
-        assertEquals(35, nodes.size());
-        // that the number of edges is identical is only accidental
-        assertEquals(35, graph.getEdges());
-    }
-
-    @Test
-    public void testInMemIndex() {
-        Graph graph = createTestGraph(encodingManager);
-        LocationIndexTree index = createIndexNoPrepare(graph, 50000);
-        index.prepareAlgo();
-        LocationIndexTree.InMemConstructionIndex inMemIndex = index.getPrepareInMemIndex(EdgeFilter.ALL_EDGES);
-        assertEquals(IntArrayList.from(new int[]{4, 4}), index.getEntries());
-
-        assertEquals(4, inMemIndex.getEntriesOf(0).size());
-        assertEquals(10, inMemIndex.getEntriesOf(1).size());
-        assertEquals(0, inMemIndex.getEntriesOf(2).size());
-        // [LEAF 0 {} {0, 2}, LEAF 2 {} {0, 1}, LEAF 1 {} {2}, LEAF 3 {} {1}, LEAF 8 {} {0}, LEAF 10 {} {0}, LEAF 9 {} {0}, LEAF 4 {} {2}, LEAF 6 {} {0, 1, 2, 3}, LEAF 5 {} {0, 2, 3}, LEAF 7 {} {1, 2, 3}, LEAF 13 {} {1}]        
-        // System.out.println(inMemIndex.getLayer(2));
-
-        index.dataAccess.create(10);
-        inMemIndex.store(inMemIndex.root, LocationIndexTree.START_POINTER);
-        // [LEAF 0 {2} {},    LEAF 2 {1} {},    LEAF 1 {2} {}, LEAF 3 {1} {}, LEAF 8 {0} {}, LEAF 10 {0} {}, LEAF 9 {0} {}, LEAF 4 {2} {}, LEAF 6 {0, 3} {},       LEAF 5 {0, 2, 3} {}, LEAF 7 {1, 2, 3} {}, LEAF 13 {1} {}]
-        // System.out.println(inMemIndex.getLayer(2));
-
-        GHIntHashSet set = new GHIntHashSet();
-        set.add(0);
-
-        GHIntHashSet foundIds = new GHIntHashSet();
-        index.findNetworkEntries(0.5, -0.5, foundIds, 0);
-        assertEquals(set, foundIds);
-
-        set.add(1);
-        set.add(2);
-        foundIds.clear();
-        index.findNetworkEntries(-0.5, -0.9, foundIds, 0);
-        index.findNetworkEntries(-0.5, -0.9, foundIds, 1);
-        assertEquals(set, foundIds);
-        assertEquals(2, findID(index, -0.5, -0.9));
-
-        // The optimization if(dist > normedHalf) => feed nodeA or nodeB
-        // although this reduces chance of nodes outside of the tile
-        // in practice it even increases file size!?
-        // Is this due to the CHGraph disconnect problem?
-//        set.clear();
-//        set.add(4);
-//        assertEquals(set, index.findNetworkEntries(-0.7, 1.5));
-//        
-//        set.clear();
-//        set.add(4);
-//        assertEquals(set, index.findNetworkEntries(-0.5, 0.5));
-    }
-
-    @Test
-    public void testInMemIndex2() {
-        Graph graph = createTestGraph2();
-        LocationIndexTree index = createIndexNoPrepare(graph, 500);
-        index.prepareAlgo();
-        LocationIndexTree.InMemConstructionIndex inMemIndex = index.getPrepareInMemIndex(EdgeFilter.ALL_EDGES);
-        assertEquals(IntArrayList.from(new int[]{4, 4}), index.getEntries());
-        assertEquals(3, inMemIndex.getEntriesOf(0).size());
-        assertEquals(5, inMemIndex.getEntriesOf(1).size());
-        assertEquals(0, inMemIndex.getEntriesOf(2).size());
-
-        index.dataAccess.create(10);
-        inMemIndex.store(inMemIndex.root, LocationIndexTree.START_POINTER);
-
-        // 0
-        assertEquals(2L, index.keyAlgo.encode(49.94653, 11.57114));
-        // 1
-        assertEquals(3L, index.keyAlgo.encode(49.94653, 11.57214));
-        // 28
-        assertEquals(6L, index.keyAlgo.encode(49.95053, 11.57714));
-        // 29
-        assertEquals(6L, index.keyAlgo.encode(49.95053, 11.57814));
-        // 8
-        assertEquals(1L, index.keyAlgo.encode(49.94553, 11.57214));
-        // 34
-        assertEquals(12L, index.keyAlgo.encode(49.95153, 11.57714));
-
-        // Query near point 25 (49.95053, 11.57314).
-        // If we would have a perfect compaction (takes a lot longer) we would
-        // get only 0 or any node in the lefter greater subgraph.
-        // The other subnetwork is already perfect {26}.
-        // For compaction see: https://github.com/graphhopper/graphhopper/blob/5594f7f9d98d932f365557dc37b4b2d3b7abf698/core/src/main/java/com/graphhopper/storage/index/Location2NodesNtree.java#L277
-        GHIntHashSet set = new GHIntHashSet();
-        set.addAll(28, 27, 26, 24, 23, 21, 19, 18, 16, 14, 6, 5, 4, 3, 2, 1, 0);
-
-        GHIntHashSet foundIds = new GHIntHashSet();
-        index.findNetworkEntries(49.950, 11.5732, foundIds, 0);
-        assertEquals(set, foundIds);
-    }
-
-    @Test
-    public void testInMemIndex3() {
-        Graph graph = createTestGraph(encodingManager);
-        LocationIndexTree index = createIndexNoPrepare(graph, 10000);
-        index.prepareAlgo();
-        LocationIndexTree.InMemConstructionIndex inMemIndex = index.getPrepareInMemIndex(EdgeFilter.ALL_EDGES);
-        assertEquals(IntArrayList.from(new int[]{16, 4, 4}), index.getEntries());
-
-        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);
-        assertEquals(1 << 20, index.getCapacity());
-
-        Snap res = index.findClosest(-.5, -.5, EdgeFilter.ALL_EDGES);
-        assertEquals(1, res.getClosestNode());
-    }
-
-    @Test
-    public void testReverseSpatialKey() {
-        LocationIndexTree index = createIndex(createTestGraph(encodingManager), 200);
-        assertEquals(IntArrayList.from(new int[]{16, 16, 16, 16, 4, 4}), index.getEntries());
-
-        // 10111110111110101010
-        String str44 = "00000000000000000000000000000000000000000000";
-        assertEquals(str44 + "01010101111101111101", BitUtil.BIG.toBitString(index.createReverseKey(1.7, 0.099)));
+        // Also all edges (see testgraph2.jpg)
+        assertEquals(edges.size(), graph.getEdges());
     }
 
     @Test
     public void testMoreReal() {
         FlagEncoder encoder = new CarFlagEncoder();
-        Graph graph = createGHStorage(EncodingManager.create(encoder));
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), EncodingManager.create(encoder), false).create(100);
         NodeAccess na = graph.getNodeAccess();
         na.setNode(1, 51.2492152, 9.4317166);
         na.setNode(0, 52, 9);
         na.setNode(2, 51.2, 9.4);
         na.setNode(3, 49, 10);
 
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 0).setDistance(1000));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2).setDistance(1000));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 3).setDistance(1000)).setWayGeometry(Helper.createPointList(51.21, 9.43));
-        LocationIndex index = createIndex(graph, -1);
-        assertEquals(2, findID(index, 51.2, 9.4));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 0));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 3)).setWayGeometry(Helper.createPointList(51.21, 9.43));
+        LocationIndex index = (LocationIndexTree) createIndexNoPrepare(graph, 500000).prepareIndex();
+        assertEquals(1, findClosestEdge(index, 51.2, 9.4));
     }
 
     //    -1    0   1 1.5
@@ -283,7 +180,7 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     //-1|  2---------/
     //  |
     private Graph createTestGraphWithWayGeometry() {
-        Graph graph = createGHStorage(encodingManager);
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
         FlagEncoder encoder = encodingManager.getEncoder("car");
         NodeAccess na = graph.getNodeAccess();
         na.setNode(0, 0.5, -0.5);
@@ -291,48 +188,48 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         na.setNode(2, -1, -1);
         na.setNode(3, -0.4, 0.9);
         na.setNode(4, -0.6, 1.6);
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 1).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2).setDistance(1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 2));
         // insert A and B, without this we would get 0 for 0,0
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 4).setDistance(1)).setWayGeometry(Helper.createPointList(1, 1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 3).setDistance(1)).setWayGeometry(Helper.createPointList(0, 0));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 3).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 4).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(3, 4).setDistance(1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(0, 4)).setWayGeometry(Helper.createPointList(1, 1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 3)).setWayGeometry(Helper.createPointList(0, 0));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(2, 4));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(3, 4));
         return graph;
     }
 
     @Test
     public void testWayGeometry() {
         Graph g = createTestGraphWithWayGeometry();
-        LocationIndex index = createIndex(g, -1);
-        assertEquals(1, findID(index, 0, 0));
-        assertEquals(1, findID(index, 0, 0.1));
-        assertEquals(1, findID(index, 0.1, 0.1));
-        assertEquals(1, findID(index, -0.5, -0.5));
+        LocationIndex index = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+        assertEquals(3, findClosestEdge(index, 0, 0));
+        assertEquals(3, findClosestEdge(index, 0, 0.1));
+        assertEquals(3, findClosestEdge(index, 0.1, 0.1));
+        assertEquals(1, findClosestNode(index, -0.5, -0.5));
     }
 
     @Test
     public void testFindingWayGeometry() {
-        Graph g = createGHStorage(encodingManager);
+        Graph g = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
         FlagEncoder encoder = encodingManager.getEncoder("car");
         NodeAccess na = g.getNodeAccess();
         na.setNode(10, 51.2492152, 9.4317166);
         na.setNode(20, 52, 9);
         na.setNode(30, 51.2, 9.4);
         na.setNode(50, 49, 10);
-        GHUtility.setSpeed(60, true, true, encoder, g.edge(20, 50).setDistance(1)).setWayGeometry(Helper.createPointList(51.25, 9.43));
-        GHUtility.setSpeed(60, true, true, encoder, g.edge(10, 20).setDistance(1));
-        GHUtility.setSpeed(60, true, true, encoder, g.edge(20, 30).setDistance(1));
+        GHUtility.setSpeed(60, true, true, encoder, g.edge(20, 50)).setWayGeometry(Helper.createPointList(51.25, 9.43));
+        GHUtility.setSpeed(60, true, true, encoder, g.edge(10, 20));
+        GHUtility.setSpeed(60, true, true, encoder, g.edge(20, 30));
 
-        LocationIndex index = createIndex(g, 2000);
-        assertEquals(20, findID(index, 51.25, 9.43));
+        LocationIndex index = (LocationIndexTree) createIndexNoPrepare(g, 2000).prepareIndex();
+        assertEquals(0, findClosestEdge(index, 51.25, 9.43));
     }
 
     @Test
     public void testEdgeFilter() {
         Graph graph = createTestGraph(encodingManager);
-        LocationIndexTree index = createIndex(graph, -1);
+        LocationIndexTree index = (LocationIndexTree) createIndexNoPrepare(graph, 500000).prepareIndex();
 
         assertEquals(1, index.findClosest(-.6, -.6, EdgeFilter.ALL_EDGES).getClosestNode());
         assertEquals(2, index.findClosest(-.6, -.6, new EdgeFilter() {
@@ -346,7 +243,7 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     // see testgraph2.jpg
     Graph createTestGraph2() {
         FlagEncoder encoder = encodingManager.getEncoder("car");
-        Graph graph = createGHStorage(new RAMDirectory(), encodingManager, false);
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
         NodeAccess na = graph.getNodeAccess();
 
         na.setNode(0, 49.94653, 11.57114);
@@ -398,76 +295,55 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         na.setNode(101, 49.96053, 11.58814);
 
         GHUtility.setSpeed(60, 60, encoder,
-                graph.edge(0, 1).setDistance(10),
-                graph.edge(1, 2).setDistance(10),
-                graph.edge(2, 3).setDistance(10),
-                graph.edge(3, 4).setDistance(10),
-                graph.edge(4, 5).setDistance(10),
-                graph.edge(6, 7).setDistance(10),
-                graph.edge(2, 8).setDistance(10),
-                graph.edge(2, 9).setDistance(10),
-                graph.edge(3, 10).setDistance(10),
-                graph.edge(4, 11).setDistance(10),
-                graph.edge(5, 12).setDistance(10),
-                graph.edge(6, 13).setDistance(10),
-
-                graph.edge(1, 14).setDistance(10),
-                graph.edge(2, 15).setDistance(10),
-                graph.edge(5, 16).setDistance(10),
-                graph.edge(14, 15).setDistance(10),
-                graph.edge(16, 17).setDistance(10),
-                graph.edge(16, 20).setDistance(10),
-                graph.edge(16, 25).setDistance(10),
-
-                graph.edge(18, 14).setDistance(10),
-                graph.edge(18, 19).setDistance(10),
-                graph.edge(18, 21).setDistance(10),
-                graph.edge(19, 21).setDistance(10),
-                graph.edge(21, 24).setDistance(10),
-                graph.edge(23, 24).setDistance(10),
-                graph.edge(24, 25).setDistance(10),
-                graph.edge(26, 27).setDistance(10),
-                graph.edge(27, 28).setDistance(10),
-                graph.edge(28, 29).setDistance(10),
-
-                graph.edge(24, 30).setDistance(10),
-                graph.edge(24, 31).setDistance(10),
-                graph.edge(26, 32).setDistance(10),
-                graph.edge(26, 22).setDistance(10),
-                graph.edge(27, 33).setDistance(10),
-                graph.edge(28, 34).setDistance(10));
+                graph.edge(0, 1),
+                graph.edge(1, 2),
+                graph.edge(2, 3),
+                graph.edge(3, 4),
+                graph.edge(4, 5),
+                graph.edge(6, 7),
+                graph.edge(2, 8),
+                graph.edge(2, 9),
+                graph.edge(3, 10),
+                graph.edge(4, 11),
+                graph.edge(5, 12),
+                graph.edge(6, 13),
+
+                graph.edge(1, 14),
+                graph.edge(2, 15),
+                graph.edge(5, 16),
+                graph.edge(14, 15),
+                graph.edge(16, 17),
+                graph.edge(16, 20),
+                graph.edge(16, 25),
+
+                graph.edge(18, 14),
+                graph.edge(18, 19),
+                graph.edge(18, 21),
+                graph.edge(19, 21),
+                graph.edge(21, 24),
+                graph.edge(23, 24),
+                graph.edge(24, 25),
+                graph.edge(26, 27),
+                graph.edge(27, 28),
+                graph.edge(28, 29),
+
+                graph.edge(24, 30),
+                graph.edge(24, 31),
+                graph.edge(26, 32),
+                graph.edge(26, 22),
+                graph.edge(27, 33),
+                graph.edge(28, 34));
         return graph;
     }
 
     @Test
     public void testRMin() {
         Graph graph = createTestGraph(encodingManager);
-        LocationIndexTree index = createIndex(graph, 50000);
-
-        //query: 0.05 | -0.3
+        LocationIndexTree index = (LocationIndexTree) createIndexNoPrepare(graph, 50000).prepareIndex();
         DistanceCalc distCalc = new DistancePlaneProjection();
-
-        double rmin = index.calculateRMin(0.05, -0.3);
-        double check = distCalc.calcDist(0.05, Math.abs(graph.getNodeAccess().getLon(2)) - index.getDeltaLon(), -0.3, -0.3);
-
-        assertTrue((rmin - check) < 0.0001);
-
         double rmin2 = index.calculateRMin(0.05, -0.3, 1);
         double check2 = distCalc.calcDist(0.05, Math.abs(graph.getNodeAccess().getLat(0)), -0.3, -0.3);
-
         assertTrue((rmin2 - check2) < 0.0001);
-
-        GHIntHashSet points = new GHIntHashSet();
-        assertEquals(Double.MAX_VALUE, index.calcMinDistance(0.05, -0.3, points), 1e-1);
-
-        points.add(0);
-        points.add(1);
-        assertEquals(54757.03, index.calcMinDistance(0.05, -0.3, points), 1e-1);
-
-        /*GraphVisualizer gv = new GraphVisualizer(graph, index.getDeltaLat(), index.getDeltaLon(), index.getCenter(0, 0).lat, index.getCenter(0, 0).lon);
-         try {
-         Thread.sleep(4000);
-         } catch(InterruptedException ie) {}*/
     }
 
     @Test
@@ -476,7 +352,7 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         BikeFlagEncoder bikeEncoder = new BikeFlagEncoder();
 
         EncodingManager tmpEM = EncodingManager.create(carEncoder, bikeEncoder);
-        Graph graph = createGHStorage(new RAMDirectory(), tmpEM, false);
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), tmpEM, false).create(100);
         NodeAccess na = graph.getNodeAccess();
 
         // distance from point to point is roughly 1 km
@@ -486,10 +362,10 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
                 int index = lonIdx * 10 + latIdx;
                 na.setNode(index, 0.01 * latIdx, 0.01 * lonIdx);
                 if (latIdx < MAX - 1)
-                    GHUtility.setSpeed(60, true, true, carEncoder, graph.edge(index, index + 1).setDistance(1000));
+                    GHUtility.setSpeed(60, true, true, carEncoder, graph.edge(index, index + 1));
 
                 if (lonIdx < MAX - 1)
-                    GHUtility.setSpeed(60, true, true, carEncoder, graph.edge(index, index + 10).setDistance(1000));
+                    GHUtility.setSpeed(60, true, true, carEncoder, graph.edge(index, index + 10));
             }
         }
 
@@ -524,7 +400,7 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
     @Test
     public void testCrossBoundaryNetwork_issue667() {
         FlagEncoder encoder = encodingManager.getEncoder("car");
-        Graph graph = createGHStorage(new RAMDirectory(), encodingManager, false);
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
         NodeAccess na = graph.getNodeAccess();
         na.setNode(0, 0.1, 179.5);
         na.setNode(1, 0.1, 179.9);
@@ -537,22 +413,22 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
 
         // just use 1 as distance which is incorrect but does not matter in this unit case
         GHUtility.setSpeed(60, 60, encoder,
-                graph.edge(0, 1).setDistance(1),
-                graph.edge(0, 4).setDistance(1),
-                graph.edge(1, 5).setDistance(1),
-                graph.edge(4, 5).setDistance(1),
+                graph.edge(0, 1),
+                graph.edge(0, 4),
+                graph.edge(1, 5),
+                graph.edge(4, 5),
 
-                graph.edge(2, 3).setDistance(1),
-                graph.edge(2, 6).setDistance(1),
-                graph.edge(3, 7).setDistance(1),
-                graph.edge(6, 7).setDistance(1));
+                graph.edge(2, 3),
+                graph.edge(2, 6),
+                graph.edge(3, 7),
+                graph.edge(6, 7));
 
         // as last edges: create cross boundary edges
         // See #667 where the recommendation is to adjust the import and introduce two pillar nodes 
         // where the connection is cross boundary and would be okay if ignored as real length is 0
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 2).setDistance(1)).setWayGeometry(Helper.createPointList(0, 180, 0, -180));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(1, 2)).setWayGeometry(Helper.createPointList(0, 180, 0, -180));
         // but this unit test succeeds even without this adjusted import:
-        GHUtility.setSpeed(60, true, true, encoder, graph.edge(5, 6).setDistance(1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(5, 6));
 
         LocationIndexTree index = createIndexNoPrepare(graph, 500);
         index.prepareIndex();
@@ -564,55 +440,188 @@ public class LocationIndexTreeTest extends AbstractLocationIndexTester {
         }
     }
 
-    // 0---1---2
-    // |   |   |
-    // |10 |   |
-    // | | |   |
-    // 3-9-4---5
-    // |   |   |
-    // 6---7---8
+    private int findClosestNode(LocationIndex index, double lat, double lon) {
+        Snap closest = index.findClosest(lat, lon, EdgeFilter.ALL_EDGES);
+        assert closest.getSnappedPosition() == Snap.Position.TOWER;
+        return closest.getClosestNode();
+    }
+
+    private int findClosestEdge(LocationIndex index, double lat, double lon) {
+        return index.findClosest(lat, lon, EdgeFilter.ALL_EDGES).getClosestEdge().getEdge();
+    }
+
     @Test
-    public void testFindNClosest() {
-        Graph graph = createGHStorage(new RAMDirectory(), encodingManager, false);
-        NodeAccess na = graph.getNodeAccess();
-        na.setNode(0, 0.0010, 0.0000);
-        na.setNode(1, 0.0010, 0.0005);
-        na.setNode(2, 0.0010, 0.0010);
-        na.setNode(3, 0.0005, 0.0000);
-        na.setNode(4, 0.0005, 0.0005);
-        na.setNode(5, 0.0005, 0.0010);
-        na.setNode(6, 0.0000, 0.0000);
-        na.setNode(7, 0.0000, 0.0005);
-        na.setNode(8, 0.0000, 0.0010);
-        na.setNode(9, 0.0005, 0.0002);
-        na.setNode(10, 0.0007, 0.0002);
-        graph.edge(0, 1);
-        graph.edge(1, 2);
-        graph.edge(0, 3);
-        graph.edge(1, 4);
-        graph.edge(2, 5);
-        graph.edge(3, 9);
-        graph.edge(9, 4);
-        EdgeIteratorState edge4_5 = graph.edge(4, 5);
-        graph.edge(10, 9);
-        graph.edge(3, 6);
-        EdgeIteratorState edge4_7 = graph.edge(4, 7);
-        graph.edge(5, 8);
-        graph.edge(6, 7);
-        graph.edge(7, 8);
+    public void testSimpleGraph() {
+        EncodingManager em = EncodingManager.create("car");
+        Graph g = new GraphHopperStorage(new RAMDirectory(), em, false).create(100);
+        initSimpleGraph(g, em);
+
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+        assertEquals(3, findClosestEdge(idx, 5, 2));
+        assertEquals(3, findClosestEdge(idx, 1.5, 2));
+        assertEquals(1, findClosestEdge(idx, -1, -1));
+        assertEquals(4, findClosestEdge(idx, 4, 0));
+        Helper.close((Closeable) g);
+    }
 
-        LocationIndexTree index = createIndexNoPrepare(graph, 500);
-        index.prepareIndex();
+    @Test
+    public void testSimpleGraph2() {
+        EncodingManager em = EncodingManager.create("car");
+        Graph g = new GraphHopperStorage(new RAMDirectory(), em, false).create(100);
+        initSimpleGraph(g, em);
+
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+        assertEquals(3, findClosestEdge(idx, 5, 2));
+        assertEquals(3, findClosestEdge(idx, 1.5, 2));
+        assertEquals(1, findClosestEdge(idx, -1, -1));
+        assertEquals(6, findClosestNode(idx, 4.5, -0.5));
+        assertEquals(3, findClosestEdge(idx, 4, 1));
+        assertEquals(4, findClosestEdge(idx, 4, 0));
+        assertEquals(6, findClosestNode(idx, 4, -2));
+        assertEquals(5, findClosestEdge(idx, 3, 3));
+        Helper.close((Closeable) g);
+    }
+
+    @Test
+    public void testSinglePoints120() {
+        Graph g = createSampleGraph(EncodingManager.create("car"));
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+
+        assertEquals(3, findClosestEdge(idx, 1.637, 2.23));
+        assertEquals(10, findClosestEdge(idx, 3.649, 1.375));
+        assertEquals(9, findClosestNode(idx, 3.3, 2.2));
+        assertEquals(6, findClosestNode(idx, 3.0, 1.5));
+
+        assertEquals(15, findClosestEdge(idx, 3.8, 0));
+        assertEquals(15, findClosestEdge(idx, 3.8466, 0.021));
+        Helper.close((Closeable) g);
+    }
+
+    @Test
+    public void testSinglePoints32() {
+        Graph g = createSampleGraph(EncodingManager.create("car"));
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+
+        assertEquals(10, findClosestEdge(idx, 3.649, 1.375));
+        assertEquals(15, findClosestEdge(idx, 3.8465748, 0.021762699));
+        assertEquals(4, findClosestEdge(idx, 2.485, 1.373));
+        assertEquals(0, findClosestEdge(idx, 0.64628404, 0.53006625));
+        Helper.close((Closeable) g);
+    }
 
-        // query node 4 => get at least 4-5, 4-7
-        List<Snap> result = index.findNClosest(0.0004, 0.0006, EdgeFilter.ALL_EDGES, 15);
-        List<Integer> ids = new ArrayList<>();
-        for (Snap snap : result) {
-            ids.add(snap.getClosestEdge().getEdge());
+    @Test
+    public void testNoErrorOnEdgeCase_lastIndex() {
+        final EncodingManager encodingManager = EncodingManager.create("car");
+        int locs = 10000;
+        Graph g = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
+        NodeAccess na = g.getNodeAccess();
+        Random rand = new Random(12);
+        for (int i = 0; i < locs; i++) {
+            na.setNode(i, (float) rand.nextDouble() * 10 + 10, (float) rand.nextDouble() * 10 + 10);
         }
-        Collections.sort(ids);
-        assertEquals("edge ids do not match",
-                Arrays.asList(edge4_5.getEdge(), edge4_7.getEdge()), ids);
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 200).prepareIndex();
+        Helper.close((Closeable) g);
+    }
+
+    public Graph createSampleGraph(EncodingManager encodingManager) {
+        Graph graph = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
+        // length does not matter here but lat,lon and outgoing edges do!
+
+//
+//   lat             /--------\
+//    5   o-        p--------\ q
+//          \  /-----\-----n | |
+//    4       k    /--l--    m/
+//           / \  j      \   |
+//    3     |   g  \  h---i  /
+//          |       \    /  /
+//    2     e---------f--  /
+//                   /  \-d
+//    1        /--b--      \
+//            |    \--------c
+//    0       a
+//
+//   lon: 0   1   2   3   4   5
+        int a0 = 0;
+        NodeAccess na = graph.getNodeAccess();
+        na.setNode(0, 0, 1.0001f);
+        int b1 = 1;
+        na.setNode(1, 1, 2);
+        int c2 = 2;
+        na.setNode(2, 0.5f, 4.5f);
+        int d3 = 3;
+        na.setNode(3, 1.5f, 3.8f);
+        int e4 = 4;
+        na.setNode(4, 2.01f, 0.5f);
+        int f5 = 5;
+        na.setNode(5, 2, 3);
+        int g6 = 6;
+        na.setNode(6, 3, 1.5f);
+        int h7 = 7;
+        na.setNode(7, 2.99f, 3.01f);
+        int i8 = 8;
+        na.setNode(8, 3, 4);
+        int j9 = 9;
+        na.setNode(9, 3.3f, 2.2f);
+        int k10 = 10;
+        na.setNode(10, 4, 1);
+        int l11 = 11;
+        na.setNode(11, 4.1f, 3);
+        int m12 = 12;
+        na.setNode(12, 4, 4.5f);
+        int n13 = 13;
+        na.setNode(13, 4.5f, 4.1f);
+        int o14 = 14;
+        na.setNode(14, 5, 0);
+        int p15 = 15;
+        na.setNode(15, 4.9f, 2.5f);
+        int q16 = 16;
+        na.setNode(16, 5, 5);
+        // => 17 locations
+
+        FlagEncoder encoder = encodingManager.getEncoder("car");
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(a0, b1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(c2, b1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(c2, d3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, b1));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(e4, f5));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(m12, d3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(e4, k10));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, d3));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, i8));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(f5, j9));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, g6));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(j9, l11));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(i8, l11));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(i8, h7));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, n13));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(k10, o14));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(l11, p15));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(m12, p15));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(q16, p15));
+        GHUtility.setSpeed(60, true, true, encoder, graph.edge(q16, m12));
+        return graph;
     }
 
+    @Test
+    public void testDifferentVehicles() {
+        final EncodingManager encodingManager = EncodingManager.create("car,foot");
+        Graph g = new GraphHopperStorage(new RAMDirectory(), encodingManager, false).create(100);
+        initSimpleGraph(g, encodingManager);
+        LocationIndexTree idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+        assertEquals(0, findClosestEdge(idx, 1, -1));
+
+        // now make all edges from node 1 accessible for CAR only
+        EdgeIterator iter = g.createEdgeExplorer().setBaseNode(1);
+        FlagEncoder encoder = encodingManager.getEncoder("foot");
+        BooleanEncodedValue accessEnc = encoder.getAccessEnc();
+        while (iter.next()) {
+            iter.set(accessEnc, false, false);
+        }
+
+        idx = (LocationIndexTree) createIndexNoPrepare(g, 500000).prepareIndex();
+        FootFlagEncoder footEncoder = (FootFlagEncoder) encodingManager.getEncoder("foot");
+        assertEquals(2, idx.findClosest(1, -1, DefaultEdgeFilter.allEdges(footEncoder)).getClosestNode());
+        Helper.close((Closeable) g);
+    }
 }
diff --git a/core/src/test/java/com/graphhopper/storage/index/PixelGridTraversalTest.java b/core/src/test/java/com/graphhopper/storage/index/PixelGridTraversalTest.java
new file mode 100644
index 000000000..62ac5d849
--- /dev/null
+++ b/core/src/test/java/com/graphhopper/storage/index/PixelGridTraversalTest.java
@@ -0,0 +1,66 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.storage.index;
+
+import com.graphhopper.util.shapes.BBox;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.CsvSource;
+import org.locationtech.jts.algorithm.RectangleLineIntersector;
+import org.locationtech.jts.geom.Coordinate;
+import org.locationtech.jts.geom.Envelope;
+
+import java.util.HashSet;
+import java.util.Set;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+public class PixelGridTraversalTest {
+
+    @ParameterizedTest
+    @CsvSource({
+            "5.5, 2.5, 0.5, 0.5",
+            "3.5, 1.5, 0.5, 3.5",
+            "2.5, 2.5, 3.5, 0.5",
+            "0.5, 0.5, 2.5, 3.5",
+            "2.5, 2.9, 3.1, 0.9"
+    })
+    public void testAgainstNaiveGridCellIntersection(double x1, double y1, double x2, double y2) {
+        BBox bounds = new BBox(0.0, 10.0, 0.0, 10.0);
+        int parts = 10;
+        Coordinate a = new Coordinate(x1, y1);
+        Coordinate b = new Coordinate(x2, y2);
+
+        Set<Coordinate> actual = new HashSet<>();
+        PixelGridTraversal pixelGridTraversal = new PixelGridTraversal(parts, bounds);
+        pixelGridTraversal.traverse(a, b, actual::add);
+
+        Set<Coordinate> expected = new HashSet<>();
+        double deltaLat = (bounds.maxLat - bounds.minLat) / parts;
+        double deltaLon = (bounds.maxLon - bounds.minLon) / parts;
+        for (int y = 0; y < parts; y++) {
+            for (int x = 0; x < parts; x++) {
+                RectangleLineIntersector rectangleLineIntersector = new RectangleLineIntersector(new Envelope(bounds.minLon + x * deltaLon, bounds.minLon + (x+1) * deltaLon, bounds.minLat + y* deltaLat, bounds.minLat+ (y+1) * deltaLat));
+                if (rectangleLineIntersector.intersects(a, b)) {
+                    expected.add(new Coordinate(x, y));
+                }
+            }
+        }
+        assertEquals(expected, actual);
+    }
+
+}
diff --git a/core/src/test/java/com/graphhopper/util/AbstractBitUtilTester.java b/core/src/test/java/com/graphhopper/util/AbstractBitUtilTester.java
index 8a3706b32..40cad11d7 100644
--- a/core/src/test/java/com/graphhopper/util/AbstractBitUtilTester.java
+++ b/core/src/test/java/com/graphhopper/util/AbstractBitUtilTester.java
@@ -89,23 +89,4 @@ public abstract class AbstractBitUtilTester {
         assertEquals("011", bitUtil.toLastBitString(3L, 3));
     }
 
-    @Test
-    public void testBitString2Long() {
-        String str = "01000000000110000011100000011110";
-        assertEquals(str + "00000000000000000000000000000000", bitUtil.toBitString(bitUtil.fromBitString2Long(str)));
-        assertEquals("1000000000000000000000000000000000000000000000000000000000000000", bitUtil.toBitString(1L << 63));
-    }
-
-    @Test
-    public void testReverse() {
-        String str48 = "000000000000000000000000000000000000000000000000";
-        long ret = bitUtil.reverse(bitUtil.fromBitString2Long(str48 + "0111000000000101"), 16);
-        assertEquals(str48 + "1010000000001110", bitUtil.toBitString(ret, 64));
-
-        ret = bitUtil.reverse(bitUtil.fromBitString2Long(str48 + "0111000000000101"), 8);
-        assertEquals(str48 + "0000000010100000", bitUtil.toBitString(ret, 64));
-
-//        ret = BitUtil.BIG.reversePart(bitUtil.fromBitString2Long("0111000000000101"), 8);
-//        assertEquals("0111000010100000", bitUtil.toBitString(ret, 16));
-    }
 }
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 fa2426cef..1c69d9d22 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
@@ -178,15 +178,16 @@ public class GraphHopperOSMTest {
         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) {
+        index.query(bbox, new LocationIndexTree.Visitor() {
             @Override
             public void onTile(BBox bbox, int width) {
             }
 
             @Override
-            public void onEdge(EdgeIteratorState edge, int nodeA, int nodeB) {
+            public void onEdge(int edgeId) {
+                EdgeIteratorState edge = gh.getGraphHopperStorage().getEdgeIteratorStateForKey(edgeId * 2);
                 for (int i = 0; i < 2; i++) {
-                    int nodeId = i == 0 ? nodeA : nodeB;
+                    int nodeId = i == 0 ? edge.getBaseNode() : edge.getAdjNode();
                     double lat = na.getLatitude(nodeId);
                     double lon = na.getLongitude(nodeId);
                     if (bbox.contains(lat, lon))
@@ -429,6 +430,13 @@ public class GraphHopperOSMTest {
                 setDataReaderFile(testOsm8);
         instance.importOrLoad();
 
+        // This test is arguably a bit unfair: It expects the LocationIndex
+        // to find a foot edge that is many tiles away.
+        // Previously, it worked, but only because of the way the LocationIndex would traverse the Graph
+        // (it would also go into CAR edges to find WALK edges).
+        // Now it doesn't work like that anymore, so I set this parameter so the test doesn't fail.
+        ((LocationIndexTree) instance.getLocationIndex()).setMaxRegionSearch(300);
+
         assertEquals(5, instance.getGraphHopperStorage().getNodes());
         assertEquals(8, instance.getGraphHopperStorage().getEdges());
 
@@ -699,6 +707,8 @@ public class GraphHopperOSMTest {
         instance.getCHPreparationHandler().setCHProfiles(new CHProfile(profile));
         instance.importOrLoad();
 
+        ((LocationIndexTree) instance.getLocationIndex()).setMaxRegionSearch(300);
+
         assertEquals(2, instance.getGraphHopperStorage().getNodes());
         assertEquals(2, instance.getGraphHopperStorage().getAllEdges().length());
 
diff --git a/web/src/test/java/com/graphhopper/http/MapMatching2Test.java b/web/src/test/java/com/graphhopper/http/MapMatching2Test.java
index 79ef02261..1fa3f44d6 100644
--- a/web/src/test/java/com/graphhopper/http/MapMatching2Test.java
+++ b/web/src/test/java/com/graphhopper/http/MapMatching2Test.java
@@ -81,9 +81,6 @@ public class MapMatching2Test {
             validateEdgeMatch(em);
         }
 
-        // create street names
-        assertEquals(Arrays.asList("", "", "", "", "", ""),
-                fetchStreets(mr.getEdgeMatches()));
         assertEquals(mr.getGpxEntriesLength(), mr.getMatchLength(), 2.5);
         assertEquals(28790, mr.getMatchMillis(), 50);
     }
@@ -105,11 +102,7 @@ public class MapMatching2Test {
         Gpx gpx = xmlMapper.readValue(getClass().getResourceAsStream("/issue-70.gpx"), Gpx.class);
         MatchResult mr = mapMatching.match(gpx.trk.get(0).getEntries());
 
-        assertEquals(Arrays.asList("Милана Видака", "Милана Видака", "Милана Видака",
-                "Бранка Радичевића", "Бранка Радичевића", "Здравка Челара"),
-                fetchStreets(mr.getEdgeMatches()));
-        // TODO: length/time
-
+        assertEquals(Arrays.asList("Милана Видака", "Бранка Радичевића", "Здравка Челара"), fetchStreets(mr.getEdgeMatches()));
         for (EdgeMatch edgeMatch : mr.getEdgeMatches()) {
             validateEdgeMatch(edgeMatch);
         }
diff --git a/web/src/test/java/com/graphhopper/http/MapMatchingTest.java b/web/src/test/java/com/graphhopper/http/MapMatchingTest.java
index ee90088d8..da913cd08 100644
--- a/web/src/test/java/com/graphhopper/http/MapMatchingTest.java
+++ b/web/src/test/java/com/graphhopper/http/MapMatchingTest.java
@@ -120,17 +120,10 @@ public class MapMatchingTest {
         }
 
         // create street names
-        assertEquals(Arrays.asList("Platnerstraße", "Platnerstraße", "Platnerstraße"),
+        assertEquals(Arrays.asList("Platnerstraße"),
                 fetchStreets(mr.getEdgeMatches()));
         assertEquals(mr.getGpxEntriesLength(), mr.getMatchLength(), 1.5);
 
-        ResponsePath matchGHRsp =
-                new PathMerger(mr.getGraph(), mr.getWeighting()).doWork(PointList.EMPTY, Collections.singletonList(mr.getMergedPath()), graphHopper.getEncodingManager(), translationMap.get("en"));
-        InstructionList il = matchGHRsp.getInstructions();
-
-        assertEquals(il.toString(), 2, il.size());
-        assertEquals("Platnerstraße", il.get(0).getName());
-
         ResponsePath route1 = graphHopper.route(new GHRequest(
                 new GHPoint(51.33099, 12.380267),
                 new GHPoint(51.330531, 12.380396))
@@ -139,19 +132,9 @@ public class MapMatchingTest {
         mapMatching.setMeasurementErrorSigma(5);
         mr = mapMatching.match(inputGPXEntries);
 
-        assertEquals(Arrays.asList("Windmühlenstraße", "Windmühlenstraße", "Bayrischer Platz",
-                "Bayrischer Platz", "Bayrischer Platz"), fetchStreets(mr.getEdgeMatches()));
+        assertEquals(Arrays.asList("Windmühlenstraße", "Bayrischer Platz"), fetchStreets(mr.getEdgeMatches()));
         assertEquals(mr.getGpxEntriesLength(), mr.getMatchLength(), .1);
 
-        matchGHRsp =
-                new PathMerger(mr.getGraph(), mr.getWeighting()).doWork(PointList.EMPTY, Collections.singletonList(mr.getMergedPath()),
-                        graphHopper.getEncodingManager(), translationMap.get("en"));
-        il = matchGHRsp.getInstructions();
-
-        assertEquals(il.toString(), 3, il.size());
-        assertEquals("Windmühlenstraße", il.get(0).getName());
-        assertEquals("Bayrischer Platz", il.get(1).getName());
-
         ResponsePath route = graphHopper.route(new GHRequest(
                 new GHPoint(51.377781, 12.338333),
                 new GHPoint(51.323317, 12.387085))
@@ -234,8 +217,7 @@ public class MapMatchingTest {
         MapMatching mapMatching = new MapMatching(graphHopper, hints);
         mapMatching.setMeasurementErrorSigma(20);
         MatchResult mr = mapMatching.match(gpx.trk.get(0).getEntries());
-        assertEquals(Arrays.asList("Weinligstraße", "Weinligstraße", "Weinligstraße",
-                "Fechnerstraße", "Fechnerstraße"), fetchStreets(mr.getEdgeMatches()));
+        assertEquals(Arrays.asList("Weinligstraße", "Fechnerstraße"), fetchStreets(mr.getEdgeMatches()));
         assertEquals(mr.getGpxEntriesLength(), mr.getMatchLength(), 11); // TODO: this should be around 300m according to Google ... need to check
     }
 
@@ -253,9 +235,7 @@ public class MapMatchingTest {
         Gpx gpx = xmlMapper.readValue(getClass().getResourceAsStream("/tour2-with-loop.gpx"), Gpx.class);
         MatchResult mr = mapMatching.match(gpx.trk.get(0).getEntries());
         assertEquals(
-                Arrays.asList("Gustav-Adolf-Straße", "Gustav-Adolf-Straße", "Gustav-Adolf-Straße",
-                        "Leibnizstraße", "Hinrichsenstraße", "Hinrichsenstraße",
-                        "Tschaikowskistraße", "Tschaikowskistraße"),
+                Arrays.asList("Gustav-Adolf-Straße", "Leibnizstraße", "Hinrichsenstraße", "Tschaikowskistraße"),
                 fetchStreets(mr.getEdgeMatches()));
         assertEquals(mr.getGpxEntriesLength(), mr.getMatchLength(), 5);
     }
@@ -271,10 +251,9 @@ public class MapMatchingTest {
         mapMatching.setMeasurementErrorSigma(50);
         Gpx gpx = xmlMapper.readValue(getClass().getResourceAsStream("/tour-with-loop.gpx"), Gpx.class);
         MatchResult mr = mapMatching.match(gpx.trk.get(0).getEntries());
-        assertEquals(Arrays.asList("Jahnallee, B 87, B 181", "Jahnallee, B 87, B 181",
-                "Jahnallee, B 87, B 181", "Jahnallee, B 87, B 181", "Funkenburgstraße",
+        assertEquals(Arrays.asList("Jahnallee, B 87, B 181", "Funkenburgstraße",
                 "Gustav-Adolf-Straße", "Tschaikowskistraße", "Jahnallee, B 87, B 181",
-                "Lessingstraße", "Lessingstraße"), fetchStreets(mr.getEdgeMatches()));
+                "Lessingstraße"), fetchStreets(mr.getEdgeMatches()));
     }
 
     /**
@@ -295,18 +274,12 @@ public class MapMatchingTest {
         // with large measurement error, we expect no U-turn
         mapMatching.setMeasurementErrorSigma(50);
         MatchResult mr = mapMatching.match(gpx.trk.get(0).getEntries());
-
-        assertEquals(Arrays.asList("Gustav-Adolf-Straße", "Gustav-Adolf-Straße", "Funkenburgstraße",
-                "Funkenburgstraße"), fetchStreets(mr.getEdgeMatches()));
+        assertEquals(Arrays.asList("Gustav-Adolf-Straße", "Funkenburgstraße"), fetchStreets(mr.getEdgeMatches()));
 
         // with small measurement error, we expect the U-turn
         mapMatching.setMeasurementErrorSigma(10);
         mr = mapMatching.match(gpx.trk.get(0).getEntries());
-
-        assertEquals(
-                Arrays.asList("Gustav-Adolf-Straße", "Gustav-Adolf-Straße", "Funkenburgstraße",
-                        "Funkenburgstraße", "Funkenburgstraße", "Funkenburgstraße"),
-                fetchStreets(mr.getEdgeMatches()));
+        assertEquals(Arrays.asList("Gustav-Adolf-Straße", "Funkenburgstraße"), fetchStreets(mr.getEdgeMatches()));
     }
 
     static List<String> fetchStreets(List<EdgeMatch> emList) {
@@ -316,6 +289,7 @@ public class MapMatchingTest {
         for (EdgeMatch em : emList) {
             String str = em.getEdgeState().getName();// + ":" + em.getEdgeState().getBaseNode() +
             // "->" + em.getEdgeState().getAdjNode();
+            if (list.size() == 0 || !list.get(list.size()-1).equals(str))
             list.add(str);
             if (prevNode >= 0) {
                 if (em.getEdgeState().getBaseNode() != prevNode) {
diff --git a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceBikeTest.java b/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceBikeTest.java
deleted file mode 100644
index d6935c17c..000000000
--- a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceBikeTest.java
+++ /dev/null
@@ -1,78 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.http.resources;
-
-import com.fasterxml.jackson.databind.JsonNode;
-import com.graphhopper.config.Profile;
-import com.graphhopper.http.GraphHopperApplication;
-import com.graphhopper.http.GraphHopperServerConfiguration;
-import com.graphhopper.http.WebHelper;
-import com.graphhopper.util.Helper;
-import io.dropwizard.testing.junit5.DropwizardAppExtension;
-import io.dropwizard.testing.junit5.DropwizardExtensionsSupport;
-import org.junit.jupiter.api.AfterAll;
-import org.junit.jupiter.api.Test;
-import org.junit.jupiter.api.extension.ExtendWith;
-
-import javax.ws.rs.client.Entity;
-import javax.ws.rs.core.Response;
-import java.io.File;
-import java.util.Collections;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * @author Peter Karich
- */
-@ExtendWith(DropwizardExtensionsSupport.class)
-public class MapMatchingResourceBikeTest {
-
-    private static final String DIR = "../target/mapmatching2test";
-    public static final DropwizardAppExtension<GraphHopperServerConfiguration> app = new DropwizardAppExtension<>(GraphHopperApplication.class, createConfig());
-
-    private static GraphHopperServerConfiguration createConfig() {
-        GraphHopperServerConfiguration config = new GraphHopperServerConfiguration();
-        config.getGraphHopperConfiguration().
-                putObject("graph.flag_encoders", "bike").
-                putObject("datareader.file", "../map-matching/files/leipzig_germany.osm.pbf").
-                putObject("graph.location", DIR).
-                setProfiles(Collections.singletonList(new Profile("fast_bike").setVehicle("bike").setWeighting("fastest")));
-        return config;
-    }
-
-    @AfterAll
-    public static void cleanUp() {
-        Helper.removeDir(new File(DIR));
-    }
-
-    @Test
-    public void testGPX() {
-        final Response response = app.client().target("http://localhost:8080/match?vehicle=bike")
-                .request()
-                .buildPost(Entity.xml(getClass().getResourceAsStream("tour2-with-loop.gpx")))
-                .invoke();
-        assertEquals("no success", 200, response.getStatus());
-        JsonNode json = response.readEntity(JsonNode.class);
-        JsonNode path = json.get("paths").get(0);
-
-        assertEquals(5, path.get("instructions").size());
-        assertEquals(5, WebHelper.decodePolyline(path.get("points").asText(), 10, false).size());
-        // ensure that is actually also is bike! (slower than car)
-        assertEquals(162, path.get("time").asLong() / 1000f, 1);
-    }
-}
diff --git a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTest.java b/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTest.java
index 44dc9ca42..bd821b3b0 100644
--- a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTest.java
@@ -28,10 +28,15 @@ import io.dropwizard.testing.junit5.DropwizardExtensionsSupport;
 import org.junit.jupiter.api.AfterAll;
 import org.junit.jupiter.api.Test;
 import org.junit.jupiter.api.extension.ExtendWith;
+import org.locationtech.jts.algorithm.distance.DiscreteHausdorffDistance;
+import org.locationtech.jts.geom.LineString;
+import org.locationtech.jts.io.ParseException;
+import org.locationtech.jts.io.WKTReader;
 
 import javax.ws.rs.client.Entity;
 import javax.ws.rs.core.Response;
 import java.io.File;
+import java.util.Arrays;
 import java.util.Collections;
 
 import static org.junit.Assert.assertEquals;
@@ -49,10 +54,12 @@ public class MapMatchingResourceTest {
     private static GraphHopperServerConfiguration createConfig() {
         GraphHopperServerConfiguration config = new GraphHopperServerConfiguration();
         config.getGraphHopperConfiguration().
-                putObject("graph.flag_encoders", "car").
+                putObject("graph.flag_encoders", "car,bike").
                 putObject("datareader.file", "../map-matching/files/leipzig_germany.osm.pbf").
                 putObject("graph.location", DIR).
-                setProfiles(Collections.singletonList(new Profile("profile").setVehicle("car").setWeighting("fastest")));
+                setProfiles(Arrays.asList(
+                        new Profile("fast_car").setVehicle("car").setWeighting("fastest"),
+                        new Profile("fast_bike").setVehicle("bike").setWeighting("fastest")));
         return config;
     }
 
@@ -63,7 +70,7 @@ public class MapMatchingResourceTest {
 
     @Test
     public void testGPX() {
-        final Response response = app.client().target("http://localhost:8080/match")
+        final Response response = app.client().target("http://localhost:8080/match?profile=fast_car")
                 .request()
                 .buildPost(Entity.xml(getClass().getResourceAsStream("/tour2-with-loop.gpx")))
                 .invoke();
@@ -71,17 +78,37 @@ public class MapMatchingResourceTest {
         JsonNode json = response.readEntity(JsonNode.class);
         JsonNode path = json.get("paths").get(0);
 
-        assertEquals(5, path.get("instructions").size());
-        assertEquals(5, WebHelper.decodePolyline(path.get("points").asText(), 10, false).size());
+        LineString expectedGeometry = readWktLineString("LINESTRING (12.3607 51.34365, 12.36418 51.34443, 12.36379 51.34538, 12.36082 51.34471, 12.36188 51.34278)");
+        LineString actualGeometry = WebHelper.decodePolyline(path.get("points").asText(), 10, false).toLineString(false);
+        assertEquals(DiscreteHausdorffDistance.distance(expectedGeometry, actualGeometry), 0.0, 1E-4);
         assertEquals(106.15, path.get("time").asLong() / 1000f, 0.1);
         assertEquals(106.15, json.get("map_matching").get("time").asLong() / 1000f, 0.1);
         assertEquals(811.56, path.get("distance").asDouble(), 1);
         assertEquals(811.56, json.get("map_matching").get("distance").asDouble(), 1);
     }
 
+    @Test
+    public void testBike() throws ParseException {
+        WKTReader wktReader = new WKTReader();
+        final Response response = app.client().target("http://localhost:8080/match?profile=fast_bike")
+                .request()
+                .buildPost(Entity.xml(getClass().getResourceAsStream("tour2-with-loop.gpx")))
+                .invoke();
+        assertEquals("no success", 200, response.getStatus());
+        JsonNode json = response.readEntity(JsonNode.class);
+        JsonNode path = json.get("paths").get(0);
+
+        LineString expectedGeometry = (LineString) wktReader.read("LINESTRING (12.3607 51.34365, 12.36418 51.34443, 12.36379 51.34538, 12.36082 51.34471, 12.36188 51.34278)");
+        LineString actualGeometry = WebHelper.decodePolyline(path.get("points").asText(), 10, false).toLineString(false);
+        assertEquals(DiscreteHausdorffDistance.distance(expectedGeometry, actualGeometry), 0.0, 1E-4);
+
+        // ensure that is actually also is bike! (slower than car)
+        assertEquals(162, path.get("time").asLong() / 1000f, 1);
+    }
+
     @Test
     public void testGPX10() {
-        final Response response = app.client().target("http://localhost:8080/match")
+        final Response response = app.client().target("http://localhost:8080/match?profile=fast_car")
                 .request()
                 .buildPost(Entity.xml(getClass().getResourceAsStream("gpxv1_0.gpx")))
                 .invoke();
@@ -90,7 +117,7 @@ public class MapMatchingResourceTest {
 
     @Test
     public void testEmptyGPX() {
-        final Response response = app.client().target("http://localhost:8080/match")
+        final Response response = app.client().target("http://localhost:8080/match?profile=fast_car")
                 .request()
                 .buildPost(Entity.xml(getClass().getResourceAsStream("test-only-wpt.gpx")))
                 .invoke();
@@ -100,4 +127,16 @@ public class MapMatchingResourceTest {
         assertTrue(message.isValueNode());
         assertTrue(message.asText().startsWith("No tracks found"));
     }
+
+    private LineString readWktLineString(String wkt) {
+        WKTReader wktReader = new WKTReader();
+        LineString expectedGeometry = null;
+        try {
+            expectedGeometry = (LineString) wktReader.read(wkt);
+        } catch (ParseException e) {
+            e.printStackTrace();
+        }
+        return expectedGeometry;
+    }
+
 }
diff --git a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceProfileTest.java b/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTurnCostsTest.java
similarity index 81%
rename from web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceProfileTest.java
rename to web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTurnCostsTest.java
index 514706e31..4c64e66b0 100644
--- a/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceProfileTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/MapMatchingResourceTurnCostsTest.java
@@ -32,6 +32,10 @@ import org.junit.jupiter.api.AfterAll;
 import org.junit.jupiter.api.BeforeAll;
 import org.junit.jupiter.api.Test;
 import org.junit.jupiter.api.extension.ExtendWith;
+import org.locationtech.jts.algorithm.distance.DiscreteHausdorffDistance;
+import org.locationtech.jts.geom.LineString;
+import org.locationtech.jts.io.ParseException;
+import org.locationtech.jts.io.WKTReader;
 
 import javax.ws.rs.client.Entity;
 import javax.ws.rs.core.Response;
@@ -45,7 +49,7 @@ import static org.junit.Assert.*;
  * @author easbar
  */
 @ExtendWith(DropwizardExtensionsSupport.class)
-public class MapMatchingResourceProfileTest {
+public class MapMatchingResourceTurnCostsTest {
 
     private static final String DIR = "../target/mapmatchingtest";
     public static final DropwizardAppExtension<GraphHopperServerConfiguration> app = new DropwizardAppExtension<>(GraphHopperApplication.class, createConfig());
@@ -124,8 +128,9 @@ public class MapMatchingResourceProfileTest {
         assertEquals(200, response.getStatus());
         JsonNode path = json.get("paths").get(0);
 
-        assertEquals(5, path.get("instructions").size());
-        assertEquals(5, WebHelper.decodePolyline(path.get("points").asText(), 10, false).size());
+        LineString expectedGeometry = readWktLineString("LINESTRING (12.3607 51.34365, 12.36418 51.34443, 12.36379 51.34538, 12.36082 51.34471, 12.36188 51.34278)");
+        LineString actualGeometry = WebHelper.decodePolyline(path.get("points").asText(), 10, false).toLineString(false);
+        assertEquals(DiscreteHausdorffDistance.distance(expectedGeometry, actualGeometry), 0.0, 1E-4);
         assertEquals(106.15, path.get("time").asLong() / 1000f, 0.1);
         assertEquals(106.15, json.get("map_matching").get("time").asLong() / 1000f, 0.1);
         assertEquals(811.56, path.get("distance").asDouble(), 1);
@@ -142,12 +147,24 @@ public class MapMatchingResourceProfileTest {
         assertEquals(200, response.getStatus());
         JsonNode path = json.get("paths").get(0);
 
-        assertEquals(5, path.get("instructions").size());
-        assertEquals(5, WebHelper.decodePolyline(path.get("points").asText(), 10, false).size());
+        LineString expectedGeometry = readWktLineString("LINESTRING (12.3607 51.34365, 12.36418 51.34443, 12.36379 51.34538, 12.36082 51.34471, 12.36188 51.34278)");
+        LineString actualGeometry = WebHelper.decodePolyline(path.get("points").asText(), 10, false).toLineString(false);
+        assertEquals(DiscreteHausdorffDistance.distance(expectedGeometry, actualGeometry), 0.0, 1E-4);
         assertEquals(162.31, path.get("time").asLong() / 1000f, 0.1);
         assertEquals(162.31, json.get("map_matching").get("time").asLong() / 1000f, 0.1);
         assertEquals(811.56, path.get("distance").asDouble(), 1);
         assertEquals(811.56, json.get("map_matching").get("distance").asDouble(), 1);
     }
 
+    private LineString readWktLineString(String wkt) {
+        WKTReader wktReader = new WKTReader();
+        LineString expectedGeometry = null;
+        try {
+            expectedGeometry = (LineString) wktReader.read(wkt);
+        } catch (ParseException e) {
+            e.printStackTrace();
+        }
+        return expectedGeometry;
+    }
+
 }
diff --git a/web/src/test/java/com/graphhopper/http/resources/MvtResourceTest.java b/web/src/test/java/com/graphhopper/http/resources/MvtResourceTest.java
index cb9043dca..13333068a 100644
--- a/web/src/test/java/com/graphhopper/http/resources/MvtResourceTest.java
+++ b/web/src/test/java/com/graphhopper/http/resources/MvtResourceTest.java
@@ -86,7 +86,7 @@ public class MvtResourceTest {
         JtsLayer layer = layerValues.values().iterator().next();
         MultiLineString multiLineString = (MultiLineString) layer.getGeometries().iterator().next();
         assertEquals(42, multiLineString.getCoordinates().length);
-        Map map = (Map) multiLineString.getUserData();
+        Map map = attributes(multiLineString);
         assertEquals("Camì de les Pardines", map.get("name"));
     }
 
@@ -98,21 +98,17 @@ public class MvtResourceTest {
         JtsMvt result = MvtReader.loadMvt(is, new GeometryFactory(), new TagKeyValueMapConverter());
         final Map<String, JtsLayer> layerValues = result.getLayersByName();
         JtsLayer layer = layerValues.values().iterator().next();
-        List layerGeoList = (List) layer.getGeometries();
-        Geometry geometry = (Geometry) layerGeoList.get(0);
-        assertEquals(18, geometry.getCoordinates().length);
-        assertEquals(21, layerGeoList.size());
+        assertEquals(21, layer.getGeometries().size());
 
-        Map map = (Map) ((Geometry) layerGeoList.get(0)).getUserData();
-        assertTrue(Double.isInfinite((Double) map.get("max_speed")));
-        assertEquals("residential", map.get("road_class"));
-
-        map = (Map) ((Geometry) layerGeoList.get(1)).getUserData();
-        assertEquals(50, (Double) map.get("max_speed"), .1);
-        assertEquals("secondary", map.get("road_class"));
-        assertEquals("road", map.get("road_environment"));
+        Geometry geometry = layer.getGeometries().stream().
+                filter(g -> attributes(g).get("name").equals("Avinguda de Tarragona, CG-1"))
+                .findFirst().get();
+        assertEquals("road", attributes(geometry).get("road_environment"));
+        assertEquals(50.0, attributes(geometry).get("max_speed"));
+        assertEquals("primary", attributes(geometry).get("road_class"));
+    }
 
-        map = (Map) ((Geometry) layerGeoList.get(12)).getUserData();
-        assertEquals("bridge", map.get("road_environment"));
+    private Map<String, Object> attributes(Geometry g) {
+        return (Map<String, Object>) g.getUserData();
     }
 }