Tôi đã viết mã để thực hiện việc này từ rất lâu rồi. Dự án tôi đã làm việc trên các đối tượng 2D được xác định bằng cách sử dụng các ranh giới Bezier chắp vá được tạo ra dưới dạng đường dẫn PostScipt.
Cách tiếp cận tôi đã sử dụng là:
Để đường cong p, q, được xác định bởi các điểm kiểm soát Bezier. Họ có giao nhau không?
Tính các hộp giới hạn của các điểm kiểm soát. Nếu chúng không chồng lên nhau, thì hai đường cong không cắt nhau. Nếu không:
p.x (t), p.y (t), q.x (u), q.y (u) là đa thức khối trên 0 < = t, u < = 1.0. Khoảng cách bình phương (p.x - q.x) ** 2 + (p.y - q.y) ** 2 là đa thức trên (t, u). Sử dụng Newton-Raphson để thử và giải quyết điều đó bằng không. Vứt bỏ bất kỳ giải pháp nào bên ngoài 0 < = t, u < = 1.0
N-R có thể hoặc không thể hội tụ. Các đường cong có thể không giao nhau, hoặc N-R chỉ có thể nổ tung khi hai đường cong gần như song song. Vì vậy, cắt bỏ N-R nếu nó không hội tụ sau một số lần lặp lại tùy ý. Đây có thể là một con số khá nhỏ.
Nếu N-R không hội tụ về một giải pháp, chia một đường cong (nói, p) thành hai đường cong pa, pb tại t = 0,5. Điều này là dễ dàng, nó chỉ là các điểm giữa tính toán, như bài báo được liên kết cho thấy. Sau đó kiểm tra đệ quy (q, pa) và (q, pb) cho giao lộ. (Lưu ý rằng trong lớp đệ quy tiếp theo rằng q đã trở thành p, sao cho p và q được luân phiên tách trên mỗi lớp đệ quy.)
Hầu hết các cuộc gọi đệ quy trở lại nhanh chóng vì các hộp giới hạn không chồng chéo .
Bạn sẽ phải cắt bỏ đệ quy ở độ sâu tùy ý, để xử lý các trường hợp lạ khi hai đường cong song song và không hoàn toàn chạm vào, nhưng khoảng cách giữa chúng là nhỏ tùy ý - có lẽ chỉ có 1 ULP của sự khác biệt .
Khi bạn tìm thấy giao lộ, bạn chưa hoàn thành, bởi vì đường cong khối có thể có nhiều giao cắt.Vì vậy, bạn phải phân chia từng đường cong tại điểm giao nhau, và đệ quy kiểm tra nhiều sự giao nhau giữa (pa, qa), (pa, qb), (pb, qa), (pb, qb).