線間斷橫向

Question

我有幾個線段。線條是隨機的。我必須檢查任何兩行之間是否有交集。線路可能連接或不連接。對於這個問題什麼是最好的算法。

代碼示例非常感謝。

編輯：線段

Answer 1

假設你正在談論線段這裏（否則，簡單地比較直線的斜率：如果他們有不平等的斜坡，它們相交）。

要確定一個2個或多個線段中是否存在[單個]交叉點，可以使用Shamos-Hoey算法。

要找到所有在2個或多個線段集合中的交點，可以使用Bentley-Ottmann算法。

實施這兩種基於其他「掃描線」的算法，大量使用available on the internet。