7

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

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

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

1.Convex Hull算法：

如果集合等于他的凸包，那么它是凸的。这种算法的复杂度为 O(n*LN(N))。但我觉得这就像在轮子上折断蝴蝶。

3.看角度：

然后我想检查两个连续向量的角度是否永远不会超过 180°。但由于我的点没有排序，我需要检查 3 个连续点的所有组合，这使得复杂度像 O(n3)。（应该有比这更好的方法）

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

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

在此处输入图像描述

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

3.看重心：

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

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

在此处输入图像描述

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

你能告诉我一个好的算法来解决这个问题或改进我正在考虑的解决方案吗

提前致谢

4

2 回答 2

3

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

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

今天，人们普遍认为解决这个问题的最简单/最好的方法是使用梅尔克曼算法：

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

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

于 2011-07-04T18:56:01.967 回答
1

我正在考虑从 Wikipedia on Grahams Scan开始：

做所有事情，包括“用点[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

排序和凸性检查都非常适合并行化，如果需要，可以合并以进一步加速。

于 2011-07-04T17:36:14.340 回答