r - Рассчитать кратчайшее расстояние между двумя точками в триангуляции Делоне

Question

В настоящее время я работаю с пространственными данными и применил триангуляцию Делоне к моим точкам данных. Я дополнительно рассчитал геодезические расстояния на эллипсоиде 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 * ( Wikipedia Link ). Может быть, это вам поможет. Вы можете заменить регулярно упорядоченные точки в евклидовой метрике точками Делоне в вашей коллекции точек. Затем всегда переходите к следующему соседу, который находится ближе всего к финишной точке.