[OSM-dev] Way simplification (was Re: Garmin maps)

Robert (Jamie) Munro rjmunro at arjam.net
Thu Feb 15 12:55:48 GMT 2007


Robert Hart wrote:
>> The standard way of simplifying a polyline is the Douglas-Peucker
>> algorithm. Given a maximum tolerance, it works like this:
>>
>> 1. Take the polyline A-C.
>> 2. Find the point that is the greatest distance from the line. Call it
> B.
>> 3. If it's less than the tolerance, then accept A-C as the simplified
>> line.
>> 4. Otherwise, repeat the whole process recursively for A-B and B-C.
>> 5. Continue until either all segments are either within the tolerance,
>> or consist solely of one line.
>>
>> http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-133A.pdf is quite
>> a decent explanation (under "Method" on p2).
> 
> Thanks for the reference. I'll have a read. That's pretty much what I
> described though.
> 
> It does strike me that a common case in OSM is long straight bits with
> rounded corners. That algorithm would prefer picking the mid-point of
> the curved bit as the point to keep, whereas a human would either pick
> the start and end points of the curve, or project the long straight bits
> to find their apparent intersection - resulting in a point not on the
> original polyline.

What you want to do is find one node which minimises the total area (A)
enclosed between the simplified way and the original way. I've attached
a diagram (if this list strips attachments, I'll upload it to
http://arjam.net/diagram.png). The original line is ABCD. The simplified
one is AED. The idea is to place E where it minimises A (the black
area). I don't have time to figure out the formula now, but I don't
expect it will be too hard in this simple case. Generalising it to
reduce a way of n points to m points where m<n will probably be hard.
Finding m such that A<[some maximum acceptable amount] will probably
require just trying lots of values of m, which might be very
computationally expensive.

Robert (Jamie) Munro
-------------- next part --------------
A non-text attachment was scrubbed...
Name: diagram.PNG
Type: image/png
Size: 3912 bytes
Desc: not available
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20070215/e78c93ac/attachment.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 249 bytes
Desc: OpenPGP digital signature
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20070215/e78c93ac/attachment.pgp>


More information about the dev mailing list