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

Fri Jul 24 22:11:09 BST 2009

Thilo Hannemann schrieb:
> 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.
>
Hi Thilo,

I was just trying to get your patch working and would like to test it 
afterwards.
In general I find it a good one.
But I'm not sure about the last lines of your patch. If you delete the 
endpoint in case of ab==0 then you introduce the original problem again. 
The problem was polygons loosing their start or endpoints.

What are your thoughts about it?

Greetings,
Johann

> @@ -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);
>              }
>
>