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

Fri Jul 24 22:36:43 BST 2009

Hi Johann,

it is actually not what it seems to be. The douglasPeucker function is  
called recursively. If the condition (maxDistance < allowedError) is  
fulfilled, the current part of the way can be reduced to a line (in  
case start- and endpoint are different points) or a point (in case  
start- and endpoint are the same). So the "if (ab == 0)  
points.remove(endIndex)" does not remove the endpoint of the whole  
polygon, but only prevents the polygon to have consecutive identical  
nodes if the original way has small "loops" in it. Wouldn't be that  
uncommon for contour lines btw. Closed polygons stay closed unless  
they are smaller than the allowedError, in which case they will reduce  
to a single point and will be dropped later anyway.

Some other observation about the DP code: I'm currently using the  
"Straight version" instead of the "Node version" and I think the maps  
look much nicer if zoomed out. I would recommend this as the standard  
setting. The problem of T-crossings not lining up isn't that  
prominent, because in resolution 24 the DP won't be applied at all and  
in the other resolutions it is not that much noticeable (for me at  
least).

Regards
Thilo

Am 24.07.2009 um 23:11 schrieb Johann Gail:

>
>
> 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);
>>             }
>>
>>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev