Thuật toán khớp đường cong bằng các đường Bézier

Tư tưởng chính của thuật toán

Bước 1: Với tập hợp điểm \(points=\{(x_1,y_1), (x_2,y_2),\dots, (x_n,y_n)\}\), sinh ra một đường cong Bezier \(C\) với các thông số \(\hat{t_1},\hat{t_2},\varepsilon \) lần lượt là tiếp tuyến bên trái, tiếp tuyến bên phải, và độ sai lệch cho phép
Bước 2: Tính giá trị \(\text{error}\) là sai số của đường cong \(C\) khi khớp với tập điểm \(points\).
- Nếu \(\text{error} < \varepsilon\), ngừng thuật toán, \(C \) chính là đường cong cần tìm
- Nếu không, ta chia tập điểm \(points\) thành 2 phần tại điểm có khoảng cách xa nhất so với \(C\), tạm gọi là điểm \(M(x_M,y_M)\) rồi áp dụng gọi đệ quy cho 2 tập điểm mới: \([(x_1,y_1) \dots (x_M, y_M)]\) và \([(x_M, y_M) \dots (x_n,y_n)]\) để tiếp tục tìm đường cong \(C_1, C_2\) để khớp với 2 tập điểm mới.

Một số điểm nhấn của thuật toán

Để tiện cho việc tính toán, ta dùng công thức tính đường cong với tham số \(t\):

\(Q(t) = \sum_{i=0}^nV_iB_i^n(t), \quad t \in [0,1]\)
Đối với đường cong Bezier bậc 3 với control points \(P_1, P_2,P_3,P_4\) thì tiếp tuyến của đường cong tại các điểm đầu mút \(P_1\)và \(P_4\) nằm trên đường thẳng chứa đoạn \(P_1P_2\)và đường thẳng chứa đoạn \(P_3P_4\). Điều này được thể hiện qua công thức:

\(\displaystyle \frac {dQ}{dt} = Q^{\prime}(t)=n\sum_{i=0}^{n-1}(V_{i+1} - V_i)B_i^{n-1}(t)\)

Như vậy, ta có thể biểu diễn \(P_2=\alpha_1\hat{t_1}+P_1\) và \(P_3=\alpha_2\hat{t_2}+P_4\) với \(\hat{t_1}, \hat{t_2}\) lần lượt các các vector tiếp tuyến tại \(P_1\) và \(P_4\)
Như vậy việc khớp đường cong với một tập điểm thực chất là ta đi kiếm giá trị phù hợp của \(\alpha_1, \alpha_2\). Chi tiết để tính toán đã được mô tả khá kỹ trong paper từ trang 618 đến trang 620 nên mình không viết lại nữa. Implementation của phần này nằm trong function generateBezier, bạn có thể tham khảo trong phần source code.
Việc còn lại là cần tính khoảng cách từ 1 điểm \(P\) đến đường cong \(C\), với phương trình tham số \(Q(t)\):

Mình mượn lại hình vẽ trong bài báo. Như vậy để tính khoảng cách từ \(P\) đến \(Q(t)\)nghĩa là chúng ta cần tính \(dist = ||P-Q(t)||\). Như vậy, việc khớp đường cong nghĩa là ta cần cực tiểu hóa khoảng cách của tất cả các điểm trong tập \(points\) đến \(Q(t)\): \(\displaystyle \sum_{i=1}^n ||P_i - Q(t_i)||\), với \(t_i\) là giá trị tham số \(t\) tương ứng với điểm \(P_i\). Để đơn giản hóa, ta tìm cực tiểu của tổng bình phương khoảng cách của tất các các điểm trong tập \(points\) đến đường cong: \(\displaystyle S=\sum_{i=1}^n[P_i-Q(t_i)]^2\).
Vậy làm sao tính giá trị tham số \(t_i\) cho một điểm \(P_i\)? Đầu tiên, ta tạm thời xấp xỉ các giá trị \(t_i\) cho từng điểm \(P_i\), bằng cách đo khoảng khách của một đoạn \(P_{i-1}P_i\) trên tổng khoảng cách các đoạn từ \(P_1\)đến \(P_n\) (tham khảo function chordLengthParam). Sau đó ta cố gắng tính \(t_i\) chính xác hơn theo phương phắp lặp Newton-Ralphson, nhờ vào nhận xét rằng vector khoảng cách từ \(P_i\)và tiếp tuyến tại \(t_i\) là vuông góc, ta có \([Q(t_i)-P_i](Q^{\prime}(t_i)) = 0\). Công thức để cạp nhật \(t_i\) sau mỗi lần lặp tìm nghiệm: \(\displaystyle t_i \leftarrow t_i - \frac {f(t)}{f^{\prime}(t)}\).