# [OSM-dev] Garmin maps

Robert Hart Robert.Hart at BuroHappold.com
Thu Feb 15 11:01:29 GMT 2007

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

Rob

This message has been scanned for viruses by MailControl - www.mailcontrol.com

```