Point reduction algorithm Ramer - Douglas - Peuker

Point reduction algorithm Ramer – Douglas – Peuker

💡 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 $δ > 0$

We define function $f R e d u c e (p o i n t s, s t a r t, e n d, δ)$ is the function to reduce points in $p o i n t s$ from $s t a r t$ index to $e n d$ index as following:

Let $i = [(s t a r t + 1) \dots (e n d - 1)]$
Calculate $d_{i} = d (P_{i}, \overset{―}{P_{s t a r t} P_{e n d}})$ inwhich:
- $\overset{―}{P_{s t a r t} P_{e n d}}$ is the line segment that connects $P_{s t a r t}$ and $P_{e n d}$
- function $d (P_{i}, \overset{―}{P_{i} P_{j}})$ is the function to measure the Euclidean distance from $P_{i}$ to $\overset{―}{P_{i} P_{j}}$
Find $d_{m a x} = max d (P_{i}, \overset{―}{P_{s t a r t} P_{e n d}})$
If $d_{m a x} \leq δ$ : remove all points $[P_{s t a r t + 1} \dots P_{e n d - 1}]$
If $d_{m a x} > δ$ at the $k^{t h}$ index, we split the $p o i n t s$ at $k$ and makes 2 recursive calls:
- $f R e d u c e (p o i n t s, s t a r t, k, δ)$
- $f R e d u c e (p o i n t s, k, e n d, δ)$

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 $B C$ is the length of $A H$ . Knowing:

$S_{A B C} = \frac{A H \times B C}{2} ⟹ A H = \frac{2 \times S_{A B C}}{B C}$

$S_{A B C}$ can be calculated by the cross product of those vectors $\vec{A B}$ and $\vec{A C}$ :

$2 \times S_{A B C} = | \vec{A B} | | \vec{A C} | | \sin θ | = | \vec{A B} \times \vec{A C} | ⟹ A H = \frac{| \vec{A B} \times \vec{A C} |}{2}$

With $θ$ is the angle by $\vec{A B}$ and $\vec{A C}$ .

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;
}