Search code examples
rpolygonareapoint-cloudsconvex-hull

R: Find a shape from a point cloud


I have a point cloud like such below

enter image description here

df <- data.frame(x=c(2,3,3,5,6,2,6,7,7,4,3,8,9,10,10,12,11,12,14,15),
              y=c(6,5,4,4,4,4,3,3,2,3,7,3,2,3,4,6,5,5,4,6))
plot(df,xlab="",ylab="",pch=20)

Think of them as gps coordinates of movement by an animal. I would like to find the spatial area covered by the points (animal). The most obvious solution is a convex hull which produces this:

enter image description here

df1 <- df[chull(x = df$x,y=df$y),]
polygon(x = df1$x,df1$y)

But this is not the result I am looking for. The movement area is not a closed geometric shape, but rather a boomerang kind of shape. The convex hull covers a lot of area not covered by the animal thereby overestimating the area. I am looking for something like this:

enter image description here

Of course, this is a mock dataset to give an idea. The original datasets have lot more points and varying geometries in point cloud. I was thinking along the lines of DBSCAN or minimum spanning networks, but they don't quite work.

I am not sure how to describe this geometrically or mathematically. If anyone has any ideas on how to approach this (even if it's not a full solution), I would very much appreciate that. If anyone has a better title for this question, that would be nice too :-) Thanks.

Update ----------------------------------------------------------------

Plot of (minimum spanning tree) MST. I think this might be in the right direction.

library(ape)
d <- dist(df)
mstree <-mst(d)
plot(mstree, x1 = df$x, x2 = df$y)

enter image description here


Solution

  • Try alphahull

    library(alphahull)
    
    p <- ahull(df$x, df$y, alpha = 2.5)
    plot(p)
    

    Still, purely geometric tricks like this are rarely helpful for animal tracking data. It's too ad hoc to be applicable for other cases, doesn't have anything for the temporal component or information about the environment or the uncertainty of the locations or the relationship between the point samples and the real track etc etc.