Tìm điểm giao nhau của tất cả các đoạn đường

Question

Đưa ra danh sách các đoạn thẳng, cách dễ nhất để tìm điểm giao nhau là lặp qua danh sách đoạn đường, kiểm tra xem chúng có giao nhau hay không và ghi lại điểm giao cắt nếu có.

Nhưng thời gian chạy của phương pháp này là O(n^2), điều này rất không hiệu quả. Có thuật toán nào khác có thể tăng tốc quá trình này không?

Answer 1

Bentley-Ottmann Algorithm có thể là những gì bạn đang tìm kiếm.