问题标签 [convex-polygon]

我需要想出一个凸包算法来读取一堆 X ， Y 坐标并勾勒出图像的轮廓。我正在用 python 编码有什么想法吗？

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

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

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

1.Convex Hull算法：

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

3.看角度：

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

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

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

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

3.看重心：

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

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

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

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

提前致谢

我最近问了这个关于如何将凹多边形切割成凸多边形的问题，有人建议我进行三角剖分或多边形分区。

我正在使用的库 (SFML\Box2D) 只采用凸形。

这是我想知道的：

1. 多边形分区或多边形三角剖分更快吗？

2. 多边形分区如何工作/你是如何做到的？

不要忘记三角剖分也不需要制作凸形......

我有一个由 N 个顶点组成的多边形 P。我需要一种算法，给定 P，将其细分为一定数量的凸多边形，每个凸多边形最多使用 M 个顶点。

附言。P 是一个二维多边形。此外，我可以使用多边形三角剖分，但我对将 P 细分为具有 3 个以上顶点（并且如上所述，最多 M）的凸多边形的算法感兴趣。

给定两个简单的多边形 P 和 Q，其中 P 是凸的，但 Q 不是凸的，如果 P 有 n 并且 Q 有 m 个顶点，那么计算 P 和 Q 之间的差 $P - Q$ 的速度有多快？

可以假设多边形是作为按顺时针方向排序的顶点列表给出的。

如何获得随机地理点[十进制的纬度/经度]，放置在半径为 100 米的圆内的任何位置？圆的中心是另一个参考 GeoPoint。有没有实现这个的函数/公式？

基本上我正在读取我的 android 设备的 GPS 输入，并且需要在设备周围生成随机地理点 [在以我的设备为中心的半径 100 米的圆圈中]。

请注意：数据库中没有预先存储的地理点。如上所述，我需要动态创建所有地理点。

因此，我正在学习 Convex Hull 算法，并编写从幼稚的 Bruteforce 到 Graham Scan 的所有算法。

这是我的蛮力 O(n^4) 算法。一开始，假设所有点都是船体的一部分。对于每个可能的三角形，消除位于三角形内的所有点。最后，那些没有被淘汰的点将成为船体的一部分。

这是 Java 代码（已修复：使用 Thomash 的解决方案）

我试着在视觉上看到这些点，它们似乎是正确的，但是我不知道如何建立点的顺序来绘制凸包多边形？任何帮助表示赞赏。

我在 Matlab 中使用不同的凸包函数来查找形成凸包的点坐标。但是，这些函数返回三角形矩阵。如何指定这些点？谢谢。塞皮德

问：为什么凸多边形被认为是设计图形算法的更好选择？

我的 A. 凸多边形是平面的，更容易剪裁。

我的回答有点简短，我不确定我的回答是否正确，请问其他人可以扩展或给我一个更好的答案吗？

在 2d 中，凸包基本上表示为点之旅。似乎这种表示可能会超出二维。因为，我将很快与他们合作，我想提前知道这样做的“标准”是什么，如果有这样做的话，因为船体可能会被其他人使用。

澄清：我所指的标准是关于输出格式的，这样程序就可以从该输出中利用外壳来做其他事情。