How to find convex hull in a 3 dimensional space

问题:

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.

It says:

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.

回答1:

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. At the lower end on both measures is my own C code:
     
In between there is code all over the web, including this implementation of QuickHull.

回答2:

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:

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

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

3. 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.

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

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

6. 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.

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

Gift wrapping algorithm:

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.

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.

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

回答3:

GPL C++ code for finding 3D convex hulls is available at http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz and a description of the O(n log(n)) algorithm at http://www.newtonapples.net/NewtonAppleWrapper.html