由网友(野蛮:)分享简介：有关定义为（X，Y）点的序列多边形，我怎么能检测是否是复杂的或没有？一个复杂的多边形有交点本身，如下所示：For a polygon defined as a sequence of (x,y) points, how can I detect whether it is complex or not? A com...

有关定义为（X，Y）点的序列多边形，我怎么能检测是否是复杂的或没有？一个复杂的多边形有交点本身，如下所示：

For a polygon defined as a sequence of (x,y) points, how can I detect whether it is complex or not? A complex polygon has intersections with itself, as shown:

有没有比检查每对一个更好的解决方案，这将有O（N 2 ）？

Is there a better solution than checking every pair which would have a time complexity of O(N2)?

推荐答案

有扫描方法，可以判断这个速度远远超过蛮力的方法。此外，它们可以被用来打破非简单的多边形分成多个多边形简单

There are sweep methods which can determine this much faster than a brute force approach. In addition, they can be used to break a non-simple polygon into multiple simple polygons.

有关详细信息，请参见这篇文章，尤其是这的 code测试一个简单的多边形。

For details, see this article, in particular, this code to test for a simple polygon.