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)
library(geometry)
polyarea(df$x, df$y)
[1] 18.5
不过这需要正确的顺序。
试试 alphahull
library(alphahull)
p <- ahull(df$x, df$y, alpha = 2.5)
plot(p)
不过，像这样的纯几何技巧对动物追踪数据很少有帮助。它太临时了，无法适用于其他情况，没有任何时间成分或有关环境的信息或位置的不确定性或点样本与真实轨迹之间的关系等。
您可能需要考虑一种基于 TSP 启发式的方法。当所有点都相关时，这种方法接近理想。
下面是一种从 insertion heuristic for TSP 扩展而来的简单方法，它可能可行，但它的复杂度为 O(N^2) 或最差，除非您对数据结构相当小心。 link对凸包法的启发式描述如下
Convex Hull, O(n^2*log^2(n))
- Find the convex hull of our set of cities, and make it our initial subtour.
- For each city not in the subtour, find its cheapest insertion (as in step 3 of Nearest Insertion). Then chose the city with the least
cost/increase ratio, and insert it.
- Repeat step 2 until no more cities remain.
在这种情况下，城市是数据点，并且由于目标不是连接到所有数据点而是获得一般形状，因此需要一个额外的步骤来确定数据点何时要么不应添加或不再需要并且可以删除。但问题是，尚不清楚哪些点将被视为无关紧要。
这个 TSP Test Data 网站应该让您了解该启发式的结果，以及您希望如何从结果 "tour" 中删除您认为无关紧要的点。
虽然可能的解决方案是跟踪原始凸包，并将两个相邻包点之间的距离增加限制为包点之间原始距离的某个（相对较小）倍数，这类似于 alpha hull 的工作方式。这将通过限制两个船体点之间可以行进的距离来防止诸如底部的形状 TSP Test Case BCL380 之类的形状。
我有一个像下面这样的点云
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)
library(geometry)
polyarea(df$x, df$y)
[1] 18.5
不过这需要正确的顺序。
试试 alphahull
library(alphahull)
p <- ahull(df$x, df$y, alpha = 2.5)
plot(p)
不过，像这样的纯几何技巧对动物追踪数据很少有帮助。它太临时了，无法适用于其他情况，没有任何时间成分或有关环境的信息或位置的不确定性或点样本与真实轨迹之间的关系等。
您可能需要考虑一种基于 TSP 启发式的方法。当所有点都相关时，这种方法接近理想。
下面是一种从 insertion heuristic for TSP 扩展而来的简单方法，它可能可行，但它的复杂度为 O(N^2) 或最差，除非您对数据结构相当小心。 link对凸包法的启发式描述如下
Convex Hull, O(n^2*log^2(n))
- Find the convex hull of our set of cities, and make it our initial subtour.
- For each city not in the subtour, find its cheapest insertion (as in step 3 of Nearest Insertion). Then chose the city with the least cost/increase ratio, and insert it.
- Repeat step 2 until no more cities remain.
在这种情况下，城市是数据点，并且由于目标不是连接到所有数据点而是获得一般形状，因此需要一个额外的步骤来确定数据点何时要么不应添加或不再需要并且可以删除。但问题是，尚不清楚哪些点将被视为无关紧要。
这个 TSP Test Data 网站应该让您了解该启发式的结果，以及您希望如何从结果 "tour" 中删除您认为无关紧要的点。
虽然可能的解决方案是跟踪原始凸包，并将两个相邻包点之间的距离增加限制为包点之间原始距离的某个（相对较小）倍数，这类似于 alpha hull 的工作方式。这将通过限制两个船体点之间可以行进的距离来防止诸如底部的形状 TSP Test Case BCL380 之类的形状。