r-计算delaunay三角测量中2个点之间的最短距离

Question

目前我正在处理空间数据，并在数据点上应用了Delaunay三角测量。我还计算了WGS84椭球上三角测量中每条边(2点之间的连接(的测地线距离。现在，我将在生成的图中搜索每2个点之间的最短路径，并计算路径距离。因此，最短距离应计算为所有边距离的总和。

下面是一个最小的工作示例：

library(deldir)
set.seed(31)
x <- runif(100)
y <- runif(100)
d <- deldir(x, y)  #preforms tesselation & Delaunay triangulation
#Calculate edge distances (for reasons of simplicity I calculate here Euclidean distances)
geodists <- NULL
for (i in 1:nrow(d$delsgs)) {
geodists[i] <- sqrt((x[d$delsgs[i,5]] - x[d$delsgs[i,6]])^2 + (y[d$delsgs[i,5]] - y[d$delsgs[i,6]])^2)
}
#Plot data
plot(d, wlines="triang")

然而，我不知道如何对我创建的deldir对象执行最短路径搜索。因此，如果你能为我的问题提供一些解决方案，我将非常高兴：

1. 如何识别点A和B之间的最短路径中涉及哪些边
2. 然后如何有效地计算路径距离矩阵

非常感谢您的帮助！

Answer 1

有一些路径查找算法。其中之一是A*(维基百科链接(也许这对你有帮助。可以用点集合的delaunay点替换欧几里得度量中的规则有序点。然后总是去到离终点最近的下一个邻居那里。