|It has been proposed that this page be deleted or replaced by a redirect. See the discussion page for further information.|
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:
- Take the polyline A-C.
- Find the point that is the greatest distance from the line. Call it B.
- If this distance is less than the tolerance, then accept A-C as the simplified line.
- Otherwise, repeat the whole process recursively for A-B and B-C.
- 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.