检查多边形是否为自相交

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

简单，缓慢，低内存占用 ：将每个分段与所有其他分段进行比较并检查交叉点。复杂度O（n ² ） 。
略快，中等内存占用 （上面的修改版本）：在空间“桶”中存储边缘，然后在每个桶的基础上执行上述算法。 m桶的复杂度O（n ² / m） （假设均匀分布）。
快速和高内存占用 ：使用空间散列函数将边分割成桶。检查碰撞。复杂度O（n） 。
快速和低内存占用 ：使用扫描线算法，例如此处（或此处）描述的算法。复杂度O（n log n）

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

检查是否有任何一对非连续线段相交。

为了完整起见，我在本次讨论中添加了另一种算法。

假设读者知道轴对齐的边界框（如果不是谷歌的话）。使用“扫描和修剪算法”快速找到具有AABB冲突的边对可能非常有效。（谷歌一下）。然后在这些对上调用交叉例程。

这里的优势在于您甚至可以与非直边（圆和样条）相交，并且该方法更通用，尽管几乎同样有效。