找到一组点是否描述凸包的算法

我想检查一组N个点是否描述凸多边形

我想知道是否有一个好的算法呢？

以下是我想到的一些方法：

---

1.凸包算法：

如果该集合等于他的凸包，那么它是凸的。 这种算法的复杂性是O（n * LN（N））。 但我的感觉就像是在一个轮子上打蝴蝶。

---

3.看角度：

然后我想到检查2个连续矢量的角度是否不超过180°。 但是因为我的观点并不是有序的，我需要检查3个连续点的所有组合，这就像O（n3）的复杂性一样（应该有办法做得比这更好）

例如，我尝试从右到左选择点，但结果并不总是预期的结果：

例如，在这种情况下，如果我从左到右，我会找到一个凸形状：

所以对于这个解决方案，我可能需要一个好的算法来选择点。

---

3.看重心：

我认为检查所有3个连续点的中心是否在形状内部会告诉我该形状是否为凸形。

这里是我的意思（G是每个三角形的中心）：

对于这个解决方案，我可以毫无问题地从左至右选择点。 如果检查G是否在形状中的复杂度是O（N），那么整体复杂度将会是O（N2）。

您能否请您提供一个很好的算法来解决这个问题或改进我所想的解决方案

提前致谢

---

如果你的输入是一个简单的多边形，你可以在线性时间内完成，但它并不明显。 这个问题有很长的历史不正确的解决方案，您可以在以下网页上阅读：

http://cgm.cs.mcgill.ca/~athens/cs601/

今天，人们普遍接受的是，解决这个问题最简单/最好的方法是使用Melkman算法：

http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm#Melkman%20Algorithm

如果你没有一个简单的多边形，那么在最坏的情况下它就像常规的凸包一样坚硬（因为你可以采取任何普通的凸包问题并任意连接点来获得一些无意义的多边形）。

---

我正考虑从维基百科开始Grahams扫描：

做所有事情，包括“用极角排序点[1]”。

然后：

for i = 3 to N:
    if ccw(points[i-2], points[i-1], points[i]) < 0: # Note this inequality might need checking
        return NotConvex
return Convex

排序和凸性检查均适合并行化，如果需要，可以合并以进一步提高速度。

链接地址: http://www.djcxy.com/p/53519.html

上一篇: Algorithm to find if a set of point describes a convex enveloppe

下一篇: google::dense