Douglas-Peucker Polygon Simplification

In Live Air Routing, polygons describing airspace boundaries, restricted zones, and weather cells are often produced from rasterized satellite data and contain far more vertices than necessary for routing computation. The Douglas-Peucker algorithm simplifies such a polyline (and by extension, a closed polygon) by discarding vertices whose perpendicular deviation from a chord falls below a chosen tolerance $\varepsilon.$

The basic subroutine is the perpendicular distance from a point $P=(x_0,y_0)$ to the line through $A=(x_1,y_1)$ and $B=(x_2,y_2){:}$

$$d = \dfrac{\big|(x_2-x_1)(y_1-y_0) - (x_1-x_0)(y_2-y_1)\big|}{\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}}.$$

The numerator is the magnitude of the 2D cross product $(B-A) \times (P-A),$ which equals twice the area of triangle $\triangle ABP.$ The denominator is the length of the chord $\overline{AB}.$

For example, with $A=(0,0),$ $B=(6,0),$ and $P=(2,3),$

$$\begin{align*} d &= \dfrac{|(6)(0-3) - (0-2)(0-0)|}{\sqrt{36 + 0}} \\[3pt] &= \dfrac{|{-18}|}{6} \\[3pt] &= 3. \end{align*}$$