给定一组点S (x, y, z)。如何找到convex hull那些点？
我试着从这里理解算法，但没有得到太多。
它说：
首先将所有点投影到 xy 平面上，然后通过选择 y 坐标最高的点找到肯定在船体上的边缘，然后进行一次礼品包装迭代以确定边缘的另一个端点。这是不完整船体的第一部分。然后我们迭代地构建船体。考虑这第一条边；现在找到另一个点以形成船体的第一个三角形面。我们通过选择一个点来做到这一点，使得所有其他点都位于这个三角形的右侧，当正确查看时（就像在礼品包装算法中，我们选择了一条边，使得所有其他点都位于三角形的右侧那个边缘）。现在船体中有三个边缘；继续，我们任意选择其中一个，并再次扫描所有点以找到另一个点以使用该边构建一个新三角形，并重复此操作直到没有剩余边为止。（当我们创建一个新的三角形面时，我们将两条边添加到池中；但是，我们必须首先检查它们是否已经添加到船体中，在这种情况下我们忽略它们。）有 O(n) 个面，并且每次迭代都需要 O(n) 时间，因为我们必须扫描所有剩余的点，给出 O(n2)。
谁能以更清晰的方式解释它或提出更简单的替代方法。
实现 3D 凸包并不容易，但已经实现了许多算法，并且代码广泛可用。CGAL是质量和时间投资的高端。在这两种措施的低端是我自己的 C 代码：
在这两者之间有遍布网络的代码，包括这个 QuickHull 的实现。
我建议首先尝试一种更简单的方法，例如快速船体。（顺便说一句，礼品包装的顺序是 O(nh) 而不是 O(n2)，其中 h 是船体上的点，快速船体的顺序是 O(n log n)）。
在一般情况下，快速 hull 工作得很好，但在高度对称或点位于圆周上的情况下，处理通常会变慢。快速船体可以分解为以下步骤：
找到具有最小和最大 x 坐标的点，这些点必然是凸的一部分。
使用两个点形成的线将集合划分为两个点子集，将递归处理。
确定线的一侧与线的最大距离的点。之前找到的两点与这一点一起形成一个三角形。
位于该三角形内部的点不能成为凸包的一部分，因此可以在接下来的步骤中忽略。
在三角形形成的两条线（不是初始线）上重复前两个步骤。
继续这样做，直到没有剩下的点，递归已经结束，选择的点构成凸包。
请参阅this impementaion and explanation for 3d convex hull using quick hull algorithm。
礼品包装算法：
Jarvis 的匹配算法就像在点周围缠绕一根绳子。它首先计算最左边的点 l，因为我们知道最左边的点必须是一个凸包顶点。这个过程将花费线性时间。然后算法执行一系列旋转步骤以找到每个连续的凸包顶点，直到下一个顶点又是原来的最左边的点。
该算法像这样找到连续的凸包顶点：点 p 之后的顶点是看起来离站在 p 处并看着其他点的人最右边的点。换句话说，如果 q 是 p 之后的顶点，并且 r 是任何其他输入点，那么三元组 p、q、r 是按逆时针顺序排列的。我们可以通过执行一系列 O(n) 逆时针测试在线性时间内找到每个连续的顶点。
由于该算法为每个凸包顶点花费 O(n) 时间，因此最坏情况的运行时间为 O(n2)。但是，如果凸包的顶点很少，Jarvis 的行进速度非常快。编写运行时间的更好方法是 O(nh)，其中 h 是凸包顶点的数量。在最坏的情况下，h = n，我们得到旧的 O(n2) 时间界限，但在最好的情况下，h = 3，算法只需要 O(n) 时间。这就是所谓的输出敏感算法，输出越小，算法越快。
下面的图片应该给你更多的想法
用于查找 3D 凸包的 GPL C++ 代码可在http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz获得，O(n log(n)) 算法的描述在http://www.newtonapples .net/NewtonAppleWrapper.html