檢查多邊形是否自相交

Question

我有一個System.Windows.Shapes.Polygon對象，其佈局完全由一系列點確定。我需要確定這個Polygon是否自相交;即，如果多邊形的任何邊在不是頂點的點處與任何其他邊相交。有沒有簡單/快速的方法來計算這個？

Answer 1

• 輕鬆，緩慢，低內存佔用：比較對所有其他各段和檢查交叉點。複雜性O（n ）。

• 稍快一點，中等內存佔用量（上述修改版本）：在空間「桶」中存儲邊緣，然後在每個桶的基礎上執行上述算法。複雜性O（n/m）對於m料斗（假設均勻分佈）。

• 快速&高內存佔用空間：使用空間散列函數將邊緣拆分爲存儲桶。檢查碰撞。複雜性O（n）。

• 快速&低內存佔用：使用一個掃描線算法，如一項所述here（或here）。複雜爲O（n log n）的

最後是我最喜歡的，因爲它有良好的速度 - 內存平衡，尤其是Bentley-Ottmann algorithm。實施也不是太複雜。

Answer 2

檢查是否有任何一對不連續線段相交。

Answer 3

爲了完整起見，我在本次討論中增加了另一種算法。

假設讀者知道軸對齊的邊界框（如果不是Google的話）可以非常高效地使用「掃描和修剪算法」快速查找具有AABB衝突的邊對。 （去谷歌上查詢）。然後在這些對上調用交集例程。

這裏的優點是，你甚至可以相交一個非直邊（圓和樣條曲線），這種方法雖然幾乎相同，但效率更高。