测试一个多边形是简单的还是复杂的。

Question

对于由一系列(x,y)点定义的多边形，如何检测它是否为复杂多边形？复杂多边形与自身相交，如下所示：

有没有比O(N^2)更好的解决方案来检查每对多边形点?

- Drew Noakes

---

如果用户使用gmaps输入多边形，那么您不太可能有超过100个顶点。在这种情况下，我会先采用简单的解决方案，看看是否足够。 - Nikita Rybak

@Nikita，这个问题可能在那方面有点误导。用户还可以编辑一个具有数千个顶点的现有多边形。不管怎样，我仍然很想知道最佳方法是什么。 - Drew Noakes

Answer 1

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

详情请参见本文，特别是测试简单多边形的代码。

- Reed Copsey

---

代码链接为 http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon()，从 Markdown 自动转义的版本无法使用。 - Ryan Ahearn

链接已经失效。除了“存在一个可以实现这个功能的算法”之外，这个答案没有提供任何其他信息。这就是为什么自包含的答案非常重要的原因。:( - Cris Luengo

Answer 2

关于这一点，可以查看 Bentley Ottmann算法，它是基于扫描线的O((N + I)log N)方法。 其中 N 是线段的数量，I 是交点的数量。

- Amit Prakash

Answer 3

事实上，可以使用Chazelle的三角剖分算法在线性时间内完成此操作。它可以将多边形三角剖分，或者发现该多边形不是简单多边形。

- Chao Xu

---

由于实现复杂，Chazelle的实际应用非常少，甚至可以说几乎没有。 - Brandon Kohn