peelhull: Convex Hull Enclosing a Given Proportion of Points

In jarioksa/natto: An Extreme 'vegan' Package of Experimental Code

Convex Hull Enclosing a Given Proportion of Points

Description

Functions find a small convex hull or ellipse enclosing a given proportion of points. The functions work by removing points from the hull or ellipse one by one. The points are selected either so that the area of the remaining hull is reduced as much as possible at every step (de Smith, Goodrich & Longley 2007), or removing the point that has the maximal total distance to all remaining points or longest Mahalanobis distance to the group.

Usage

peelhull(pts, keep = 0.9, criterion = c("area", "distance", "mahalanobis"))

peelellipse(pts, keep = 0.9, criterion = c("area", "mahalanobis"))

Arguments

pts	Coordinates of points, a two-column matrix
keep	Proportion of points kept
criterion	Criterion to remove a point on the hull. "area" removes the point that reduces the area most, "distance" remove the point at the hull that has the largest total distance to all points on and within the hull, and "mahalanobis" remove the point with longest Mahalanobis distance to the centroid.

Details

Reduction of area is the only criterion that really is based the area. The other methods are based on the distances to all points within and on the hull or on the Mahalanobis distance. The functions only work in 2D.

The algorithms are naïve, and stepwise removal of single points does not guarantee smallest possible final hull. Two outlier points close to each other can protect each other from removal, but removing both together would give a large reduction of the hull. The "distance" criterion produces circular hulls, but "mahalanobis" will better preserve the original elongation of the configuration, although it rarely gives smaller areas than "area" criterion.

Value

A two-column matrix of coordinates of peeled hull or ellipse defining that can be plotted with polygon, with attributes "centre" and "area".

Author(s)

Jari Oksanen

References

de Smith, M.J., Goodchild, M.F. & Longley, P.A. (2007). Geospatial analysis: A comprehensive guide to principles, techniques and software tools. Matador.

Examples

x <- matrix(c(rnorm(100), rnorm(100, sd=2)), nrow=100, ncol=2)
op <- par(mar=c(0,0,1,0), mfrow=c(2,2))
## show first ten dropped points and hull keeping 50% of points
for (crit in c("area", "distance", "mahalanobis")) {
   plot(x, asp = 1, main = crit, xlab="", ylab="", axes=FALSE)
   for (p in c(100:90, 50)/100)
       polygon(peelhull(x, keep=p, crit=crit),
               col = adjustcolor("blue", alpha.f=0.04))
}
plot(x, asp = 1, main = "ellipse", xlab="", ylab="", axes=FALSE)
for (p in c(100:90, 50)/100)
   polygon(peelellipse(x, keep=p), col=adjustcolor("blue", alpha.f=0.04))

par(op) # original graphical parameters

jarioksa/natto documentation built on Feb. 20, 2025, 3:29 p.m.