测试多边形是简单还是复杂

Question

对于定义为(x,y)点序列的多边形,如何检测它是否复杂？复杂多边形与自身交叉,如图所示:

有没有比检查时间复杂度为O(N ²)的每一对更好的解决方案？

Answer 1

有扫描方法可以比蛮力方法更快地确定这一点.此外,它们可用于将非简单多边形分解为多个简单多边形.

有关详细信息,请参阅此文章,特别是此代码,以测试简单的多边形.

Answer 2

对于基于扫描的O((N + I)log N)方法,参见Bentley Ottmann算法.其中N是线段的数量,I是交叉点的数量.