对于定义为一系列 (x,y) 点的多边形，我如何检测它是否复杂？复杂的多边形与自身有交点，如图所示:
有没有比检查时间复杂度为 O(N2) 的每一对更好的解决方案？
最佳答案
有扫描方法可以比蛮力方法更快地确定这一点。此外，它们还可用于将一个非简单多边形分解为多个简单多边形。
有关详细信息，请参阅 this article ，特别是这个 code to test for a simple polygon .
关于algorithm - 测试多边形是简单还是复杂，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4001745/