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: 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 (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.