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

对于定义为（x，y）点序列的多边形，如何检测它是否复杂？一个复杂的多边形具有交叉点与自身，如图所示：测试多边形是简单还是复杂

example complex polygon image

是否有比检查每对这将具有O（N 2 ）的时间复杂度的更好的解决方案？

那么，如果多边形是由用户使用gmaps输入的，那么你不可能有超过100个顶点。在这种情况下，我会先用简单的解决方案，看看是否足够。 – 2010-10-23 00:00:35

@Nikita，这个问题在这方面可能是误导。用户还可以编辑具有数千个顶点的现有多边形。无论如何，我仍然有兴趣了解最佳方法。 – 2010-10-23 00:03:28

有扫描方法可以比暴力方法快得多。另外，它们可以用来将一个非简单的多边形分解为多个简单的多边形。

有关详细信息，请参阅this article，特别是此code to test for a simple polygon。

2010-10-23 00:15:53

代码链接是http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon（）markdown中的自动转义版本不起作用。 – 2013-06-26 14:01:27

参见Bentley Ottmann Algorithm用于基于扫描的O（（N + I）logN）方法。其中N是线段的数量，I是交点的数量。

2010-10-23 04:01:58

实际上，这可以用线性时间来完成Chazelle的三角剖分算法。它要么对多边形进行三角化，要么发现多边形并不简单。

2015-01-17 09:28:12

除了由于其实施的复杂性而导致Chazelle的实际实现的宝贵数量很少。 – 2016-02-17 16:42:18

回答