Repository: graphhopper/graphhopper (java)

Issue:
Path simplification is very slow compared to routing
For example for 50 random locations in Germany `PathSimplification.simplify` takes about 80% of the time needed for calculating the route (`GraphHopper.route(request)` for node-based CH), something like: 600 of 720ms.
Apparently, for more locations this gets even worse, e.g. for 500 locations the path simplification takes 55s out of the 57s it takes to calculate the route (>95%). This is maybe expected, because for longer routes CH does not get so much slower, while the path contains a lot more points that need to be simplified.

I added a little measurement file in the `performance_via_routing` branch.

Pull request description:
Speed up path simplification with path details/instructions - fixed
This is a revised version of the previously reverted #1782 and should fix #1764.
When trying to update the navigation sdk it turned out the point lists for via- and finish instructions were empty after #1782, which makes problems for both navigation and map matching. For via- and finish-instructions the pointlists must contain a single point even though their `instruction.getLength()` is zero. I have now fixed this and navigation and map-matching tests are green with this change.



Patch:
diff --git a/api/src/main/java/com/graphhopper/util/PointList.java b/api/src/main/java/com/graphhopper/util/PointList.java
index 92b347dd2..08e5a1fd7 100644
--- a/api/src/main/java/com/graphhopper/util/PointList.java
+++ b/api/src/main/java/com/graphhopper/util/PointList.java
@@ -565,7 +565,7 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
             if (latlon.trim().length() == 0)
                 continue;
 
-            String ll[] = latlon.split(",");
+            String[] ll = latlon.split(",");
             String lat = ll[1].replace("]", "").trim();
             add(Double.parseDouble(lat), Double.parseDouble(ll[0].trim()), Double.NaN);
         }
diff --git a/core/src/main/java/com/graphhopper/util/DouglasPeucker.java b/core/src/main/java/com/graphhopper/util/DouglasPeucker.java
index b7b3aa2c2..c7acdfdc3 100644
--- a/core/src/main/java/com/graphhopper/util/DouglasPeucker.java
+++ b/core/src/main/java/com/graphhopper/util/DouglasPeucker.java
@@ -64,16 +64,22 @@ public class DouglasPeucker {
         return simplify(points, 0, points.size() - 1);
     }
 
+    public int simplify(PointList points, int fromIndex, int lastIndex) {
+        return simplify(points, fromIndex, lastIndex, true);
+    }
+
     /**
      * Simplifies a part of the <code>points</code>. The <code>fromIndex</code> and <code>lastIndex</code>
      * are guaranteed to be kept.
      *
      * @param points    The PointList to simplify
-     * @param fromIndex Start index to simplify, should be >= <code>lastIndex</code>
+     * @param fromIndex Start index to simplify, should be <= <code>lastIndex</code>
      * @param lastIndex Simplify up to this index
+     * @param compress  Whether or not the <code>points</code> shall be compressed or not, if set to false no points
+     *                  are actually removed, but instead their lat/lon/ele is only set to NaN
      * @return The number of removed points
      */
