giao lộ phân đoạn-đa giác

Question

Lời chào,

Tôi muốn phát hiện xem phân đoạn có 'chạm' đa giác hoặc gạch chéo hay không.

Các Hình

giải thích nghi ngờ của tôi. Làm thế nào để biết sự khác biệt giữa các trường hợp A và B? Lưu ý rằng trong cả hai trường hợp, đường màu đỏ đi qua các đa giác ở hai đỉnh, một chạm vào bên ngoài và các đường cắt ngang khác bên trong. Tôi có thuật toán giao cắt phân đoạn, nhưng tôi không biết cách sử dụng nó đúng cách. Bất kỳ trợ giúp được đánh giá cao.

Answer 1

Tôi nghĩ rằng có thể không có cách tiếp cận nào dễ dàng hơn nhiều so với việc tính toán chi tiết ở mức thấp. Trước tiên, bạn sẽ cần mã mạnh để tính toán giao lộ giữa hai đoạn. Điều này được thảo luận (có mã) here. Khi bạn có các điểm giao nhau, bạn cần để tính toán cách ranh giới đa giác tương tác với phân đoạn của bạn trong vùng lân cận của các điểm giao nhau đó là . Về cơ bản, đây là số lặp lại LeftOf() tính toán, sử dụng ký pháp trong sách của tôi. Trong hình ảnh của bạn, phân khúc đi qua đỉnh b, trong khi các đỉnh liền kề một và c (trong một chuỗi liên tiếp (a, b, c)) đều đến cùng một phía của b. Do đó, đoạn không xâm nhập vào bên trong đa giác trong vùng lân cận của b. Nhưng nếu a và c nằm ở hai bên đối diện của đoạn đó, thì phải xuyên qua.

Answer 2

Nói chung, một giao lộ có thể bao gồm nhiều điểm. Ví dụ: xem http://cagd.cs.byu.edu/~557/text/ch7.pdf thảo luận về cách đường cong phẳng cắt nhau và đường cong tiếp tuyến cắt nhau tại hai điểm "được tính đúng", phản trực giác. Trong trường hợp của một đa giác lồi với một đường chăn thả, giao lộ có hai điểm "được tính đúng không?" Trong trường hợp của bạn, có hai điểm giao nhau với hai điểm không?

Vì vậy, Giáo sư O'Rourke đưa ra thuật toán tính toán số điểm trong giao lộ, để nói. Thực tế, một gói cho giao lộ tính toán có trả về số điểm trong mỗi giao lộ không?