检查多边形是否为自相交

Question

我有一个System.Windows.Shapes.Polygon对象,其布局完全由一系列点确定.我需要确定这个Polygon是否是自相交的; 即,如果多边形的任何边与不是顶点的点处的任何其他边相交.有一种简单/快速的方法来计算它吗？

Answer 1

• 简单,缓慢,低内存占用:将每个分段与其他分段进行比较并检查交叉点.复杂度O(n ²).

• 稍快,中等内存占用(上面的修改版本):在空间"桶"中存储边缘,然后在每个桶的基础上执行上述算法.复杂性为O(n ²/m)的为米桶(假设均匀分布).

• 快速和高内存占用:使用空间散列函数将边分割成桶.检查碰撞.复杂度O(n).

• 快速和低内存占用:使用扫描线算法,例如此处(或此处)描述的算法.复杂度O(n log n)

最后一个是我最喜欢的,因为它具有良好的速度 - 内存平衡,尤其是Bentley-Ottmann算法.实施也不是太复杂.