將一組線條拆分爲相交線段

Question

我有一組線條可能會在某些點相交。每條線至少有2個點。我想要做的是當每條線與其他線相交併將所有線存儲到列表中時分割每條線。在這個結果列表中可能沒有任何行與其他行相交。

一個路口可能只在一條線上的點是什麼使路口檢測微不足道（只是相互比較各點）進行。我認爲非常具有挑戰性的是找到解決此問題的高性能算法。

感謝您的幫助！

編輯：線被表示爲點，例如， A =（0,0），（10,1），（20,2），（30,3），（35,4），B =（12,4），（10,1） 5）

Answer 1

平面掃描算法。

在任何地方查找參考。

本質上，我們沿着x軸掃描每個線段，將startx和endx存儲爲「事件」。排序事件。然後，您保留第二個「活動」段的排序列表，當您點擊startx時將行添加到活動列表中，並在您碰到endx時刪除它。活動列表按y排序。所以你只需要一些實際的相交測試，其中x和y都重疊。