Compute Convex Hull of a Set of Points

Usage

chull(x, y=NULL)

Arguments

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

Description

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

Details

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.

Value

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

Author(s)

B. D. Ripley

References

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.

See Also

xy.coords,polygon

Examples

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

[Package Contents]