[mkgmap-dev] Putting the DP code under the microscope

Wed Jun 17 21:15:40 BST 2009

Here is another approach to the "lost last point". The Douglas Peucker  
filter is improved so that it can deal with identical start- and  
endpoints. If the start- and the endpoint are identical, the algorithm  
calculates the distance between these identical points and the point  
p. So the polygon is not split at point N/2, but at the point that has  
the greatest distance from the start-/endpoint.

Dealing with the problem in the Douglas Peucker algorithm itself has  
the advantage that it will also work for a pathological polygon or way  
that has identical, non-consecutive points in the middle of it.

Index: src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java
===================================================================

--- src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java	 
(revision 1067)
+++ src/uk/me/parabola/mkgmap/filters/DouglasPeuckerFilter.java	 
(working copy)
@@ -60,20 +60,11 @@

  		MapLine line = (MapLine) element;

+		// Create a new list to rewrite the points into. Don't alter the  
original one
  		List<Coord> points = line.getPoints();
-		int n = points.size()-1;
-
-		// Create a new list to rewrite the points into. Don't alter the  
original one
-		List<Coord> coords = new ArrayList<Coord>(n);
+		List<Coord> coords = new ArrayList<Coord>(points.size());
  		coords.addAll(points);

-		// If the first point is identic with the last one (a polygon),  
drop it
-		// Otherwise douglasPeucker will not work!
-		while ((n > 0) && coords.get(0).equals(coords.get(n))) {
-			coords.remove(n);
-			n--;
-		}
-
  //#if (Node version)
  //Dont touch Coords, which are nodes.
  //So points at croosings will not be moved
@@ -129,18 +120,33 @@
  		Coord b = points.get(endIndex);
  		double ab = a.distance(b);

-		// Find point with highest distance.
-		for(int i = endIndex-1; i > startIndex; i--) {
-			Coord p = points.get(i);
-			double ap = p.distance(a);
-			double bp = p.distance(b);
-			double abpa = (ab+ap+bp)/2;
-			double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) *  
(abpa-bp)) / ab;
-			if (distance > maxDistance) {
-				maxDistance = distance;
-				maxIndex = i;
+		if (ab == 0) { // Start- and endpoint are the same
+			// Find point with highest distance to start- and endpoint
+			for (int i = endIndex-1; i > startIndex; i--) {
+				Coord p = points.get(i);
+				double distance = p.distance(a);
+				if (distance > maxDistance) {
+					maxDistance = distance;
+					maxIndex = i;
+				}
  			}
+		} else {
+			// Find point with highest distance to line between start- and  
endpoint
+			for(int i = endIndex-1; i > startIndex; i--) {
+				// Calculate the area of the triangle a-b-p using Heron's  
formular. The height of
+				// that triangle is the distance we look for.
+				Coord p = points.get(i);
+				double ap = p.distance(a);
+				double bp = p.distance(b);
+				double abpa = (ab+ap+bp)/2;
+				double distance = 2 * Math.sqrt(abpa * (abpa-ab) * (abpa-ap) *  
(abpa-bp)) / ab;
+				if (distance > maxDistance) {
+					maxDistance = distance;
+					maxIndex = i;
+				}
+			}
  		}
+
  		if (maxDistance > allowedError) {
  			// Call recursive for both parts
  			douglasPeucker(points, maxIndex, endIndex, allowedError);		
@@ -148,6 +154,12 @@
  		}
  		else {
  			// All points in tolerance, delete all of them.
+
+			// Remove the endpoint if it is the same as the startpoint
+			if (ab == 0)
+				points.remove(endIndex);
+	
+			// Remove the points in between
  			for(int i = endIndex-1; i > startIndex; i--) {
  				points.remove(i);
  			}


