Is it possible to rearrange GPS points based on distance to each other

Question

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:

Order Points with TSP

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.

Answer 1

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