[Q] Thuật toán vẽ đường cubic spline

[vietlap]

Có bạn nào biết thuật toán vẽ đường cong dạng cubic spline qua một số điểm cho trước thì giúp mình với. Cám ơn nhiều.
Lập.

[Mach2]

Vào đây đi bạn http://www.diendantinhoc.com/showthread.php?threadid=15402

[vietlap]

Cám ơn bạn. Nhưng tài liệu đơn giản và khó hiểu quá. Nếu bạn có tài liệu chi tiết hơn thì giúp mình với nhé. Cảm ơn bạn trước. Lập.

[Mach2]

Hic, mình đưa cách giải ra thui, đương nhiên là đơn giản rùi. Thuật toán chi tiết thì để mình xem lại sau nhé.

[mqt]

Lập,

Trước hết cho mình xin lỗi nếu có những chổ mình không biết từ tiếng Việt. Để mình ráng giải thích thử nha. Cái này học cũng lâu rồi mà không có xài.

Bạn xem hình kèm theo ở dưới.
Đường cong được biểu diễn qua t (parameterized by t)
Có 4 điểm A,B,C,D, đây là những giới hạn:

AE=t AB; BF=t BC; CG=t CD; EH=t EF; FI=t FG; HJ=t HI

Bạn hãy tưởng tượng rằng khi t tăng từ 0 tới 1, E chạy trên AB từ A tới B, F chạy trên BC từ B tới C, G chạy trên CD từ C tới D, H chạy trên EF từ E tới F, I chạy trên FG từ F tới G và J chạy trên HI từ H tới I. Quỹ tích của J chính là đường cong cubic spline.

Ví dụ tọa độ của E có thể được biểu diễn như sau:
Ex = (1-t )Ax + tBx
Ey = (1-t )Ay + tBy

Với những điều đã biết này, tọa độ của điểm J là như sau:
x = At^3 + Bt^2 + Ct + D
y = Et^3 + Ft^2 + Gt + H
when t increase from 0 to 1
với
A = Dx - 3Cx + 3Bx - Ax
B = 3Cx - 6Bx + 3Ax
C = 3Bx - 3Ax
D = Ax
E = Dy - 3Cy + 3By - Ay
F = 3Cy - 6By + 3Ay
G = 3By - 3Ay
H = Ay

[mqt]

Bài viết được gửi bởi mqt
Với những điều đã biết này, tọa độ của điểm J là như sau:
x = At^3 + Bt^2 + Ct + D
y = Et^3 + Ft^2 + Gt + H
when t increase from 0 to 1
với
A = Dx - 3Cx + 3Bx - Ax
B = 3Cx - 6Bx + 3Ax
C = 3Bx - 3Ax
D = Ax
E = Dy - 3Cy + 3By - Ay
F = 3Cy - 6By + 3Ay
G = 3By - 3Ay
H = Ay [/B]

Post xong rồi ngồi đọc lại thấy cũng hơi khó hiểu. cai forum này dỏm quá. không cho coi bài trước khi post.

Để cho khỏi bị confused, mqt muốn đổi mấy cái cubic constant thành lower case.

x = at^3 + bt^2 + ct + d
y = et^3 + ft^2 + gt + h
when t increase from 0 to 1
với
a = Dx - 3Cx + 3Bx - Ax
b = 3Cx - 6Bx + 3Ax
c = 3Bx - 3Ax
d = Ax
e = Dy - 3Cy + 3By - Ay
f = 3Cy - 6By + 3Ay
g = 3By - 3Ay
h = Ay

[Mach2]

Đây là đường Bezier mà bạn. Đường này rất thông dụng nhưng mà có điều nó lại ko đi qua các điểm điều khiển cho trước.

[danceswithwolves]

x = At^3 + Bt^2 + Ct + D
y = Et^3 + Ft^2 + Gt + H
đây đúng là phương trình tham số của đường Bezier. Đường này chỉ đi qua hai điểm đầu và cuối, có dạng kéo về phía hai điểm giữa chứ không như spline. Hì, đây là đường đẹp nhất trong số những đường tui biết.

[mqt]

Các bạn overlook rồi. Cả hai có dạng giống nhau vì đều là cubic polinominals. Nhưng cách tính coefficients a, b, c, ..., h của hai loại curves này khác nhau.

[Mach2]

Đúng là tên chung cả hai loại này đều là cubic polynomials.
Mình nghĩ là Bezier khác với Natural Cubic Spline (viết đầy đủ mờ).
Loại đầu mình thường dùng để vẽ còn loại sau hay dùng trong nội suy. Loại NCS ko cần tính các hệ số a,b,c,... mà chỉ cần đến giá trị đạo hàm tại các điểm điều khiển (dù tính cũng được nhưng mà khi cần 5 hay nhiều điểm điều khiển hơn thì cách tìm các hệ số lại ko tiện lém).