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.

Usage

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

peelellipse(pts, keep = 0.9)

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 of the new hull as much as possible, while "distance" and "mahalanobis" remove the point that has the largest total distance to all points on and within the hull.

Details

Reduction of area is the only criterion that really is based the area of the ellipse and only uses points on the hull. The other methods are based on the distances to all points within and on the hull. In peelpoly, the distance can be either isometric Euclidean distance or Mahalanobis distance where the distance is evaluated with respect to the covariance ellipse of points in the polygon. Function peelellipse is based on 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. peelellipse and peelhull with criterion "mahalanobis" results have the same points on the perimeter of the shape.

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 March 28, 2024, 12:45 a.m.