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

Question

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

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

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

1.凸壳赫尔算法:

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

3.寻找角度:

然后我想到检查2个连续矢量的角度是否永远不会超过180°.但由于我的点数没有被排序,我需要检查3个连续点的所有组合,这就像O(n3)复杂度一样.(应该有一种比这更好的方法)

我尝试从右到左选择点,但结果并不总是预期的结果:

例如,在这种情况下,如果从左到右,我会发现凸形:

在此输入图像描述

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

3.看着重心:

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

这就是我的意思(G是每个三角形的中心):

在此输入图像描述

对于这个解决方案,我可以从左到右选择点没有问题.如果检查G是否在形状中的复杂性是O(N)那么总体复杂度将是O(N2).

你能告诉我一个好的算法来解决这个问题或改进我想到的解决方案

提前致谢

Answer 1

如果您的输入是一个简单的多边形，您可以在线性时间内完成，但这一点也不明显。此问题长期以来一直存在错误的解决方案，您可以在以下网页上阅读：

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

如果您没有简单的多边形，那么在最坏的情况下，它与常规凸包一样困难（因为您可以采用任何普通的凸包问题并任意连接点以获得一些无意义的多边形）。