Centroid of the minimum convex polygon

Question

I have the occurrence points of a species across an area. I want to calculate the centroid of the minimum convex polygon encompassing all occurrence points of this species. Could anyone tell me how to do this in R?

Answer 1

First note that the centroid of a convex polygon is not equal to the centroid of its vertices except in special cases such as when the polygon is a triangle. (If you actually wanted the centroid of the vertices rather than the centroid of the polygon then use sapply(ch[c("x", "y")], mean) in terms of ch computed below or colMeans(X[ix, ]) in terms of ix calculated in the last section.)

To get the centroid divide up the convex hull polygon's area into triangles (Delaunay triangularization), compute the centroid and area of each triangle and then take the weighted average of the centroids using the areas as the weights.

voronoi.mosaic in the tripack package will provide the indexes of the vertices of the triangles and the areas of the triangles. In its output p1, p2 and p3 are the indexes into the input X of vertices of the triangles and area is the corresponding areas. From that we calculate x and y as the coordinates of the centroids of the triangles. Then in the line following their calculation we take their weighted mean to get the overall centroid, cen. Finally we plot everything.

library(tripack)

set.seed(43)

# test data
n <- 25
X <- matrix(rnorm(2 * n), ncol = 2)

vm <- voronoi.mosaic(xy.coords(X))
x <- with(vm, rowMeans(cbind(X[p1, 1], X[p2, 1], X[p3, 1])))
y <- with(vm, rowMeans(cbind(X[p1, 2], X[p2, 2], X[p3, 2])))
cen <- apply(cbind(x, y), 2, weighted.mean, vm$area)  # centroid of conv hull

tri <- tri.mesh(xy.coords(X)) # triangularization
ch <- convex.hull(tri) # ch$i gives indexes of vertices of conv hull

# plot points & Delauney triangularization, conv hull (red) and centroid (red)
plot(tri)
lines(X[c(ch$i, ch$i[1]), ], col = "red", lwd = 2)
points(cen[1], cen[2], col = "red", pch = 20, cex = 2)

(continued after plot)

deldir

An alternative to tripack is to use the deldir package to get the centroid. The deldir function provides in its output del.wts which is the amount to weight each of the input points such that the weighted average of them is the centroid. cen.dd is equal up to floating point approximation to cen above and the plot is also similar. chull is from the base of R.

library(deldir)

dd <- deldir(xy.coords(X))
cen.dd <- with(dd$summary, sapply(list(x, y), weighted.mean, del.wts))

# plot points & triangularization, compute & plot conv hull (red) and 
#  centroid (red)
plot(dd, wlines = "triang")
ix <- chull(X)
lines(X[c(ix, ix[1]), ], col = "red", lwd = 2)
points(cen.dd[1], cen.dd[2], col = "red", pch = 20, cex = 2)

Update

Have completely revised answer.

Answer 2

As G. Grothendieck points out, the centroid of the polygon is not the mean of the vertices. The formulas for the centroid of a convex polygon are not difficult and I haven't seen them posted:

set.seed(42)
pts <- matrix(rnorm(40, 5, 1), 20, 2)
plot(pts)
# The centroid of the data points
points(t(pts.mn), pch=8, col="darkgreen", cex=2)
verts <- chull(pts)
poly <- pts[verts,]
polygon(poly)
cent <- colMeans(poly)
# The centroid of the vertices
points(t(cent), pch=8, col="blue", cex=2)

Now the formulas for area and centroid. These assume that the polygon is closed (first row is the same as the last row) and that the points traverse the polygon counter-clockwise:

poly <- rbind(poly, poly[1, ])
n <- nrow(poly)
x <- rev(poly[, 1])
y <- rev(poly[, 2])
i <- 1:(n-1)
# Area of the polygon
A <- sum(c(x[i] * y[i+1] - x[i+1] * y[i])) / 2
# Coordinates of the centroid
Cx <- sum((x[i] + x[i+1]) * (x[i] * y[i+1] - x[i+1] * y[i])) / (6 * A)
Cy <- sum((y[i] + y[i+1]) * (x[i] * y[i+1] - x[i+1] * y[i])) / (6 * A)
# The centroid of the polygon
points(Cx, Cy, pch=8, col="red", cex=2)