问题标签 [convex-hull]

嗨，还请考虑我有 4 个点，我将有 4 个三角形，我如何检查这四个三角形中的每个点是否是三角形内的点。谢谢

我需要一种算法来计算 O(n) 中点的 Voronoi 图的一组点的凸包。Voronoi 图包含在边界框中，并存储为双向连接的边列表。输入是一个半边，其原点在边界框上。

我知道两个点在凸包上是相邻的，如果它们共享一个无限长的 voronoi 边。

我使用 swig 包装 ac 函数以在 python 代码中使用时遇到属性错误。我在 chap 旁边还有其他功能可以正常工作，但是有些奇怪的原因这个不起作用：/

我正在尝试使用 CGAL 来确定所有粒子的凸包（第一章）。下面是 chap 函数和回溯：

I'm trying to wrap my head around rendering point clouds. Right now I'm using Processing/Java, and have a pseudo working thing using QuickHull 3D, but it's not what I've been looking for, effect wise.

This is a sample of what I have: http://vimeo.com/17509829 Here's the javadocs for Quickhull3D: http://www.cs.ubc.ca/~lloyd/java/doc/quickhull3d/index.html

The Convex hull method is effective for identifying a bounding type of mesh, but not what I'm looking for, which is closer to a "shrink wrap" effect. I had hoped that I might be able to limit the distance two vertices might be joined by the QuickHull3D, but no go. Long story short, what's happening is this: http://www.cs.sunysb.edu/~algorith/files/convex-hull.shtml

And I want to be able to identify that the G is a G, however crudely.

Can anyone recommend a different approach for tackling this, a second step that I'm missing/unaware of, or alternatively, a way of actually limiting the distance for joining those vertecies? I know that's kinda not the point of the convex hull approach, so I shy from asking that, but any help would be appreciated.

Thanks!

我正在尝试研究和实现一些计算机视觉技术，例如对 2D 中的一组任意点进行运动跟踪。我正在为我知道的一组点生成一个凸包，并为它可能映射到的一组点生成一个凸包。我正在寻找可以帮助我比较两个船体的相似程度的资源，然后如果足够相似，它们实际上是如何相互映射的？任何关于在哪里可以找到讨论这种算法风格和该领域可能更复杂算法的好资源/书籍的信息将不胜感激。

我有两个凸包，我只是想知道是否有人知道任何好的算法或资源/对如何将一个凸包的位置与另一个进行比较有任何想法？

距离、方向和相似性将是一个很好的开始。

我有一个 GPS 集群（包含许多彼此靠近的 GPS 点），我想通过在其外点周围创建一个多边形来将其识别为一个地方。一种方法是 Convex Hull，我正在寻找它在 Javascript 中的实现。

任何想法？

相关：多边形分解 - 去除凹点以形成凸多边形

我正在寻找一种算法来执行以下操作：

输入是二维点数组 (P ₀ …P _N-1 )。数组的长度 N 变化 (3 ≤ N < ∞)
对于任何 M ≤ N，可能有也可能没有顶点为 P ₀ …P _M-1的凸多边形。

请注意 ，边缘不一定是阵列中的相邻对。

找到最大 M 以使该凸多边形存在的最有效算法是什么？

我目前的算法效率很低。我用 M=3 然后 M=4, M=5 等进行测试，计算船体然后测试所有 P ₀ ...P _M-1是船体的顶点，如果不是，那么我跳出循环并返回 M- 1.

示例 #1：[(-2,2), (2,2), (-2,-2), (-1,1)]

结果：3（因为前三个点形成一个三角形，但添加 P ₃ =(-1,1)会使多边形非凸）

示例 #2：[(-2,2), (2,2), (-2,-2), (1,-1)]

结果：4（因为可以从数组中的所有 4 个点构造一个凸四边形）

更新示例 #3：[(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
结果：4。

这个例子说明了为什么只取所有提供点的凸包并找到一个前缀是它的子集是不够的。(3,-3)不能是由前五个点组成的凸多边形的一部分，因为这样前一个点将(2,-1)不再位于船体上。但它(3,-3)必须被拒绝，即使它位于所有六个点的船体上并且(2,-1)没有。

无效输入示例：

• [(-1,-1), (0,0)]（分数太少）
• [(-1,-1), (0,0), (1,1), (1, -1)]（前三点是共线的：我不希望算法能够处理这个问题。）

我想制作一组 2D 点的凸包（在 python 中）。我找到了几个有用的例子，但我有一个额外的功能我想要我无法实现。我想要做的是创建凸包，但如果它们足够“接近”边界，则允许它拾取内部点。请参见下图 -> 如果 theta < x 度，则该内部点将添加到船体中。

正如我从我的想法和测试中发现的那样，显然这会使事情变得更加复杂。例如，如果添加了一个内部点，那么它可能会允许添加另一个更进一步的内部点。

速度在这里并不是一个真正的问题，因为我将使用的点数相对较少。我宁愿有一个更健壮的算法，而不是一个快速的算法。

我想知道是否有人知道任何这样的例子，或者可以指出我从哪里开始的正确方向。谢谢。

我有一些二维点，我想用这些点绘制一个多边形。这个多边形必须通过所有给定的点，这意味着多边形内部或外部没有这样的点。

例如：如果我有如下点：(0,0)、(1,1)、(-1,-1)、(-1,1) 和 (1,-1)，如果我想绘制多边形使用那些然后我的点数组应该按以下方式排序：

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) 或

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

但它不能是：

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1, 1)

为了绘制多边形，我使用drawLine函数并从一个点画线到另一个点，最后从最后一个点画到第一个点。

有没有可用的算法或代码？

谢谢！！