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):

enter image description here

My questions are:

  1. 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.
  2. What are the algorithms to implement this, ideally in R?

closed as too broad by PolyGeo Nov 10 '18 at 2:58

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 2:31
  • As per the Tour there should be only one question asked per question. – PolyGeo Nov 10 '18 at 2: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 5:00
  • @mdsumner and there's actually a nice illustration of alphahul here: yihui.name/en/2010/04/… – Matifou Nov 11 '18 at 20:15

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:


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)

enter image description here

Not the answer you're looking for? Browse other questions tagged or ask your own question.