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

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