有沒有一種有效的方法來計算給定的一組線段之間的交點數量？

Question

假設我在一般位置有n條線段。我怎樣才能快速計算出n個分段中的每個分段有多少個n-1相交？

我可以在O（n ）的時候做到這一點。我可以在O（（n + k）log n）時間內使用相當直接的掃描線算法（Bentley-Ottmann）找到所有交點，其中k是這樣的交點的數量，然後將我發現的交點聚集成一堆計數。

我不需要找到的交叉點，雖然;我只想知道有多少。我看不出如何修改掃描線算法，因爲它需要爲每個交集重新排列樹中的兩個東西，而且我也想不到任何其他不會遇到相同問題的技術。

我也有興趣聽到如何計算有多少總交叉點。

Answer 1

我很難相信在一般情況下你可以比賓利奧特曼做得更好。如果您不關心線段相交的位置，您可以簡化計算，但是我沒有看到如何在不發現它們的情況下計算交叉點。

本質上，Bentley Ottman是一種簡化交叉路口搜索空間的方法。還有其他一些方法可能適用於線段的特定佈置，但除非您的線段之間存在某種可預測的幾何關係，否則您將無法比第一種方法更好地使用某種巧妙的方法找到候選交點並將其與個別覈對每位候選人。

除非您的問題域具有某些可能會提供可開發子結構的特定功能，否則我認爲您最好的速度選擇是使Bentley Ottman（或某種類似的掃描算法）適用於並行執行。 （將線段剪成樂隊是很簡單的，找出一組最佳樂隊也會很有趣。）當然，這是一個實用的而不是學術的練習;並行算法可能最終會完成更多的工作;它只是利用硬件在（固定因素）時間內完成工作。