Functions | |
void | Compute_Convex_Hull (int pcount, const HC_POINT *points, int *fcount, int *face_list) |
void Compute_Convex_Hull | ( | int | pcount, | |
const HC_POINT * | points, | |||
int * | fcount, | |||
int * | face_list | |||
) |
Given a set of points, determines the set of faces that minimally bind all the points.
pcount | - Number of valid points in points. | |
points | - Vector of x-y-z triplets for the coordinates of the vertices. (A simple N*3 can also be used.) Passed by reference always. | |
fcount | - Total number of integers returned in face_list. Passed by reference always. Returned to user. | |
face_list | - Encoded description of how to connect the points to build the faces of the hull. Same format as in Insert_Shell() . Passed by reference always. Returned to user. Potentially up to 8*pcount*sizeof(int) in length. |
For all but the simplest sets of points there are many possible hulls. However, disregarding degeneracies (coplanar/colinear points), there is only one possible convex hull surrounding any given set of points. Compute_Convex_Hull() computes this shape. The input is a list of points. The output is a face connectivity list suitable for passing to Insert_Shell() .
Compute_Convex_Hull() only produces convex figures, by definition. However, there is nothing preventing you from artificially moving one of the points inward to form a concave figure after Compute_Convex_Hull() returns. Likewise, Compute_Convex_Hull() only produces closed figures, by definition. There is nothing preventing you from artificially removing one or more of the faces to form an open shell afterwards.
The algorithm used is O(n squared). In other words, it's going to take a while.
Not all the points will necessarily be mentioned in the face_list. Depending on the shape of your object, many points might be completely interior to the hull and thus unconnected.
Another definition of "convex hull" is "the surface of the smallest area that encloses a set of points".