Tôi có đối tượng System.Windows.Shapes.Polygon, có bố cục được xác định hoàn toàn bằng một loạt các điểm hay không. Tôi cần phải xác định nếu đa giác này là tự giao nhau; tức là, nếu bất kỳ cạnh nào của đa giác giao nhau với bất kỳ cạnh nào khác tại một điểm không phải là đỉnh. Có cách nào dễ dàng/nhanh chóng để tính toán điều này?Kiểm tra xem Đa giác có tự liên kết
dễ dàng, chậm, thấp bộ nhớ dấu chân: so sánh từng phân khúc chống lại tất cả những người khác và kiểm tra các nút giao thông. Mức độ phức tạp O (n).
Dấu chân bộ nhớ nhanh hơn, trung bình (phiên bản sửa đổi ở trên): lưu trữ các cạnh trong "nhóm" không gian, sau đó thực hiện trên thuật toán trên cơ sở mỗi nhóm. Độ phức tạp O (n/m) cho m nhóm (giả định phân phối đồng đều).
Nhanh & dấu chân bộ nhớ cao: sử dụng hàm băm không gian để tách các cạnh thành nhóm. Kiểm tra va chạm. Độ phức tạp O (n).
nhanh & bộ nhớ thấp chân: sử dụng một thuật toán quét trực tuyến, chẳng hạn như một trong những mô tả here (hoặc here). Phức tạp O (n log n)
cuối cùng là yêu thích của tôi vì nó có tốc độ tốt - cân bằng bộ nhớ, đặc biệt là Bentley-Ottmann algorithm. Việc triển khai cũng không quá phức tạp.
Kiểm tra xem bất kỳ cặp nào của không liền kề đoạn đường cắt nhau.
Tất cả chúng nên giao nhau tại các đỉnh; câu hỏi sau đó trở thành cách nhanh nhất để kiểm tra giao điểm không đỉnh trong một tập hợp các đoạn đường tùy ý là gì. – GWLlosa
Điểm tốt, chỉnh sửa nó để kiểm tra xem các đoạn không tiếp giáp cắt nhau hay không. Tôi không nghĩ rằng có một phương pháp được xây dựng trong, bạn sẽ phải viết một phương pháp. Bắt đầu bằng cách lấy Polygon.Points –
Bạn không có nghĩa là các đoạn ** mở **? Tôi chưa bao giờ nghe nói về các đoạn đường không tiếp giáp. –
Vì mục đích hoàn chỉnh, tôi thêm thuật toán khác vào cuộc thảo luận này.
Giả sử người đọc biết về các hộp giới hạn trục liên kết (Google nếu không) Có thể rất nhanh để tìm các cặp cạnh có xung đột AABB của họ bằng cách sử dụng "Sweep and Prune Algorithm". (Google nó). Các thói quen giao lộ sau đó được gọi trên các cặp này.
Lợi thế ở đây là bạn thậm chí có thể cắt một cạnh thẳng (hình tròn và đường tròn) và cách tiếp cận tổng quát hơn mặc dù hiệu quả gần như tương tự.
Tôi đang cố gắng để có được đầu của tôi xung quanh thuật toán cuối cùng như chúng ta nói; đặc biệt, tôi đang gặp khó khăn khi theo dõi ý nghĩa/mục đích của cấu trúc T. – GWLlosa
* T * là một cấu trúc, có chứa các đoạn thẳng cắt ngang đường quét * L *. Cấu trúc hiệu quả nhất sẽ là cây tìm kiếm nhị phân (xem thêm thuật toán [Bentley – Ottmann] (http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm)). –
Tôi đã thêm một [liên kết khác nơi thuật toán Bentley-Ottmann] (http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm) được mô tả bằng hình minh họa. –