测试多边形是否简单或复杂 [英] Testing whether a polygon is simple or complex

问题描述

有关定义为（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 ² ）？

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

推荐答案

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

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.

这篇关于测试多边形是否简单或复杂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！