Douglas-Peucker

From OpenStreetMap Wiki
Jump to: navigation, search

Note: Should be just mentioned in articles about routing algorithms and wikipedia is made for explanations like this: http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm Kerosin 20:48, 3 October 2011 (BST)


The Douglas-Peucker algorithm is the accepted standard for simplifying polylines.

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 this distance is 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.

See also http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-133A.pdf (under "Method" on p2) for an explanation.

The processing can be computationally expensive, but in a tiles@home-type rendering project that shouldn't matter too much.