Plot line from GPS points

Question

I have around 100 list of gps coordinates and I want to draw the line that each of those lists make.

One of the lists plotted using scatter, look somewhat like this:

Clearly there's a line there;

I tried several methods to sort the gps positions and plot them:

lats = []
lngs = []
with open(filename) as f:
    for line in f:
        lat, lng = line.split("\t")
        lats.append(float(lat))
        lngs.append(float(lng))

def sort_positions(position):
    return position[0]+position[1]

positions= zip(lngs, lats)
positions = sorted(poss, key=sort_positions)
for i, positionin enumerate(positions):
    lng, lat = position
    #plt.scatter(lng, lat)
    try:
        n_lng, n_lat = positions[i+1]
        plt.plot((lng, n_lng),(lat, n_lat), "b")
    except IndexError:
        pass

plt.show()

Sorting by Longitude

def sort_positions(position):
    return position[0]

Sorting by Latitude

def sort_positions(position):
    return position[1]

Sorting by Summing Both

def sort_positions(position):
    return position[0]+position[1]

If the line are mostly straight in one of the axis(latitude/longitude), it plots fine (some minor bumps are still showing)

Here's one of the lists that do plot fine, sorting by latitude.

I to only plot if the distance between the two points was lesser than 200~500 meters, but I endup with holes in the lines, since there's some missing data.

Probably I'm doing this wrong. Does anyone know how to plot this lines properly?

EDIT:

In response to rth answer:

The blue line is using his approach in this questions, the red one is using the method in his other answer.

Ignoring the fact that the red is closing the loop.

There are some limitations in both, first, the red one can't handle too many points, I had to to use 1/90 of the points for both, the blue one generates some weird sharp turns when the points are too clustered (the dark spots in the image), while the red one some weird curves in those places.

Answer 1

The easiest thing to do here would be to figure out why the GPS coordinates were mixed up in the first place and correct that.

If that's not possible, the only thing I can think of is a iterative algorithm, that takes a xy point and decides based on some criteria (e.g. distance, direction of consecutive points, etc) which point should go next.

Something along these lines,

import numpy as np
from scipy.spatial.distance import pdist, squareform

def find_gps_sorted(xy_coord, k0=0):
    """Find iteratively a continuous path from the given points xy_coord,
      starting by the point indexes by k0 """      
    N = len(xy_coord)
    distance_matrix = squareform(pdist(xy_coord, metric='euclidean'))
    mask = np.ones(N, dtype='bool')
    sorted_order = np.zeros(N, dtype=np.int)
    indices = np.arange(N)

    i = 0
    k = k0
    while True:
        sorted_order[i] = k
        mask[k] = False

        dist_k = distance_matrix[k][mask]
        indices_k = indices[mask]

        if not len(indices_k):
            break

        # find next unused closest point
        k = indices_k[np.argmin(dist_k)]
        # you could also add some criterion here on the direction between consecutive points etc.
        i += 1
    return sorted_order, xy_coord[sorted_order]

that you could use as,

 xy_coord = np.random.randn(10, 2)
 sorted_order, xy_coord_sorted = find_gps_sorted(xy_coord, k0=0)

although this may need to be extended.

For instance you could say that in addition to the nearest distance criteria, you don't want the trajectory to turn more then by 90° (if that's something that makes sense for buses) and ignore those points at every iteration. Essentially, you can add enough constraints in this algorithm to get the result you are looking for.

Edit: Since GPS coordinates has some uncertainty, the final step could be to smooth the resulting trace with B-spline interpolation using scipy.interpolate.splprep and playing with the s argument ( see related questions (1), (2))

Answer 2

I suspect that all the (nice but) weird plots (except the first one) are because you are trying to sort something which which doesn't allow alphabetic sorting.

There is no reason to plot each line segment separately either. Try to do just:

plt.plot(lngs, lats, 'b')

Here's a sample track I had laying around: I didn't scale the horizontal and vertical axis correctly, so the plot is elongated vertically (too high).

Answer 3

place each coord into an array(lat, long). place all coords into another array collection(array1, array2, ... arrayn)

sort collection array and then plot.