Syntax Supported by the IML Procedure and the iml Action
CONVEXHULL Call
CALL CONVEXHULL (indices, volume_area, points) ;
This subroutine is supported by the IML procedure and the iml action.
The CONVEXHULL subroutine finds the convex hull of a set of n-dimensional points.
The convex hull of a set of points is the smallest convex set that contains the points (Barber, Dobkin, and Huhdanpaa 1996). Equivalently, the convex hull is the convex set of all linear combinations of points in the set. The boundary of this region is referred to as the convex hull in this documentation. Most algorithms choose to present convex hulls as a set of simplices. A simplex is the simplest possible polytope that is made from line segments in any given dimension.
For a set of n-dimensional points, the convex hull is the union of 
-dimensional simplices.
For a finite set of 2-D points, the subroutine returns a set of line segments (1-D simplices). The segments form a convex polygon that encloses the planar points.
For a finite set of 3-D points, the subroutine returns a set of triangles (2-D simplices). The triangles form the faces of a convex polyhedron that contains the points.
In n dimensions, each
-dimensional simplex is specified by n vertices.
The CONVEXHULL subroutine uses the qhull package to compute the convex hull. The development of the qhull package is based on work that is partly presented in Barber, Dobkin, and Huhdanpaa (1996).
The input argument is an 
matrix. Each row of the matrix is a point in an n-dimensional space.
The CONVEXHULL subroutine returns the following values:
- indices
is a
matrix of indices, where k is the number of vertices on the convex hull. Each row of the indices matrix specifies a single segment on the hull. In two dimensions, line segments that form the convex hull are returned in a 
matrix. The line segments traverse the convex hull in counterclockwise order. - volume_area
is a
vector. The first and the second elements of the volume_area contain the geometrical volume and the area of the convex hull that encompasses the input points. In two dimensions, these values represent the area and the perimeter of the convex hull, respectively.
The following statements find the index vector as well as the coordinates of the convex hull of a set of planar points. The results are shown in Figure 39.
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 };
call convexhull(indices, va, points);
hullIndices = indices[,1];
cvxHull = points[hullIndices, ];
print indices;
print hullIndices cvxHull[c={'cx' 'cy'} L=""];
Figure 39: Convex Hull of a Planar Set of Points
| indices | |
|---|---|
| 15 | 1 |
| 1 | 5 |
| 5 | 8 |
| 8 | 14 |
| 14 | 18 |
| 18 | 15 |
| hullIndices | cx | cy |
|---|---|---|
| 15 | 5 | 2 |
| 1 | 0 | 2 |
| 5 | 0 | 0 |
| 8 | 2 | -1 |
| 14 | 4 | -1 |
| 18 | 6 | 0 |
The 
result matrix indices contains six line segments in its rows that specify the index of the convex hull vertices. The matrix cvxHull contains the coordinates of the vertices that construct the convex hull.
The following statements visualize the original points and the convex hull:
ID = j(nrow(cvxHull),1,1); /* create ID variable for POLYGON statement */
obsNum = t(1:nrow(points)); /* obs numbers for labels */
OnHull = element(obsNum, hullIndices); /* is point on boundary of convex hull? */
create CHull from points cvxHull ID obsNum OnHull
[c={'x' 'y' 'cx' 'cy' 'ID' 'obsNum' 'OnHull'}];
append from points cvxHull ID obsNum OnHull;
close;
quit;
title "Points and Convex Hull";
proc sgplot data=CHull;
polygon x=cx y=cy ID=ID / fill outline;
scatter x=x y=y / datalabel=obsNum group=OnHull
markerattrs=(symbol=CircleFilled);
run;
Figure 40 shows the computed convex hull as a polygon that encompasses the input points. The hull vertices and the interior vertices are displayed by using different colors. Notice that the polygon is traversed in counterclockwise order by the rows of the indices matrix in Figure 40.
Figure 40: Plot of the Computed Convex Hull
You can use the CONVEXHULL subroutine to obtain the convex hull of points in higher dimensions up to seven dimensions. The following example computes the convex hull of the unit cube in three dimensions. Because the cube is convex, the convex hull equals the cube itself. The CONVEXHULL subroutine returns a set of triangles that cover the faces of the cube.
points = { 0 0 0,
1 0 0,
0 1 0,
1 1 0,
0 0 1,
1 0 1,
0 1 1,
1 1 1 };
call convexhull(indices, va, points);
print indices;
print (va[1])[L="convex hull volume"];
print (va[2])[L="convex hull area"];
Figure 41: Convex Hull of a 3-D Cube
| indices | ||
|---|---|---|
| 4 | 3 | 1 |
| 2 | 4 | 1 |
| 6 | 2 | 1 |
| 5 | 6 | 1 |
| 6 | 4 | 2 |
| 4 | 6 | 8 |
| 3 | 7 | 1 |
| 7 | 5 | 1 |
| 4 | 7 | 3 |
| 7 | 4 | 8 |
| 7 | 6 | 5 |
| 6 | 7 | 8 |
| convex hull volume |
|---|
| 1 |
| convex hull area |
|---|
| 6 |
In 3-D space, the boundary of the convex hull consists of triangles. The indices matrix has three columns. Each row displays the indices of the three data points that form the vertices of a triangle. The first two rows are the triangles on the bottom face of the cube. The next two rows are triangles on the front face of the cube, and so on.
The remainder of the output shows that the volume of the cube is 1. The area is the sum of the six unit squares that form the faces of the cube.
By definition, any point inside the cube does not belong to the convex hull. For example, the following statements add the center of the cube to the input. However, the output remains identical to what is shown in Figure 41.
points = points // {0.5 0.5 0.5}; /* add the center of the cube to the input */
call convexhull(indices, va, points);
print indices;