r - 是否可以根据彼此之间的距离重新排列 GPS 点

Question

我有一系列从开放街道 map 数据中获得的 GPS 点。 如果我从这些点创建跟踪，结果看起来像是这些点不符合“顺序”

我尝试过的一种方法是:使用 TSP 来订购这些点，如下所述:

Order Points with TSP

我做错了什么？ 也许有一个更简单/不同的解决方案可能吗？

这是示例数据和我的 TSP 代码:

library(TSP)

trace <-
  structure(
    list(
      counter = 1:29,
      lon = c(
        11.8296776,
        11.8296602,
        11.8296602,
        11.8296602,
        11.8296673,
        11.8296697,
        11.829711,
        11.8297067,
        11.8296776,
        11.830006,
        11.8299073,
        11.8298583,
        11.8298363,
        11.8297687,
        11.8297067,
        11.8310606,
        11.8310617,
        11.8310268,
        11.8309893,
        11.8309043,
        11.8307988,
        11.8305494,
        11.8302034,
        11.8301046,
        11.830006,
        11.8309893,
        11.8310215,
        11.8310483,
        11.8310606
      ),
      lat = c(
        48.1080396999118,
        48.1082178999118,
        48.1083925999117,
        48.1085890999117,
        48.1087772999116,
        48.1088399999116,
        48.1091400999115,
        48.1077663999119,
        48.1080396999118,
        48.1064633999122,
        48.1067714999121,
        48.1069627999121,
        48.107048999912,
        48.1074419999119,
        48.1077663999119,
        48.1033010999129,
        48.1034692999129,
        48.1037970999128,
        48.1040262999128,
        48.1042792999127,
        48.1045636999126,
        48.1051546999125,
        48.1059033999123,
        48.1061551999123,
        48.1064633999122,
        48.1025808999131,
        48.1027420999131,
        48.103014399913,
        48.1033010999129
      )
    ),
    row.names = c(NA,-29L),
    class = c("data.table", "data.frame"))

xytsp<-ETSP(trace)
xytour <- solve_TSP(xytsp)
reordered_trace <- trace[xytour, ]
reordered_trace$counter<-NULL
reordered_trace<-rowid_to_column(reordered_trace, "counter")
writeGPX(x =as.data.frame(reordered_trace),filename = "reordered_trace",type = "t" )

结果:

这是我想要的:

更新:一种似乎很有前途的方法:

trace$counter<-NULL
my.dist <- function(p1 = c(x,y), p2 = c(0,0)) sqrt((p1[1]-p2[1])^2 + (p1[2] - p2[2])^2)
names(trace) <- c("x", "y")
dists.to.origin <- apply(as.data.frame(trace), 1, my.dist)

reordered_trace <- trace[order(dists.to.origin),]
names(reordered_trace) <- c("lon", "lat")
reordered_trace<-rowid_to_column(reordered_trace, "counter")
writeGPX(x =as.data.frame(reordered_trace),filename = "reordered_trace",type = "t" )

这种方法有效，但仅适用于短线:

更新: 遗憾的是，Paul 的方法也没有奏效:

最终更新: 提供的两种解决方案都适用于这条短踪迹。 在较长的跟踪上，它们也可以工作，但计算时间 会增加很多。我尝试过的一种解决方案是将跟踪分成短片段，然后将 TSP 应用于它们..这使得操作更快，但会产生错误的结果，因为 TSP 需要查看所有点才能创建正确的跟踪。

Answer 1

我不确定下面的代码是否适合您，但我针对问题中的特定数据尝试了这种方式(通过选择 control 参数的起点来实现)

library(geosphere)
library(TSP)

setorder(trace, lat) # sort coordinates by `lat`
tsporder <- solve_TSP(ETSP(trace[, -1]), method = "NN", control = list(start = 1)) # add `start` into `control` to specify the starting point, i.e., the point with the lowest `lat`
tour <- trace[tsporder]

并绘制它

plot(trace$lon, trace$lat, pch = 20, col = "red", xlab = "Longitude", ylab = "Latitude")
lines(trace$lon[tsporder], trace$lat[tsporder], col = "blue")