给定一组点S (x, y, z)。如何找到convex hull那些点？
我尝试理解该算法here http://wcipeg.com/wiki/Convex_hull，但拿不到太多。
It says:
首先将所有点投影到 xy 平面上，并通过选择具有最高 y 坐标的点来找到肯定位于船体上的边缘，然后进行一次礼品包装迭代以确定边缘的另一个端点。这是不完整船体的第一部分。然后我们迭代地构建船体。考虑第一个边缘；现在找到另一个点以形成船体的第一个三角形面。我们通过选择一个点来做到这一点，使得所有其他点都位于这个三角形的右侧，当适当地观察时（就像在礼品包装算法中一样，我们选择一条边，使得所有其他点都位于该三角形的右侧）那个边缘）。现在船体上有三个边缘；继续，我们任意选择其中一个，并再次扫描所有点以找到另一个点，用这条边构建一个新的三角形，并重复此操作，直到没有边留下。 （当我们创建一个新的三角形面时，我们向池中添加两条边；但是，我们必须首先检查它们是否已经添加到外壳中，在这种情况下我们忽略它们。）有 O(n) 个面，每次迭代都需要 O(n) 时间，因为我们必须扫描所有剩余点，给出 O(n2) 时间。
任何人都可以以更清晰的方式解释它或提出更简单的替代方法。
Implementing the 3D convex hull is not easy, but many algorithms have been implemented, and code is widely available. At the high end of quality and time investment to use is CGAL http://www.cgal.org/Manual/latest/doc_html/cgal_manual/packages.html#Part:ConvexHullAlgorithms. At the lower end on both measures is my own C code http://cs.smith.edu/~orourke/books/compgeom.html:
In between there is code all over the web, including this implementation of QuickHull http://thomasdiewald.com/blog/?p=1888.
