Ramer Douglas Peuker point reduction algorithm

💡

Let C be a path created by a set of consecutive line segments of a set of points. Given a certain error rate, reduce the number of points in this set so that the shape of the original path C is still maintained.

This algorithm is also known as Ramer–Douglas–Peucker. The algorithm was developed independently by Urs Ramer in 1972 and by David Douglas and Thomas Peucker in 1973.

Algorithm

Given $C$ be a path by set of $n $ ordered points:

$C=\{P_1,P_2,\dots,P_n\}$ and an tolerance rate $\delta > 0$

We define function $fReduce(points, start,end,\delta)$ is the function to reduce points in $points$ from $start$ index to $end$ index as following:

Let $i=[(start+1) \dots (end-1)]$
Calculate $d_i = d(P_i, \overline{P_{start}P_{end}})$ inwhich:
- $\overline{P_{start}P_{end}}$ is the line segment that connects $P_{start}$ and $P_{end}$
- function $d(P_i, \overline{P_iP_j})$ is the function to measure the Euclidean distance from $P_i$ to $\overline{P_iP_j}$
Find $d_{max} = \max d(P_i,\overline{P_{start}P_{end}})$
If $d_{max} \le \delta$: remove all points $[P_{start+1} \dots P_{end-1}]$
If $d_{max} > \delta$ at the $k^{th}$ index, we split the $points$ at $k$ and makes 2 recursive calls:
- $fReduce(points, start,k,\delta)$
- $fReduce(points, k, end,\delta)$

Illustration

Source Code

// pointIndices is the array to store points after reduction process
function fReduce(points, firstPoint, lastPoint, tolerance, pointIndices){
    let maxD = 0;
    let indexFurthest = 0;

    for (let i=firstPoint + 1; i< lastPoint - 1; i++){
        let distance = dPointLine(points[i], points[firstPoint], points[lastPoint]);
        if (distance > maxD){
            maxD = distance;
            // lưu index của điểm xa nhất 
            indexFurthest = i;
        }
    }

    if ((maxD > tolerance) && (indexFurthest != 0)){
        pointIndices.push(indexFurthest);
        // recursive calls
        fReduce(points, firstPoint, indexFurthest, tolerance, pointIndices)
        fReduce(points, indexFurthest, lastPoint, tolerance, pointIndices)
    }
}

Calculate distance from a point to a line

Distance from $A$ to $BC$ is the length of $AH$. Knowing:

$$\displaystyle S_{ABC} = \frac {AH \times BC} {2} \implies AH = \frac {2 \times S_{ABC}} {BC}$$

$S_{ABC}$ can be calculated by the cross product of those vectors $\overrightarrow{AB}$ and $\overrightarrow{AC}$:

$$\displaystyle 2 \times S_{ABC} = |\overrightarrow{AB}||\overrightarrow{AC}||\sin \theta|=|\overrightarrow{AB} \times \overrightarrow{AC}| \implies AH = \frac {|\overrightarrow{AB} \times \overrightarrow{AC}|} 2$$

With $\theta$ is the angle by $\overrightarrow{AB}$ and $\overrightarrow{AC}$.

Souce code

// calculate distance from point p1 to line p2p3
function dPointLine(p1, p2, p3){
    let area = Math.abs(0.5 * (p2.x * p3.y + p3.x * p1.y + p1.x * p2.y - p3.x * p2.y - p1.x * p3.y - p2.x * p1.y))    

    let bottom = p2.dist(p3);
    let height = area / bottom * 2.0;

    return height;
}

Point reduction algorithm Ramer - Douglas - Peuker

Algorithm

Calculate distance from a point to a line