# Visvalingam–Whyatt algorithm

The Visvalingam–Whyatt algorithm, also known as the Visvalingam's algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points.

## Idea

Given a polygonal chain (often called a Polyline), the algorithm attempts to find a similar chain composed of fewer points.

Points are assigned an importance based on local conditions, and points are removed from the least important to most important.

In Visvalingam's algorithm, the importance is related to the triangular area added by each point.

## Algorithm

Given a chain of 2d points $\left\{p_{i}\right\}=\left\{{\begin{bmatrix}x_{i}\\y_{i}\end{bmatrix}}\right\}$ , the importance of each interior point is computed by finding the area of the triangle formed by it and its immediate neighbors. This can be done quickly using a matrix determinant. Alternatively, the equivalent formula below can be used

$A_{i}={\frac {1}{2}}\left|x_{i-1}y_{i}+x_{i}y_{i+1}+x_{i+1}y_{i-1}-x_{i-1}y_{i+1}-x_{i}y_{i-1}-x_{i+1}y_{i}\right|$ The minimum importance point $p_{i}$ is located and marked for removal (note that $A_{i-1}$ and $A_{i+1}$ will need to be recomputed). This process is repeated until either the desired number of points is reached, or the contribution of the least important point is small enough to neglect.