如何在三维空间中找到凸包

Question

给定一组积分S (x, y, z).如何找到convex hull那些点？

我尝试从这里理解算法,但是得不到多少.

它说:

首先将所有点投影到xy平面上,并通过选择具有最高y坐标的点然后执行礼品包装的一次迭代以确定边缘的另一个端点来找到肯定在船体上的边缘.这是不完整船体的第一部分.然后我们迭代地构建船体.考虑这第一个优势; 现在找到另一个点,以形成船体的第一个三角形面.我们通过选择点来使得所有其他点位于该三角形的右侧,当适当地观察时(就像在礼品包装算法中一样,我们选择边缘使得所有其他点位于右侧)那边缘).现在船体有三条边; 继续,我们任意选择其中一个,并再次扫描所有点以找到另一个点来构建具有此边缘的新三角形,并重复此直到没有剩余边缘.(当我们创建一个新的三角形面时,我们向池中添加两条边;但是,我们必须首先检查它们是否已经添加到船体中,在这种情况下我们忽略它们.)有O(n)个面,每次迭代需要O(n)时间,因为我们必须扫描所有剩余的点,给出O(n2).

任何人都可以用更清晰的方式解释它或建议一种更简单的替代方法.

Answer 1

实现3D凸包并不容易,但已经实现了许多算法,并且代码可以广泛使用.在质量和时间的高端使用投资是CGAL.在两个措施的低端是我自己的C代码:
     
介于两者之间的网络上都有代码,包括QuickHull的这种实现.

Answer 2

我建议先尝试一种更简单的方法,如快速船体.(顺便说一下,礼品包装的顺序是O(nh)而不是O(n2),其中h是船体上的点,快速船体的顺序是O(n log n)).

在平均情况下,快速船体工作得很好,但是在高对称性或位于圆周上的点的情况下,处理通常变慢.快速船体可以分解为以下步骤:

1. 找到具有最小和最大x坐标的点,这些点必然是凸起的一部分.

2. 使用由两点组成的线将该组分成两个点子集,这些子集将以递归方式处理.

3. 确定线的一侧的点与线的最大距离.之前发现的两点与此形成三角形.

4. 位于该三角形内部的点不能是凸包的一部分,因此可以在接下来的步骤中忽略.

5. 在由三角形(而不是初始线)形成的两条线上重复前两步.

6. 继续这样做直到没有剩下的点,递归已经结束并且所选择的点构成凸包.

请参阅快速船体算法对三维凸包的这一要求和解释.

礼品包装算法:

Jarvis的匹配算法就像在点周围包裹一条弦.它首先计算最左边的点l,因为我们知道最左边的点必须是凸壳顶点.这个过程将需要线性时间.然后算法执行一系列的旋转步骤来找到每个连续的凸包顶点,直到下一个顶点是最左边的原点.

该算法像这样找到连续的凸包顶点:紧跟在点p之后的顶点是站在p并观察其他点的某个人看起来最右边的点.换句话说,如果q是跟随p的顶点,并且r是任何其他输入点,则三重p,q,r是逆时针顺序.通过执行一系列O(n)逆时针测试,我们可以在线性时间内找到每个连续的顶点.

由于算法为每个凸包顶点花费O(n)时间,因此最坏情况下的运行时间为O(n2).但是,如果凸包的顶点非常少,那么贾维斯的游行速度非常快.编写运行时间的更好方法是O(nh),其中h是凸包顶点的数量.在最坏的情况下,h = n,我们得到旧的O(n2)时间限制,但在最好的情况下h = 3,算法只需要O(n)时间.这是一种所谓的输出敏感算法,输出越小,算法越快.

下面的图片应该会给你更多的想法

Answer 3

用于查找 3D 凸包的 GPL C++ 代码可在http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz和 O(n log(n)) 算法的描述在http://www.newtonapples .net/NewtonAppleWrapper.html