CVEXHULL Function

CVEXHULL (matrix) ;

The CVEXHULL function finds a convex hull of a set of planar points.

The matrix argument is an $n \times 2$ matrix of $(x,y)$ points.

The CVEXHULL function returns an $n \times 1$ matrix of indices. The indices of points in the convex hull in counterclockwise order are returned as the first part of the result matrix, and the negative of the indices of the internal points are returned as the remaining elements of the result matrix. Any points that lie on the convex hull but lie on a line segment joining two other points on the convex hull are not included as part of the convex hull.

The result matrix can be split into positive and negative parts by using the LOC function. For example, the following statements find the index vector for the convex hull and print the associated points:

points = {0  2, 0.5 2, 1 2, 0.5 1, 0 0, 0.5 0, 1  0,
          2 -1,   2 0, 2 1,   3 0, 4 1,   4 0, 4 -1,
          5  2,   5 1, 5 0,   6 0 };
indices = cvexhull( points );
hullIndices = indices[loc(indices>0)];
convexHull = points[hullIndices, ];
print convexHull;

Figure 23.83: Convex Hull of a Planar Set of Points

convexHull
0 2
0 0
2 -1
4 -1
6 0
5 2