R: Compute Convex Hull of a Set of Points

chull {base}

R Documentation

Compute Convex Hull of a Set of Points

Computes the subset of points which lie on the convex hull of the set of points specified.

chull(x, y=NULL)

x, y

coordinate vectors of points. This can be specified as two vectors x and y, a 2-column matrix x, a list x with components x and y

xy.coords is used to intepret the specification of the points. The algorithm is that given by Eddy (1977).

‘Peeling’ as used in the S function chull can be implemented by calling chull recursively.

A vector giving the indices of the points lying on the convex hull, in clockwise order.

B. D. Ripley

Eddy, W. F. (1977) A new convex hull algorithm for planar sets. ACM Transactions on Mathematical Software, 3, 398-403.

Eddy, W. F. (1977) Algorithm 523. CONVEX, A new convex hull algorithm for planar sets[Z]. ACM Transactions on Mathematical Software, 3, 411-412.

X <- matrix(rnorm(2000), ncol=2)
plot(X, cex=0.5)
hpts <- chull(X)
hpts <- c(hpts, hpts[1])
lines(X[hpts, ])