The 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 A and B respectively). 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 X).
• Repeat this algorithm twice: once using A as the first point and X as the last point, the other time using X as the first point and B as the last point.

This algorithm is recursive, and continues until all points have been checked.

Figure 3 Finding the point with the greatest orthogonal distance between the first and last points

In the next section we'll implement the Douglas-Peucker algorithm in PHP.

• Next: Implementing Douglas-Peucker In PHP: Part 1