Defining convex-hull of (clouds of) points using R?

Question

I have multiple (clouds of) points, and would like to take the outer envelope of these points. This will allow me to polygonize my points.

Using the convex-hull would help me, but in some cases, my shapes are not convex, and hence this convex-hull envelope contains large areas without any points. The question mark is a good example where one would not necessarily want a convex hull (from: link):

My questions are:

Is there a concept of non-convex hull? How is this called, and conceptualized? I guess that while it is easy to define a convex hull (it is unique), it is difficult to conceptualize a non-convex hull, as this won't necessarily be unique, so any definition will be harder/involve some free parameters.
What are the algorithms to implement this, ideally in R?

see the alphahull package, or bare triangulation (e.g. geometry::delaunayn) and cull out large/long triangles - alphahull is a generalization of very raw methods — mdsumner, Nov 10 '18 at 02:31
As per the [Tour] there should be only one question asked per question. — PolyGeo, Nov 10 '18 at 02:59
@PolyGeo I don't think asking about a concept as well as its implementation is that broad, many questions and answers follow (implicitly) that structure I feel — Matifou, Nov 10 '18 at 05:00
@mdsumner and there's actually a nice illustration of alphahul here: https://yihui.name/en/2010/04/alphahull-an-r-package-for-alpha-convex-hull/ — Matifou, Nov 11 '18 at 20:15

score 2 · Accepted Answer · answered Nov 10 '18 at 02:38

There are existing questions about clustering with good answers here Find clusters of points based distance rule and here How to cluster spatial data in R?.

For the actual hulling, the alg is called a 'concave hull', and package concaveman is your friend here. quick example with meuse:

library(sf)
library(concaveman)

data(meuse, package = "sp") # load data.frame from sp
meuse_sf = st_as_sf(meuse, coords = c("x", "y"), crs = 28992)

split_soil <- split(meuse_sf, meuse_sf$soil)
hulls <- lapply(split_soil, concaveman)
hulls <- do.call('rbind', hulls)

plot(meuse_sf['soil'], pch = 20, cex = 1, reset = FALSE, axes = T)
plot(hulls, add = TRUE, border = 'grey70', col = NA)

Defining convex-hull of (clouds of) points using R?

1 Answers1