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

[Martijn van Oosterhout]

On 2/15/07, Robert (Jamie) Munro <rjmunro at arjam.net> wrote:
> 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.

To be honest, I don't think you need to worry about the complex case
too much. What I'd do is start with m=n and remove the point that adds
the least area. Repeat until the area gets too large. You could progam
ths in linear time.

Adding your example of merging two points may work nicer also, but
even then it's not too much computation. There may be pathlogical
cases where it won't work, but it should be close for most realistic
uses.

Have a nice day,
-- 
Martijn van Oosterhout <kleptog at gmail.com> http://svana.org/kleptog/