Thuật toán Bentley-Ottmann cho hai nhóm phân đoạn đường

Question

Thuật toán Bentley-Ottmann được sử dụng để tính toán giao điểm của các đoạn đường.

Tuy nhiên, thay vì tìm các điểm giao nhau của tất cả các dòng trong số chúng, tôi muốn tìm các điểm giao nhau giữa hai nhóm đường. Điều này là để nói rằng đối với mỗi dòng trong dòng A nhóm, tôi muốn biết các điểm giao nhau giữa những dòng và các dòng trong nhóm B.

Có cách nào để tôi có thể mở rộng Bentley-Ottmann algorithm cho việc này không? Tôi đã có sẵn thuật toán Bentley-Ottmann hiện có (in the library of CGAL), và tôi không muốn sửa đổi nó. Tuy nhiên, tôi rất muốn tìm cách tái sử dụng nó và mở rộng nó.

Chỉnh sửa: Bất kỳ thuật toán nào khác (không nhất thiết dựa trên Bentley-Ottmann) đều được chào đón. Sẽ tốt hơn nếu các thuật toán đó đã được triển khai trong thư viện hiện có.

Answer 1

Bạn có thể tìm tất cả các giao lộ giữa tất cả các đường trong A+B, sau đó xóa các giao lộ giữa các dòng trong cùng một tập hợp. Bạn không tăng độ phức tạp nhiều và điều này cho phép bạn sử dụng chức năng thư viện của CGAL chưa được sửa đổi với chỉ một hàm bao bọc đơn giản.

Answer 2

Trường hợp Bentley-Ottman giữ một cây các đoạn đường được sắp xếp theo vị trí thẳng đứng hiện tại của chúng, bạn có thể giữ hai cây, mỗi cây cho nhóm A và B không? Sau đó, nơi thuật toán gốc kiểm tra những người hàng xóm ở trên và bên dưới điểm hiện tại, bạn sẽ kiểm tra A-neighbor bên trên với B-neighbor bên dưới và ngược lại.

Điều này được dựa trên một đoạn trích nhanh của bài viết trên Wikipedia; Tôi đã không viết nhiều mã hình học trong thập kỷ qua.

Answer 3

Thêm câu trả lời này cho đầy đủ, mặc dù nó có thể không phải là phương pháp hiệu quả nhất cho 2 thứ nguyên.

Trong đồ họa 3D phổ biến với 2 cây KD, có thể được sử dụng để phát hiện tất cả các nút chồng chéo (có thể được sử dụng cho các phép toán boolean trên hình học).

Ví dụ hoạt động (mã C). https://developer.blender.org/diffusion/B/browse/master/source/blender/blenlib/intern/BLI_kdopbvh.c;3b4a8f1cfa7339f3db9ddd4a7974b8cc30d7ff0b $ 1089

Nếu có nhiều phân đoạn nhỏ (như đường dẫn của đường vẽ tay), điều này sẽ có hiệu quả hợp lý. Tuy nhiên, nếu có nhiều cạnh dài (nghĩ rằng pickup-gậy) ... điều này sẽ thực hiện xấu, và bạn sẽ muốn chia các nút lá trong cây BVH để có được hiệu suất tốt hơn. Tuy nhiên nếu đó là trường hợp, nó có thể tốt hơn để sử dụng một phương pháp khác nhau như đề xuất trong câu trả lời khác.

Answer 4

Có thuật toán Bentley-Ottmann có thể được mở rộng để thực hiện việc này, cùng với các phương pháp khác.

Trong tài liệu, tác vụ bạn mô tả dọc theo các dòng báo cáo giao lộ giữa các đường màu đỏ và màu xanh.

Đây là một quá trình quét B-O mở rộng giấy tới một thuật toán tối ưu. http://www.cs.unc.edu/~snoeyink/demos/rbseg/jcdcg25.pdf

Tôi không đồng ý với tuyên bố của @ marcog về sự phức tạp. Các giấy liên kết tuyên bố tối ưu thời gian của O (n log (n + k)), nếu bạn lọc các nút giao, bạn sẽ phải thực hiện một B-O quét trên tất cả các dòng, và nó sẽ là ((n + k) log n).

Có những thuật toán tương tự khác mà có thể không đòi hỏi phức tạp dữ liệu cấu trúc http://www.cs.swarthmore.edu/~adanner/cs97/s08/pdf/palazzi93counting.pdf

Đối cạnh ít hơn và nút giao thông ít khoảng cách giữa các cạnh, các giải pháp trong câu trả lời sức việc @ marcog giếng. (Đây là một ví dụ từ CGAL http://doc.cgal.org/latest/Arrangement_on_surface_2/Arrangement_on_surface_2_2consolidated_curve_data_8cpp-example.html).

Nếu bạn cần xử lý các đa giác phức tạp (dữ liệu GIS, v.v.) hoặc cần một thuật toán chung, lớp thuật toán này có thể đáng giá trong khi đó.