英文:
Is it possible to rearrange GPS points based on distance to each other
问题
我有一个来自Open Streetmap数据的GPS点数组。
如果我使用这些点创建一个轨迹，结果看起来好像这些点是"无序的"。
我尝试过的一种方法是：按照这里描述的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需要看到所有点才能创建正确的轨迹。
英文:
I have an array of GPS points I get from Open Streetmap data.
If I create a trace out of these points the result looks like the points are out of "order"
One approach I tried is: to order those points with TSP as described here:
what am I doing wrong?
Is maybe a simpler/different solution possible?
Here is the example data and my code for 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" )
And the result:
Here is what I would like to have:
UPDATE: one approach that seems to be promising:
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" )
This approach works but only for short line:
UPDATE:
Sadly the approach by Paul approach did not worked either:
FNAL UPDATE:
Both provided solutions will work on this short trace.
On a longer trace they will also work but the calculation time
will increase very much. One solution to that I tried was to divide the trace in short pieces and then apply TSP to them.. which make the operation faster, yet produces the wrong result because TSP needs to see all the points to create a correct trace.
答案1
得分: 1
请问您要翻译的部分是以下内容吗？
"OK, I think I have something worth trying:
Follow your example code to create the data frame then:
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), ]
then continue as you did above to export/plot as required.
Please let me know if this works for your real examples."
英文:
OK, I think I have something worth trying:
Follow your example code to create the data frame then:
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), ]
then continue as you did above to export/plot as required.
Please let me know if this works for your real examples.
答案2
得分: 1
以下是您要翻译的代码部分：
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]
and plot it by
plot(trace$lon, trace$lat, pch = 20, col = "red", xlab = "Longitude", ylab = "Latitude")
lines(trace$lon[tsporder], trace$lat[tsporder], col = "blue")
希望这有所帮助。
<details>
<summary>英文:</summary>
I am not sure if the code below works for you in general, but I tried it this way with respect to your specific data in the question (doing by selecting a start point into `control` argument)
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]
and plot it by
plot(trace$lon, trace$lat, pch = 20, col = "red", xlab = "Longitude", ylab = "Latitude")
lines(trace$lon[tsporder], trace$lat[tsporder], col = "blue")
[![enter image description here][1]][1]
[1]: https://i.stack.imgur.com/oOi4h.png
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论