-    public int simplify(PointList points, int fromIndex, int lastIndex) {
+    public int simplify(PointList points, int fromIndex, int lastIndex, boolean compress) {
         int removed = 0;
         int size = lastIndex - fromIndex;
         if (approx) {
@@ -89,43 +95,12 @@ public class DouglasPeucker {
             removed = subSimplify(points, fromIndex, lastIndex);
         }
 
-        if (removed > 0)
-            compressNew(points, removed);
+        if (removed > 0 && compress)
+            removeNaN(points);
 
         return removed;
     }
 
-    /**
-     * compress list: move points into EMPTY slots
-     */
-    void compressNew(PointList points, int removed) {
-        int freeIndex = -1;
-        for (int currentIndex = 0; currentIndex < points.getSize(); currentIndex++) {
-            if (Double.isNaN(points.getLatitude(currentIndex))) {
-                if (freeIndex < 0)
-                    freeIndex = currentIndex;
-
-                continue;
-            } else if (freeIndex < 0) {
-                continue;
-            }
-
-            points.set(freeIndex, points.getLatitude(currentIndex), points.getLongitude(currentIndex), points.getElevation(currentIndex));
-            points.set(currentIndex, Double.NaN, Double.NaN, Double.NaN);
-            // find next free index
-            int max = currentIndex;
-            int searchIndex = freeIndex + 1;
-            freeIndex = currentIndex;
-            for (; searchIndex < max; searchIndex++) {
-                if (Double.isNaN(points.getLatitude(searchIndex))) {
-                    freeIndex = searchIndex;
-                    break;
-                }
-            }
-        }
-        points.trimToSize(points.getSize() - removed);
-    }
-
     // keep the points of fromIndex and lastIndex
     int subSimplify(PointList points, int fromIndex, int lastIndex) {
         if (lastIndex - fromIndex < 2) {
@@ -167,4 +142,18 @@ public class DouglasPeucker {
         return counter;
     }
 
+    /**
+     * Fills all entries of the point list that are NaN with the subsequent values (and therefore shortens the list)
+     */
+    static void removeNaN(PointList pointList) {
+        int curr = 0;
+        for (int i = 0; i < pointList.size(); i++) {
+            if (!Double.isNaN(pointList.getLatitude(i))) {
+                pointList.set(curr, pointList.getLatitude(i), pointList.getLongitude(i), pointList.getElevation(i));
+                curr++;
+            }
+        }
+        pointList.trimToSize(curr);
+    }
+
 }
diff --git a/core/src/main/java/com/graphhopper/util/PathMerger.java b/core/src/main/java/com/graphhopper/util/PathMerger.java
index cb0020f6c..4b1651b48 100644
--- a/core/src/main/java/com/graphhopper/util/PathMerger.java
+++ b/core/src/main/java/com/graphhopper/util/PathMerger.java
@@ -56,7 +56,7 @@ public class PathMerger {
     private DouglasPeucker douglasPeucker = DP;
     private boolean calcPoints = true;
     private PathDetailsBuilderFactory pathBuilderFactory;
-    private List<String> requestedPathDetails = Collections.EMPTY_LIST;
+    private List<String> requestedPathDetails = Collections.emptyList();
     private double favoredHeading = Double.NaN;
 
     public PathMerger(Graph graph, Weighting weighting) {
@@ -117,7 +117,7 @@ public class PathMerger {
                 if (!il.isEmpty()) {
                     fullInstructions.addAll(il);
 
-                    // for all paths except the last replace the FinishInstruction with a ViaInstructionn
+                    // for all paths except the last replace the FinishInstruction with a ViaInstruction
                     if (pathIndex + 1 < paths.size()) {
                         ViaInstruction newInstr = new ViaInstruction(fullInstructions.get(fullInstructions.size() - 1));
                         newInstr.setViaCount(pathIndex + 1);
@@ -167,8 +167,7 @@ public class PathMerger {
                 setTime(fullTimeInMillis);
 
         if (allFound && simplifyResponse && (calcPoints || enableInstructions)) {
-            PathSimplification ps = new PathSimplification(altRsp, douglasPeucker, enableInstructions);
-            ps.simplify();
+            PathSimplification.simplify(altRsp, douglasPeucker, enableInstructions);
         }
     }
 
diff --git a/core/src/main/java/com/graphhopper/util/PathSimplification.java b/core/src/main/java/com/graphhopper/util/PathSimplification.java
index b5f2cdad0..87db5a25b 100644
--- a/core/src/main/java/com/graphhopper/util/PathSimplification.java
+++ b/core/src/main/java/com/graphhopper/util/PathSimplification.java
@@ -25,117 +25,252 @@ import java.util.List;
 import java.util.Map;
 
 /**
- * This class simplifies the path, using {@link DouglasPeucker} and by considering the intervals
- * specified by <code>listsToSimplify</code>. We have to reference the points specified by the objects
- * in <code>listsToSimplify</code>. Therefore, we can only simplify in between these intervals, without
- * simplifying over one of the points, as it might get lost during the simplification
- * and we could not reference this point anymore.
+ * This class simplifies the path, using {@link DouglasPeucker}, but also considers a given list of partitions of
+ * the path. Each partition separates the points of the path into non-overlapping intervals and the simplification is
+ * done such that we never simplify across the boundaries of these intervals. This is important, because the points
+ * at the interval boundaries must not be removed, e.g. when they are referenced by instructions.
+ * For example for a path with twenty points and three partitions like this
+ * <p>
+ * - (0,1,2,3)(3,4)(4,4)(4,5,6,7)(7,8,9,10,11,12)(12,13,14,15,16)(17,18,19)
+ * - (0,1)(1,2,3,4)(4,5,6,7)(7,7)(8,9,10,11)(12,13,14,15)(16,17,18,19)
+ * - (0,1,2,3,4,5)(6,7,8,9,10,11,12,13,14),(14,15,16,17,18)(18,18)(18,19)
+ * <p>
+ * we run the simplification for the following intervals:
+ * <p>
+ * (0,1)(1,2,3)(3,4)(4,5)(5,6,7)(7,8,9,10,11)(11,12)(12,13,14)(14,15)(15,16)(16,17,18)(18,19)
  *
  * @author Robin Boldt
+ * @author easbar
  */
 public class PathSimplification {
 
-    private PointList pointList;
-    private Map<String, List<PathDetail>> pathDetails;
-    private List<List> listsToSimplify;
-    private DouglasPeucker douglasPeucker;
+    private final PointList pointList;
+    /**
+     * @see PathSimplification
+     */
+    private final List<Partition> partitions;
+    private final DouglasPeucker douglasPeucker;
 
-    public PathSimplification(PathWrapper pathWrapper, DouglasPeucker douglasPeucker, boolean enableInstructions) {
-        this.pointList = pathWrapper.getPoints();
-        listsToSimplify = new ArrayList<>();
-        if (enableInstructions)
-            listsToSimplify.add(pathWrapper.getInstructions());
+    // temporary variables used when traversing the different partitions
+    private final int numPartitions;
+    private final int[] currIntervalIndex;
+    private final int[] currIntervalStart;
+    private final int[] currIntervalEnd;
+    private final boolean[] partitionFinished;
+    // keep track of how many points were removed by Douglas-Peucker in the current and previous intervals
+    private final int[] removedPointsInCurrInterval;
+    private final int[] removedPointsInPrevIntervals;
 
-        this.pathDetails = pathWrapper.getPathDetails();
-        for (String name : pathDetails.keySet()) {
-            List<PathDetail> pathDetailList = pathDetails.get(name);
+    /**
+     * Convenience method used to obtain the partitions from a calculated path with details and instructions
+     */
+    public static PointList simplify(PathWrapper pathWrapper, DouglasPeucker douglasPeucker, boolean enableInstructions) {
+        final PointList pointList = pathWrapper.getPoints();
+        List<Partition> partitions = new ArrayList<>();
+        // todo: maybe this code can be simplified if path details and instructions would be merged, see #1121
+        if (enableInstructions) {
+            final InstructionList instructions = pathWrapper.getInstructions();
+            partitions.add(new Partition() {
+                @Override
+                public int size() {
+                    return instructions.size();
+                }
+
+                @Override
+                public int getIntervalLength(int index) {
+                    return instructions.get(index).getLength();
+                }
+
+                @Override
+                public void setInterval(int index, int start, int end) {
+                    Instruction instruction = instructions.get(index);
+                    if (instruction instanceof ViaInstruction || instruction instanceof FinishInstruction) {
+                        if (start != end) {
+                            throw new IllegalStateException("via- and finish-instructions are expected to have zero length");
+                        }
+                        // have to make sure that via instructions and finish instructions contain a single point
+                        // even though their 'instruction length' is zero.
+                        end++;
+                    }
+                    instruction.setPoints(pointList.shallowCopy(start, end, false));
+                }
+            });
+        }
+
+        for (final Map.Entry<String, List<PathDetail>> entry : pathWrapper.getPathDetails().entrySet()) {
             // If the pointList only contains one point, PathDetails have to be empty because 1 point => 0 edges
-            if (pathDetailList.isEmpty() && pointList.size() > 1)
-                throw new IllegalStateException("PathDetails " + name + " must not be empty");
+            final List<PathDetail> detail = entry.getValue();
+            if (detail.isEmpty() && pointList.size() > 1)
+                throw new IllegalStateException("PathDetails " + entry.getKey() + " must not be empty");
+
+            partitions.add(new Partition() {
+                @Override
+                public int size() {
+                    return detail.size();
+                }
+
+                @Override
+                public int getIntervalLength(int index) {
+                    return detail.get(index).getLength();
+                }
 
-            listsToSimplify.add(pathDetailList);
+                @Override
+                public void setInterval(int index, int start, int end) {
+                    PathDetail pd = detail.get(index);
+                    pd.setFirst(start);
+                    pd.setLast(end);
+                }
+            });
         }
+
+        simplify(pathWrapper.getPoints(), partitions, douglasPeucker);
+        assertConsistencyOfPathDetails(pathWrapper.getPathDetails());
+        assertConsistencyOfInstructions(pathWrapper.getInstructions(), pathWrapper.getPoints().size());
+        return pointList;
+    }
+
+    public static void simplify(PointList pointList, List<Partition> partitions, DouglasPeucker douglasPeucker) {
+        new PathSimplification(pointList, partitions, douglasPeucker).simplify();
+    }
+
+    private PathSimplification(PointList pointList, List<Partition> partitions, DouglasPeucker douglasPeucker) {
+        this.pointList = pointList;
+        this.partitions = partitions;
         this.douglasPeucker = douglasPeucker;
+        numPartitions = this.partitions.size();
+        currIntervalIndex = new int[numPartitions];
+        currIntervalStart = new int[numPartitions];
+        currIntervalEnd = new int[numPartitions];
+        partitionFinished = new boolean[numPartitions];
+        removedPointsInCurrInterval = new int[numPartitions];
+        removedPointsInPrevIntervals = new int[numPartitions];
     }
 
-    public PointList simplify() {
+    private void simplify() {
         if (pointList.size() <= 2) {
             pointList.makeImmutable();
-            return pointList;
+            return;
         }
 
-        // no constraints
-        if (listsToSimplify.isEmpty()) {
+        // no partitions -> no constraints, just simplify the entire point list
+        if (partitions.isEmpty()) {
             douglasPeucker.simplify(pointList, 0, pointList.size() - 1);
             pointList.makeImmutable();
-            return pointList;
+            return;
         }
 
-        // The offset of already included points
-        int[] offsets = new int[listsToSimplify.size()];
-        int[] endIntervals = new int[listsToSimplify.size()];
-        // All start at 0
-        int[] startIntervals = new int[listsToSimplify.size()];
-
-        while (true) {
-            boolean simplificationPossible = true;
-            int nonConflictingStart = 0;
-            int nonConflictingEnd = Integer.MAX_VALUE;
-            int listIndexToSimplify = -1;
-            int listIndexToShift = -1;
-
-            endIntervals = calculateEndIntervals(endIntervals, startIntervals, offsets, listsToSimplify);
-
-            // Find the intervals to run a simplification, if possible, and where to shift
-            for (int i = 0; i < listsToSimplify.size(); i++) {
-                if (startIntervals[i] >= nonConflictingEnd || endIntervals[i] <= nonConflictingStart) {
-                    simplificationPossible = false;
-                }
-                if (startIntervals[i] > nonConflictingStart) {
-                    listIndexToSimplify = -1;
-                    nonConflictingStart = startIntervals[i];
-                }
-                if (endIntervals[i] < nonConflictingEnd) {
-                    listIndexToSimplify = -1;
-                    nonConflictingEnd = endIntervals[i];
-                    // Remember the lowest endInterval
-                    listIndexToShift = i;
+        // Douglas-Peucker never removes the first/last point of a given interval, so as long as we only run it
+        // on each interval we can be sure that the interval boundaries will remain in the point list.
+        // Whenever we remove points from an interval we have to update the interval indices of all partitions.
+        // For example if an interval goes from point 4 to 9 and we remove points 5 and 7 we have to update the interval
+        // to [4,7].
+        // The basic idea to do this is as follows: We iterate through the point list and whenever we hit an interval
+        // end (q) in one of the partitions we run Douglas-Peucker for the interval [p,q], where p is the point where the
+        // last interval ended. We keep track of the number of removed points in the current and previous intervals
+        // to be able to calculate the updated indices.
+
+        // prepare for the first interval in each partition
+        int intervalStart = 0;
+        for (int i = 0; i < numPartitions; i++) {
+            currIntervalEnd[i] = this.partitions.get(i).getIntervalLength(currIntervalIndex[i]);
+        }
+
+        // iterate the point list and simplify and update the intervals on the go
+        for (int p = 0; p < pointList.size(); p++) {
+            int removed = 0;
+            // first we check if we hit the end of an interval for one of the partitions and run Douglas-Peucker if we do
+            for (int s = 0; s < numPartitions; s++) {
+                if (partitionFinished[s]) {
+                    continue;
                 }
-                if (startIntervals[i] >= nonConflictingStart && endIntervals[i] <= nonConflictingEnd) {
-                    listIndexToSimplify = i;
+                if (p == currIntervalEnd[s]) {
+                    // This is important for performance: we must not compress the point list after each call to
+                    // simplify, otherwise a lot of data is copied, especially for long routes (e.g. many via nodes),
+                    // see #1764. Note that since the point list does not get compressed here yet we have to keep track
+                    // of the total number of removed points to calculate the new interval boundaries later
+                    final boolean compress = false;
+                    removed = douglasPeucker.simplify(pointList, intervalStart, currIntervalEnd[s], compress);
+                    intervalStart = p;
+                    break;
                 }
             }
 
-            if (listIndexToSimplify >= 0 && simplificationPossible) {
-                // Only simplify if there is more than one point
-                if (nonConflictingEnd - nonConflictingStart > 1) {
-                    int removed = douglasPeucker.simplify(pointList, nonConflictingStart, nonConflictingEnd);
-                    if (removed > 0) {
-                        for (int i = 0; i < listsToSimplify.size(); i++) {
-                            List pathDetails = listsToSimplify.get(i);
-                            reduceLength(pathDetails, offsets[i], startIntervals[i], endIntervals[i] - removed);
-                            // This is not needed for Instructions, as they don't contain references, but PointLists
-                            if (pathDetails.get(0) instanceof PathDetail) {
-                                for (int j = offsets[i] + 1; j < pathDetails.size(); j++) {
-                                    PathDetail pd = (PathDetail) pathDetails.get(j);
-                                    reduceLength(pathDetails, j, pd.getFirst() - removed, pd.getLast() - removed);
-                                }
-                            }
-                        }
-                    }
+            // now we have (possibly) removed some points we need to update the current intervals in all partitions
+            for (int s = 0; s < numPartitions; s++) {
+                if (partitionFinished[s]) {
+                    continue;
                 }
+                removedPointsInCurrInterval[s] += removed;
+                // if the current interval of this partition ends at p, we update the interval boundaries. there is
+                // just a special catch: there can be multiple consecutive intervals that end with p, because there
+                // are intervals with a single point, for example p=3 and a partition=[0,3][3,3][3,3]
+                boolean nextIntervalHasOnlyOnePoint;
+                do {
+                    if (p == currIntervalEnd[s]) {
+                        nextIntervalHasOnlyOnePoint = updateInterval(p, s);
+                    } else {
+                        break;
+                    }
+                } while (nextIntervalHasOnlyOnePoint);
             }
+        }
+
+        // now we finally have to compress the pointList (actually remove the deleted points). note only after this
+        // call the (now shifted) indices in path details and instructions are correct
+        DouglasPeucker.removeNaN(pointList);
+
+        // Make sure that the instruction references are not broken
+        pointList.makeImmutable();
 
-            if (listIndexToShift < 0)
-                throw new IllegalStateException("toShiftIndex cannot be negative");
+        assertConsistencyOfIntervals();
+    }
+
+    /**
+     * @param p point index
+     * @param s partition index
+     */
+    private boolean updateInterval(int p, int s) {
+        boolean nextIntervalHasOnlyOnePoint = false;
+        // update interval boundaries
+        final int updatedStart = currIntervalStart[s] - removedPointsInPrevIntervals[s];
+        final int updatedEnd = currIntervalEnd[s] - removedPointsInPrevIntervals[s] - removedPointsInCurrInterval[s];
+        this.partitions.get(s).setInterval(currIntervalIndex[s], updatedStart, updatedEnd);
+
+        // update the removed point counters
+        removedPointsInPrevIntervals[s] += removedPointsInCurrInterval[s];
+        removedPointsInCurrInterval[s] = 0;
+
+        // prepare for the next interval
+        currIntervalIndex[s]++;
+        currIntervalStart[s] = p;
+        if (currIntervalIndex[s] >= this.partitions.get(s).size()) {
+            partitionFinished[s] = true;
+        } else {
+            int length = this.partitions.get(s).getIntervalLength(currIntervalIndex[s]);
+            currIntervalEnd[s] += length;
+            // special case at via points etc.
+            if (length == 0) {
+                nextIntervalHasOnlyOnePoint = true;
+            }
+        }
+        return nextIntervalHasOnlyOnePoint;
+    }
 
-            int length = getLength(listsToSimplify.get(listIndexToShift), offsets[listIndexToShift]);
-            startIntervals[listIndexToShift] += length;
-            offsets[listIndexToShift]++;
-            if (offsets[listIndexToShift] >= listsToSimplify.get(listIndexToShift).size())
-                break;
+    private void assertConsistencyOfIntervals() {
+        final int expected = pointList.size() - 1;
+        for (int i = 0; i < partitions.size(); i++) {
+            final Partition partition = partitions.get(i);
+            int count = 0;
+            for (int j = 0; j < partition.size(); j++) {
+                count += partition.getIntervalLength(j);
+            }
+            if (count != expected) {
+                throw new IllegalStateException("Simplified intervals are inconsistent: " + count + " vs. " + expected + " for intervals with index: " + i);
+            }
         }
+    }
 
+    private static void assertConsistencyOfPathDetails(Map<String, List<PathDetail>> pathDetails) {
         for (Map.Entry<String, List<PathDetail>> pdEntry : pathDetails.entrySet()) {
             List<PathDetail> list = pdEntry.getValue();
             if (list.isEmpty())
@@ -149,38 +284,35 @@ public class PathSimplification {
                 prevPD = list.get(i);
             }
         }
-        // Make sure that the instruction references are not broken
-        pointList.makeImmutable();
-        return pointList;
     }
 
-    private int getLength(Object o, int index) {
-        if (o instanceof InstructionList) {
-            return ((InstructionList) o).get(index).getLength();
+    private static void assertConsistencyOfInstructions(InstructionList instructions, int numPoints) {
+        // the total length of the instruction intervals must match the length of the point list.
+        // todo: it would be even better to make sure each instruction interval starts where the previous one ended, but
+        // currently instructions do not offer this
+        int expected = numPoints - 1;
+        int count = 0;
+        for (Instruction instruction : instructions) {
+            count += instruction.getLength();
         }
-        if (o instanceof List) {
-            return ((List<PathDetail>) o).get(index).getLength();
+        if (count != expected) {
+            throw new IllegalArgumentException("inconsistent instructions, total interval length: " + count + " vs. point list length " + expected);
         }
-        throw new IllegalStateException("We can only handle PathDetails or InstructionList in PathSimplification");
     }
 
-    private void reduceLength(Object o, int index, int startIndex, int newEndIndex) {
-        if (o instanceof InstructionList) {
-            ((InstructionList) o).get(index).setPoints(this.pointList.shallowCopy(startIndex, newEndIndex, false));
-        } else if (o instanceof List) {
-            PathDetail pd = ((List<PathDetail>) o).get(index);
-            pd.setFirst(startIndex);
-            pd.setLast(newEndIndex);
-        } else {
-            throw new IllegalStateException("We can only handle List<PathDetail> or InstructionList");
-        }
-    }
+    /**
+     * Represents a partition of a {@link PointList} into consecutive intervals, for example a list with six points
+     * can be partitioned into something like [0,2],[2,2],[2,3][3,5]. Note that intervals with a single point are
+     * allowed, but each interval must start where the previous one ended.
+     */
+    interface Partition {
+        int size();
 
-    private int[] calculateEndIntervals(int[] endIntervals, int[] startIntervals, int[] offset, List<List> toSimplify) {
-        for (int i = 0; i < toSimplify.size(); i++) {
-            endIntervals[i] = startIntervals[i] + getLength(toSimplify.get(i), offset[i]);
-        }
-        return endIntervals;
+        // todo: it would be nice to be able to retrieve the actual start and end of each interval to make the
+        // code here more straight-forward, but currently instructions only offer the length of the interval
+        int getIntervalLength(int index);
+
+        void setInterval(int index, int start, int end);
     }
 
 }


Test patch:
diff --git a/core/src/test/java/com/graphhopper/util/DouglasPeuckerTest.java b/core/src/test/java/com/graphhopper/util/DouglasPeuckerTest.java
index 1c059462d..cae31b382 100644
--- a/core/src/test/java/com/graphhopper/util/DouglasPeuckerTest.java
+++ b/core/src/test/java/com/graphhopper/util/DouglasPeuckerTest.java
@@ -19,6 +19,10 @@ package com.graphhopper.util;
 
 import org.junit.Test;
 
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 
@@ -29,13 +33,13 @@ public class DouglasPeuckerTest {
 
     // get some real life points from graphhopper API
     // http://217.92.216.224:8080/?point=49.945642,11.571436&point=49.946001,11.580706
-    String points1 = "[[11.571499218899739,49.945605917549265],[11.571664621792689,49.94570668665409],[11.571787742639804,49.94578156499077],[11.572065649302282,49.94590338198625],[11.572209445511016,49.94595944760649],[11.57229438213172,49.94598850487147],"
+    private final String points1 = "[[11.571499218899739,49.945605917549265],[11.571664621792689,49.94570668665409],[11.571787742639804,49.94578156499077],[11.572065649302282,49.94590338198625],[11.572209445511016,49.94595944760649],[11.57229438213172,49.94598850487147],"
             + "[11.573315297960832,49.946237913062525],[11.57367665112786,49.946338495902836],[11.573895511937787,49.94641784458796],[11.574013417378367,49.94646347939514],[11.574228180368875,49.94654916107392],[11.574703899950622,49.94677509993557],"
             + "[11.575003599561832,49.946924670344394],[11.575434615658997,49.94711838544425],[11.575559971680342,49.94716010869652],[11.57563783024932,49.947186185729194],[11.57609697228887,49.94727875919518],[11.57656188852851,49.947290121330845],"
             + "[11.576840167720023,49.94727782787258],[11.576961425921949,49.94725827009808],[11.577226852861648,49.947215242994176],[11.577394863457863,49.94717668623872],[11.577511092517772,49.94715005041249],[11.577635517216523,49.947112238715114],"
             + "[11.577917149169382,49.94702655703634],[11.577969116970207,49.947010724552214],[11.578816061738493,49.94673523932849],[11.579533552666014,49.94648974269233],[11.580073719771365,49.946299007824784],[11.580253092503245,49.946237913062525],"
             + "[11.580604946179799,49.94608871518274],[11.580740546749693,49.94603041438826]]";
-    String points2 = "[[9.961074440801317,50.203764443183644],[9.96106605889796,50.20365789987872],[9.960999562464645,50.20318963087774],[9.96094144793469,50.202952888673984],[9.96223002587773,50.20267889356641],[9.962200968612752,50.20262022024289],"
+    private final String points2 = "[[9.961074440801317,50.203764443183644],[9.96106605889796,50.20365789987872],[9.960999562464645,50.20318963087774],[9.96094144793469,50.202952888673984],[9.96223002587773,50.20267889356641],[9.962200968612752,50.20262022024289],"
             + "[9.961859918278305,50.201853928011374],[9.961668810881722,50.20138565901039],[9.96216874485095,50.20128507617008],[9.961953795595925,50.20088553877664],[9.961899033827313,50.200686794534775],[9.961716680863127,50.20014066696481],[9.961588158344957,50.199798499043254]]";
 
     @Test
@@ -96,4 +100,41 @@ public class DouglasPeuckerTest {
                         + "(50.20138565901039,9.961668810881722), (50.20128507617008,9.96216874485095), (50.20088553877664,9.961953795595925), (50.200686794534775,9.961899033827313), (50.20014066696481,9.961716680863127), (50.199798499043254,9.961588158344957)",
                 pointList.toString());
     }
+
+    @Test
+    public void testRemoveNaN() {
+        PointList pl = new PointList(10, true);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(1, 1, 1);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(5, 5, 5);
+        pl.add(6, 6, 6);
+        pl.add(7, 7, 7);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(8, 8, 8);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(9, 9, 9);
+        pl.add(10, 10, 10);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+        pl.add(14, 14, 14);
+        pl.add(Double.NaN, Double.NaN, Double.NaN);
+
+        DouglasPeucker.removeNaN(pl);
+        // doing it again should be no problem
+        DouglasPeucker.removeNaN(pl);
+        DouglasPeucker.removeNaN(pl);
+        assertEquals(8, pl.size());
+        List<Integer> expected = Arrays.asList(1, 5, 6, 7, 8, 9, 10, 14);
+        List<Integer> given = new ArrayList<>();
+        for (int i = 0; i < pl.size(); i++) {
+            assertEquals(pl.getLat(i), pl.getEle(i), 1.e-6);
+            assertEquals(pl.getLon(i), pl.getEle(i), 1.e-6);
+            given.add((int) pl.getLat(i));
+        }
+        assertEquals(expected, given);
+    }
 }
diff --git a/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java b/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
index b70bf55b1..be79d1ae3 100644
--- a/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
+++ b/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
@@ -38,10 +38,7 @@ import com.graphhopper.util.details.PathDetailsFromEdges;
 import org.junit.Before;
 import org.junit.Test;
 
-import java.util.Arrays;
-import java.util.List;
-import java.util.Locale;
-import java.util.Map;
+import java.util.*;
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
@@ -156,8 +153,7 @@ public class PathSimplificationTest {
         // Do not simplify anything
         douglasPeucker.setMaxDistance(0);
 
-        PathSimplification ps = new PathSimplification(pathWrapper, douglasPeucker, true);
-        ps.simplify();
+        PathSimplification.simplify(pathWrapper, douglasPeucker, true);
 
         assertEquals(numberOfPoints, pathWrapper.getPoints().size());
 
@@ -167,10 +163,214 @@ public class PathSimplificationTest {
         pathWrapper.setPoints(p.calcPoints());
 
         douglasPeucker.setMaxDistance(100000000);
-        ps = new PathSimplification(pathWrapper, douglasPeucker, true);
-        ps.simplify();
+        PathSimplification.simplify(pathWrapper, douglasPeucker, true);
 
         assertTrue(numberOfPoints > pathWrapper.getPoints().size());
     }
 
+    @Test
+    public void testSinglePartition() {
+        // points are chosen such that DP will remove those marked with an x
+        // todo: we could go further and replace DouglasPeucker with some abstract thing that makes this easier to test
+        PointList points = new PointList();
+        points.add(48.89107, 9.33161); // 0   -> 0
+        points.add(48.89104, 9.33102); // 1 x
+        points.add(48.89100, 9.33024); // 2 x
+        points.add(48.89099, 9.33002); // 3   -> 1
+        points.add(48.89092, 9.32853); // 4   -> 2
+        points.add(48.89101, 9.32854); // 5 x
+        points.add(48.89242, 9.32865); // 6   -> 3
+        points.add(48.89343, 9.32878); // 7   -> 4
+        PointList origPoints = points.clone(false);
+        TestPartition partition = TestPartition.start()
+                .add(0, 3)
+                .add(3, 3) // via
+                .add(3, 3) // via (just added this to make the test harder)
+                .add(3, 4)
+                .add(4, 4) // via
+                .add(4, 7)
+                .add(7, 7); // end
+        List<PathSimplification.Partition> partitions = new ArrayList<>();
+        partitions.add(partition);
+        PathSimplification.simplify(points, partitions, new DouglasPeucker());
+
+        // check points were modified correctly
+        assertEquals(5, points.size());
+        origPoints.set(1, Double.NaN, Double.NaN, Double.NaN);
+        origPoints.set(2, Double.NaN, Double.NaN, Double.NaN);
+        origPoints.set(5, Double.NaN, Double.NaN, Double.NaN);
+        DouglasPeucker.removeNaN(origPoints);
+        assertEquals(origPoints, points);
+
+        // check partition was modified correctly
+        TestPartition expected = TestPartition.start()
+                .add(0, 1)
+                .add(1, 1)
+                .add(1, 1)
+                .add(1, 2)
+                .add(2, 2)
+                .add(2, 4)
+                .add(4, 4);
+        assertEquals(expected.intervals, partition.intervals);
+    }
+
+    @Test
+    public void testMultiplePartitions() {
+        // points are chosen such that DP will remove those marked with an x
+        // got this data from running a request like this:
+        // http://localhost:8989/maps/?point=48.891273%2C9.325418&point=48.891005%2C9.322865&point=48.889877%2C9.32102&point=48.88975%2C9.31999&vehicle=car&weighting=fastest&elevation=true&debug=true&details=max_speed&details=street_name&
+        PointList points = new PointList(20, true);
+        points.add(48.89089, 9.32538, 270.0); // 0    -> 0
+        points.add(48.89090, 9.32527, 269.0); // 1 x
+        points.add(48.89091, 9.32439, 267.0); // 2 x
+        points.add(48.89091, 9.32403, 267.0); // 3    -> 1
+        points.add(48.89090, 9.32324, 267.0); // 4    -> 2
+        points.add(48.89088, 9.32296, 267.0); // 5 x
+        points.add(48.89088, 9.32288, 266.0); // 6    -> 3
+        points.add(48.89081, 9.32208, 265.0); // 7    -> 4
+        points.add(48.89056, 9.32217, 265.0); // 8    -> 5
+        points.add(48.89047, 9.32218, 265.0); // 9    -> 6
+        points.add(48.89037, 9.32215, 265.0); // 10   -> 7
+        points.add(48.89026, 9.32157, 265.0); // 11   -> 8
+        points.add(48.89023, 9.32101, 264.0); // 12   -> 9
+        points.add(48.89027, 9.32038, 261.0); // 13 x
+        points.add(48.89030, 9.32006, 261.0); // 14   -> 10
+        points.add(48.88989, 9.31965, 261.0); // 15   -> 11
+
+        PointList origPoints = points.clone(false);
+        // from instructions
+        TestPartition partition1 = TestPartition.start()
+                .add(0, 6)
+                .add(6, 6) // via
+                .add(6, 7)
+                .add(7, 10)
+                .add(10, 12)
+                .add(12, 12) // via
+                .add(12, 14)
+                .add(14, 15)
+                .add(15, 15); // end
+
+        // from max_speed detail
+        TestPartition partition2 = TestPartition.start()
+                .add(0, 3)
+                .add(3, 7)
+                .add(7, 15);
+
+        // from street_name detail
+        TestPartition partition3 = TestPartition.start()
+                .add(0, 7)
+                .add(7, 14)
+                .add(14, 15);
+
+        List<PathSimplification.Partition> partitions = new ArrayList<>();
+        partitions.add(partition1);
+        partitions.add(partition2);
+        partitions.add(partition3);
+        PathSimplification.simplify(points, partitions, new DouglasPeucker());
+
+        // check points were modified correctly
+        assertEquals(12, points.size());
+        origPoints.set(1, Double.NaN, Double.NaN, Double.NaN);
+        origPoints.set(2, Double.NaN, Double.NaN, Double.NaN);
+        origPoints.set(5, Double.NaN, Double.NaN, Double.NaN);
+        origPoints.set(13, Double.NaN, Double.NaN, Double.NaN);
+        DouglasPeucker.removeNaN(origPoints);
+        assertEquals(origPoints, points);
+
+        // check partitions were modified correctly
+        TestPartition expected1 = TestPartition.start()
+                .add(0, 3)
+                .add(3, 3) // via
+                .add(3, 4)
+                .add(4, 7)
+                .add(7, 9)
+                .add(9, 9) // via
+                .add(9, 10)
+                .add(10, 11)
+                .add(11, 11); // end
+
+        TestPartition expected2 = TestPartition.start()
+                .add(0, 1)
+                .add(1, 4)
+                .add(4, 11);
+
+        TestPartition expected3 = TestPartition.start()
+                .add(0, 4)
+                .add(4, 10)
+                .add(10, 11);
+
+        assertEquals(expected1.intervals, partition1.intervals);
+        assertEquals(expected2.intervals, partition2.intervals);
+        assertEquals(expected3.intervals, partition3.intervals);
+    }
+
+    static class TestPartition implements PathSimplification.Partition {
+        static Interval interval(int start, int end) {
+            return new Interval(start, end);
+        }
+
+        private List<Interval> intervals = new ArrayList<>();
+
+        private static TestPartition start() {
+            return new TestPartition();
+        }
+
+        private TestPartition add(int start, int end) {
+            intervals.add(interval(start, end));
+            return this;
+        }
+
+        @Override
+        public int size() {
+            return intervals.size();
+        }
+
+        @Override
+        public int getIntervalLength(int index) {
+            return intervals.get(index).length();
+        }
+
+        @Override
+        public void setInterval(int index, int start, int end) {
+            intervals.get(index).set(start, end);
+        }
+
+        static class Interval {
+            int start;
+            int end;
+
+            Interval(int start, int end) {
+                this.start = start;
+                this.end = end;
+            }
+
+            private int length() {
+                return end - start;
+            }
+
+            private void set(int start, int end) {
+                this.start = start;
+                this.end = end;
+            }
+
+            @Override
+            public boolean equals(Object o) {
+                if (this == o) return true;
+                if (o == null || getClass() != o.getClass()) return false;
+                Interval that = (Interval) o;
+                return start == that.start &&
+                        end == that.end;
+            }
+
+            @Override
+            public int hashCode() {
+                return Objects.hash(start, end);
+            }
+
+            @Override
+            public String toString() {
+                return "[" + start + ", " + end + "]";
+            }
+        }
+    }
 }
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
index e6e341e3a..0ca83d251 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperIT.java
@@ -1455,7 +1455,7 @@ public class GraphHopperIT {
         PathWrapper path = rsp.getBest();
 
         // check path was simplified (without it would be more like 58)
-        assertEquals(47, path.getPoints().size());
+        assertEquals(44, path.getPoints().size());
 
         // check instructions
         InstructionList instructions = path.getInstructions();
@@ -1463,42 +1463,42 @@ public class GraphHopperIT {
         for (Instruction instruction : instructions) {
             totalLength += instruction.getLength();
         }
-        assertEquals(46, totalLength);
+        assertEquals(43, totalLength);
         assertInstruction(instructions.get(0), "KU 11", "[0, 4[", 4, 4);
-        assertInstruction(instructions.get(1), "B 85", "[4, 20[", 16, 16);
-        assertInstruction(instructions.get(2), "", "[20, 20[", 0, 1);
-        assertInstruction(instructions.get(3), "B 85", "[20, 38[", 18, 18);
-        assertInstruction(instructions.get(4), "", "[38, 40[", 2, 2);
-        assertInstruction(instructions.get(5), "KU 18", "[40, 43[", 3, 3);
-        assertInstruction(instructions.get(6), "St 2189", "[43, 44[", 1, 1);
-        assertInstruction(instructions.get(7), "", "[44, 46[", 2, 2);
-        assertInstruction(instructions.get(8), "", "[46, 46[", 0, 1);
+        assertInstruction(instructions.get(1), "B 85", "[4, 18[", 14, 14);
+        // via instructions have length = 0, but the point list must not be empty!
+        assertInstruction(instructions.get(2), "", "[18, 19[", 0, 1);
+        assertInstruction(instructions.get(3), "B 85", "[18, 35[", 17, 17);
+        assertInstruction(instructions.get(4), "", "[35, 37[", 2, 2);
+        assertInstruction(instructions.get(5), "KU 18", "[37, 40[", 3, 3);
+        assertInstruction(instructions.get(6), "St 2189", "[40, 41[", 1, 1);
+        assertInstruction(instructions.get(7), "", "[41, 43[", 2, 2);
+        // finish instructions have length = 0, but the point list must not be empty!
+        assertInstruction(instructions.get(8), "", "[43, 44[", 0, 1);
 
         // check max speeds
         List<PathDetail> speeds = path.getPathDetails().get("max_speed");
         assertDetail(speeds.get(0), "null [0, 4]");
         assertDetail(speeds.get(1), "70.0 [4, 7]");
-        assertDetail(speeds.get(2), "100.0 [7, 37]");
-        assertDetail(speeds.get(3), "80.0 [37, 38]");
-        assertDetail(speeds.get(4), "null [38, 43]");
-        assertDetail(speeds.get(5), "50.0 [43, 44]");
-        assertDetail(speeds.get(6), "null [44, 46]");
+        assertDetail(speeds.get(2), "100.0 [7, 34]");
+        assertDetail(speeds.get(3), "80.0 [34, 35]");
+        assertDetail(speeds.get(4), "null [35, 40]");
+        assertDetail(speeds.get(5), "50.0 [40, 41]");
+        assertDetail(speeds.get(6), "null [41, 43]");
 
         // check street_names
         List<PathDetail> streetNames = path.getPathDetails().get("street_name");
         assertDetail(streetNames.get(0), "KU 11 [0, 4]");
-        assertDetail(streetNames.get(1), "B 85 [4, 38]");
-        assertDetail(streetNames.get(2), " [38, 40]");
-        assertDetail(streetNames.get(3), "KU 18 [40, 43]");
-        assertDetail(streetNames.get(4), "St 2189 [43, 44]");
-        assertDetail(streetNames.get(5), " [44, 46]");
+        assertDetail(streetNames.get(1), "B 85 [4, 35]");
+        assertDetail(streetNames.get(2), " [35, 37]");
+        assertDetail(streetNames.get(3), "KU 18 [37, 40]");
+        assertDetail(streetNames.get(4), "St 2189 [40, 41]");
+        assertDetail(streetNames.get(5), " [41, 43]");
     }
 
     private void assertInstruction(Instruction instruction, String expectedName, String expectedInterval, int expectedLength, int expectedPoints) {
         assertEquals(expectedName, instruction.getName());
-        if (instruction.getPoints() instanceof ShallowImmutablePointList) {
-            assertEquals(expectedInterval, ((ShallowImmutablePointList) instruction.getPoints()).getIntervalString());
-        }
+        assertEquals(expectedInterval, ((ShallowImmutablePointList) instruction.getPoints()).getIntervalString());
         assertEquals(expectedLength, instruction.getLength());
         assertEquals(expectedPoints, instruction.getPoints().size());
     }