[OSM-dev] Garmin maps

[Richard Fairhurst]

Robert Hart wrote:

> I'm not sure that's the best way of creating simplified data. What
> matter more is how much a way, or other entity would deviate from it's
> original course if you skip out a certain node.

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).

It's an excellent algorithm: it can be computationally expensive, but  
in a tiles at home-type rendering project that shouldn't matter too much.

cheers
Richard

(I'll post a version of this to the wiki for future reference)