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

Phát biểu bài toán

Cho đường polyline 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 $\delta > 0$.

Ta định nghĩa hàm $fReduce(points, start,end,\delta)$là hàm lược bỏ các điểm trong tập điểm $points$ từ index $start$ đến $end$ như sau:

• Cho $i$ lần lượt nhận giá trị $start + 1$ từ đến $end-1$:

• Tính $d_i = d(P_i, \overline{P_{start}P_{end}})$, với:

  • $\overline{P_{start}P_{end}}$ là đoạn thẳng nối $P_{start}$ và $P_{end}$

  • Hàm $d(P_i, \overline{P_iP_j})$ là hàm đo khoảng cách từ điểm $P_i$ đến $\overline{P_iP_j}$

• Tìm $d_{max} = \max d(P_i,\overline{P_{start}P_{end}})$

• Nếu $d_{max} \le \delta$: tất cả các điểm từ đến đều có thể lược bỏ

• Nếu $d_{max} > \delta$ 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:

  • $fReduce(points, start,k,\delta)$

  • $fReduce(points, k, end,\delta)$

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

Tính khoảng cách từ một điểm đến đường thẳng

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

Ta có: $\displaystyle S_{ABC} = \frac {AH \times BC} {2} \implies AH = \frac {2 \times S_{ABC}} {BC}$

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

Với $\theta$ là góc tạo bởi vector $\overrightarrow{AB}, \overrightarrow{AC}$

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