查找所有線段的交點

Question

給定一個線段列表，找到交點的最簡單方法是循環顯示線段列表，檢查它們是否相交併記錄相交點（如果有）。

但此方法的運行時間爲O(n^2)，效率非常低。有沒有其他算法可以加速這個過程？

Answer 1

Bentley-Ottmann Algorithm可能是你在找什麼。