The Algorithms

Brute Force

For every triangles/face, check if the current triangle is on the convex hull by observing all of the remaining points are on the same side of this triangle/face.

The running time is O(n^4).

Data Structure: An array to store the points and a array to store the correct convex hull triangles/faces.

Simple Incremental Construction

Construct the initial tetrahedron: The initial tetrahedron consists of four points. These four points are required that any three points are not collinear, and the four points are not coplanar. Otherwise, the initial tetrahedron cannot be generated, which will cause problems in the following incremental construction of the convex hull. If there are no such four points exist in the point set, the convex hull cannot be constructed and returns Null.

Add each vertex incrementally: Find all the faces that are visible to the vertex. The visibility of the face can be determined by the normal direction of the face. First calculate the normal direction N of the face, and then calculate the dot product of N and the vector that any point in this face to the new added point. If the product is greater than zero, then the point and the face are visible to each other, that is, the face needs to be removed. In the actual algorithm, this step should be completed by sequentially calculating the visibility of all the faces with the current point, but the efficiency may be very low.

The running time is O(n^2).

Data Structure: An array to store the points and an array to store the correct convex hull triangles/faces.

Advanced Incremental Construction

The same as the simple one. The improved place is that in this experiment, using depth-first search method, and once finding the first visible face of the new added point, then we can find all visible faces through the connection relationship between the faces.

The running time is O(n^2).

Data Structure: An array to store the points, an array to store the correct convex hull triangles/faces, and a 2D array to store the edges.

Quick Hull(Not Real)

Based on the Advanced Incremental Construction Algorithm, for the first three points which construct a face that dividing the points in two halves P1 and P2. First find 2 points which has the longest distance, connect them. Second find the point that has the longest distance with the connected edge. These three points consist first triangle/face of the initial tetrahedron. Then recursively find CH(P1) and CH(P2) then merge them. I met problem on merging the polygons so after initialize the first triangle face, I still use the dfs way. In the algorithm side, it seems nothing improved, but in the visualization side, it saves a lot of rendering process.

The running time is O(n^2) but if a real quickhull can be O(nlogn).

Data Structure: An array to store the points, an array to store the correct convex hull triangles/faces, and a 2D array to store the edges.

Gift Wrapping

Find the first face on the convex hull: The first face is not a randomly picked face, it is necessary to ensure that this surface is a surface on the convex hull. First, the point with the smallest y coordinate must be a point on the convex hull, and this point is on the the first face on the convex hull. The second point is the point with the smallest angle between the connection line with it and the first point and the xz plane. Now consider the tangent plane of the conical surface passing through the first point and the second point. The third point is the point that forms the smallest angle that the triangle/face of it and the previous two points with the tangent plane with the previous two points. Obviously, the above three points is a surface on the convex hull.

Gift "Wrapped": The wrapping starts from any currently unclosed triangle edge. Select any of its unclosed edges, and use that edge as a basis. Select a point from the remaining vertices so that the new face formed by the unclosed edge and the vertex is the same as the previously dependent face The film angle is the smallest. Obviously, the face piece selected in this way is also the face on the convex hull.

The running time is O(n*F).

Data Structure: An array to store the points, an array to store the correct convex hull triangles/faces, and a queue to store the triangles which needed to be wrapped/not entirely closed.