Thuật toán rút gọn số điểm trên đường cong Douglas-Peuker

💡 Cho đường C được tạo bởi tập hợp các đoạn thẳng nối tiếp nhau của một tập hợp điểm. Cho trước một độ error rate nhất định, rút gọn số lượng điểm của tập hợp này sao cho vẫn giữ được hình dạng của đường C ban đầu.

Thuật toán này còn được biết đến với tên là Ramer–Douglas–Peucker.Thuật toán được phát triển độc lập bởi Urs Ramer vào năm 1972 và bởi David Douglas và Thomas Peucker vào năm 1973.

Thuật toán

Cho đường $C$ dưới dạng tập hợp của $n$ điểm sắp xếp thứ tự:

$C = (P_{1}, P_{2}, \dots, P_{n})$ và một giá trị độ sai $δ > 0$ .

Ta định nghĩa hàm $f R e d u c e (p o i n t s, s t a r t, e n d, δ)$ là hàm lược bỏ các điểm trong tập điểm $p o i n t s$ từ index $s t a r t$ đến $e n d$ như sau:

Cho $i$ lần lượt nhận giá trị từ $s t a r t + 1$ đến $e n d - 1$ :
Tính $d_{i} = d (P_{i}, \overset{―}{P_{s t a r t} P_{e n d}})$ , với:
- $\overset{―}{P_{s t a r t} P_{e n d}}$ là đoạn thẳng nối $P_{s t a r t}$ và $P_{e n d}$
- hàm $d (P_{i}, \overset{―}{P_{i} P_{j}})$ là hàm đo khoảng cách từ điểm $P_{i}$ đến $\overset{―}{P_{i} P_{j}}$
Tìm $d_{m a x} = max d (P_{i}, \overset{―}{P_{s t a r t} P_{e n d}})$
Nếu $d_{m a x} \leq δ$ : tất cả các điểm từ $P_{s t a r t + 1}$ đến $P_{e n d - 1}$ đều có thể lược bỏ

Nếu $d_{m a x} > δ$ tại index thứ $k$ , ta chia đoạn thẳng thành 2 phần để thực hiện gọi đệ quy như sau:

$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, δ)$

Minh họa

Source code

				
					// pointIndices là mảng để lưu trữ các index được giữ lại sau quá trình thu gọn
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;
        }
    }

    // tolerance là giá trị delta
    if ((maxD > tolerance) && (indexFurthest != 0)){
        pointIndices.push(indexFurthest);
        fReduce(points, firstPoint, indexFurthest, tolerance, pointIndices)
        fReduce(points, indexFurthest, lastPoint, tolerance, pointIndices)
    }
}

Thuật toán tính khoảng cách điểm đến đường thẳng

Khoảng cách từ điểm $A$ đến đoạn $B C$ là chiều dài đoạn $A H$ .

Ta có: $S_{A B C} = \frac{A H \times B C}{2} ⟹ A H = \frac{2 \times S_{A B C}}{B C}$

Tuy nhiên, $S_{A B C}$ có thể được tính bởi công thức cross product của vector $\vec{A B}$ và $\vec{A C}$ như sau:

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

Với $θ$ là góc tạo bởi vector $\vec{A B}$ và $\vec{A C}$ .

Source code

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