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

Question

我有一组从 Open Streetmap 数据中获得的 GPS 点。 如果我从这些点中创建轨迹，结果看起来这些点是乱序的

我尝试的一种方法是：按照此处所述使用 TSP 订购这些点：

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" )

此方法有效但仅适用于短线：

更新： 可悲的是，保罗的方法也没有奏效：

Answer 1

好吧，我觉得我有值得尝试的东西：

然后按照您的示例代码创建数据框：

xytsp <- ETSP(trace)

xytsp <- insert_dummy(as.TSP(xytsp), label = "cut")
# this converts to a TSP
# then adds a 'dummy' node to the chart with 0 distance to all other nodes.  
# This is where we will cut to make it a one-way path.

xytour <- solve_TSP(xytsp, method = "farthest_insertion")
# the farthest_insertion method basically finds the end points of the graph (those with the longest distance between them) then
# works out an efficient way to slot the other nodes into the middle
# it is not foolproof for some shapes, but worth a try.

path <- cut_tour(xytour, "cut")
# cut the tour so it doesn't need a return.

reordered_trace <- trace[labels(path), ]

然后像上面一样继续根据需要导出/绘图。

请告诉我这是否适用于您的真实示例。

Answer 2

我不确定下面的代码是否适合你，但我这样试过

library(geosphere)
library(TSP)

tsporder <- solve_TSP(ETSP(trace[, -1]))
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")