PhpRiot
Become Zend Certified

Prepare for the ZCE exam using our quizzes (web or iPad/iPhone). More info...


When you're ready get 7.5% off your exam voucher using voucher CJQNOV23 at the Zend Store

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

In This Article


Additional Files