Reducing a Map Path Using Douglas-Peucker Algorithm
The Douglas-Peucker Algorithm
The Douglas-Peucker algorithm is used to reduce the number of points in a line. It does so by discarding points that do not deviate significantly between its surrounding points.
The amount a point may deviate before it is excluded is an input to the algorithm, and naturally will impact the number of points that are excluded.
The algorithm works as follows:
- Begin with the first and last points in the path (let's call them
Brespectively). These are always kept.
- Find the point between the first and last that is furthest away from the line joining the first and last line (the orthogonal distance).
- If this point is greater than the allowed tolerance, this point is kept (let's called it
- Repeat this algorithm twice: once using
Aas the first point and
Xas the last point, the other time using
Xas the first point and
Bas the last point.
This algorithm is recursive, and continues until all points have been checked.
In the next section we'll implement the Douglas-Peucker algorithm in PHP.