给定一组点 S（X，Y，Z）。如何找到凸包这点呢？

Given a set of points S (x, y, z). How to find the convex hull of those points ?

我试图理解从这里 的算法，但也没有得到多少。

I tried understanding the algorithm from here, but could not get much.

它说：

首先项目的所有点到xy平面，并找出一个边缘，该边缘是肯定的船体通过选择具有最高y坐标，然后做礼品包​​装的一个迭代，以确定所述边缘的另一个端点的点。这是不完整的船体的前半部分。然后，我们建立的船体反复。考虑这个第一边缘;现在发现的另一点，以便形成船体的第一三角面。为此，我们挑选了点，这样所有其他的点位于这个三角形的，适当的观看时（就像在礼品包装算法的右侧，在此我们选择了一个边缘，使得所有其他点躺着权该边缘）。现在有在船体三个边;要继续，我们选择其中的一个任意，再通过各点进行扫描，以寻找另一点建立一个新的三角形，这个边缘，重复这个直到没有边离开了。 （当我们创建一个新的三角面，我们添加两条边的游泳池;但是，我们必须首先检查他们是否已经被添加到船体，在这种情况下，我们忽略它们。）有O（n）的面孔，并且每次迭代需要O（n）的时间，因为我们必须扫描所有剩余的点，给O（N2）。

First project all of the points onto the xy-plane, and find an edge that is definitely on the hull by selecting the point with highest y-coordinate and then doing one iteration of gift wrapping to determine the other endpoint of the edge. This is the first part of the incomplete hull. We then build the hull iteratively. Consider this first edge; now find another point in order to form the first triangular face of the hull. We do this by picking the point such that all the other points lie to the right of this triangle, when viewed appropriately (just as in the gift-wrapping algorithm, in which we picked an edge such that all other points lay to the right of that edge). Now there are three edges in the hull; to continue, we pick one of them arbitrarily, and again scan through all the points to find another point to build a new triangle with this edge, and repeat this until there are no edges left. (When we create a new triangular face, we add two edges to the pool; however, we have to first check if they have already been added to the hull, in which case we ignore them.) There are O(n) faces, and each iteration takes O(n) time since we must scan all of the remaining points, giving O(n2).

任何人都可以解释它以更清晰的方式，或提出一个简单的替代方法。

Can anyone explain it in a more clearer way or suggest a simpler alternative approach.

推荐答案

我会先建议尝试像快速船体比较简单的方法。 （顺便说一句，礼品包装的顺序是O（NH）不是O（N2），其中h是船体快速船体和秩序点是O（n log n）的）。

I would suggest first try an easier approach like quick hull. (Btw, the order for gift wrapping is O(nh) not O(n2), where h is points on hull and order of quick hull is O(n log n)).

在一般情况下快速船体工作得很好，但处理通常会成为高对称的情况下，或点躺在圆的圆周速度慢。连结船体可以分解为以下步骤：

Under average circumstances quick hull works quite well, but processing usually becomes slow in cases of high symmetry or points lying on the circumference of a circle. Quick hull can be broken down to the following steps:

查找与最小和最大x坐标点，这些都是 注定是凸的一部分。

Find the points with minimum and maximum x coordinates, those are bound to be part of the convex.

使用由两个点形成的线来划分组两 点的子集，这将在循环处理。

Use the line formed by the two points to divide the set in two subsets of points, which will be processed recursively.

确定点，上线的一侧上，具有最大 距离线。之前，这一发现一起的两个点 一个形成了一个三角形。

Determine the point, on one side of the line, with the maximum distance from the line. The two points found before along with this one form a triangle.

的点，位那个三角形的内部不能是部分 凸包，因此可以在接下来的步骤可以忽略。

The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.

由所形成的两行重复previous两个步骤 三角形（非初始线）。

Repeat the previous two steps on the two lines formed by the triangle (not the initial line).

请在等，直到没有点被留做，递归拥有 走到了尽头，并选定点构成的凸包。

Keep on doing so on until no more points are left, the recursion has come to an end and the points selected constitute the convex hull.

请参阅这 impementaion，并解释了使用快速包算法的三维凸包。

See this impementaion and explanation for 3d convex hull using quick hull algorithm.

礼品包装算法：

贾维斯的匹配算法就像包裹了一块周围的点串。它开始通过计算最左边的点升，因为我们知道，最左边的点必须是凸包vertex.This过程需要线性time.Then的算法并一系列枢转步骤，找到每一连续凸包的顶点，直到下一顶点是再次原始最左边的点。

Jarvis's match algorithm is like wrapping a piece of string around the points. It starts by computing the leftmost point l, since we know that the left most point must be a convex hull vertex.This process will take linear time.Then the algorithm does a series of pivoting steps to find each successive convex hull vertex untill the next vertex is the original leftmost point again.

该算法找到连续的凸包的顶点是这样的：立即点p以下的顶点是，似乎是最远站在p和看着其他点的权利的人的地步。换句话说，如果q是以下P上的顶点，r是任何其它的输入点，则三重P，Q，r为逆时针顺序。我们可以通过执行一系列的O（n）的逆时针测试发现每个连续的顶点以线性时间。

The algorithm find the successive convex hull vertex like this: the vertex immediately following a point p is the point that appears to be furthest to the right to someone standing at p and looking at the other points. In other words, if q is the vertex following p, and r is any other input point, then the triple p, q, r is in counter-clockwise order. We can find each successive vertex in linear time by performing a series of O(n) counter-clockwise tests.

由于算法花费O（N）时间为每个凸包的顶点，运行时间的最坏情况是O（N 2）。但是，如果凸包有极少数的顶点，贾维斯的行军速度极快。一个更好的方式来写的运行时间为O（NH），其中h是凸包顶点数量。在最坏的情况下，H = N，我们得到我们的必然旧的O（n2）的时间，但在最好的情况下，H = 3，算法只需要O（n）的时间。这是所谓的输出敏感的算法，较小的输出，更快的算法

Since the algorithm spends O(n) time for each convex hull vertex, the worst-case running time is O(n2). However, if the convex hull has very few vertices, Jarvis's march is extremely fast. A better way to write the running time is O(nh), where h is the number of convex hull vertices. In the worst case, h = n, and we get our old O(n2) time bound, but in the best case h = 3, and the algorithm only needs O(n) time. This is a so called output-sensitive algorithm, the smaller the output, the faster the algorithm.

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

The following image should give you more idea