R：从点云中找到一个形状(R: Find a shape from a point cloud)

R：从点云中找到一个形状(R: Find a shape from a point cloud)

我有一个像下面这样的点云

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)

将它们视为动物的gps运动坐标。 我想找到点（动物）所覆盖的空间区域。 最明显的解决方案是凸壳，产生这样的：

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

但这不是我要找的结果。 运动区域不是封闭的几何形状，而是一种回旋镖形状。 凸壳覆盖了许多未被动物覆盖的区域，从而过高估计了该区域。 我正在寻找这样的东西：

当然，这是一个提供想法的模拟数据集。 原始数据集在点云中具有更多的点和不同的几何形状。 我在思考DBSCAN或最小跨度网络，但它们并不是很有效。

我不确定如何在几何上或数学上描述这个。 如果有人对如何处理这个问题有任何想法（即使它不是一个完整的解决方案），我将非常感激。 如果有人对这个问题有更好的称号，那也会很好:-)谢谢。

更新------------------------------------------------- ---------------

（最小生成树）MST的图。 我认为这可能是正确的方向。

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

I have a point cloud like such below

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:

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:

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)

最满意答案

试试alphahull

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

尽管如此，纯粹的几何技巧对于动物追踪数据很少有用。 它太临时不适用于其他情况，没有任何关于时间成分或有关环境的信息或位置的不确定性或点样本和真实轨道等之间的关系等。

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.