CODEWITHSUNDEEP
pythongeolocationgpsmaps
Blackecho
Blackecho

Reputation: 1290

Compute distance in meters of sequence of GPS coordinates in Python.

I have a list of GPS coordinates belonging to the same street. I would like to use this list to estimate the length of the street in meters.

I know I can use Haversine formula to compute the distance in meters between two coordinates, but I still have two problems:

  1. The sequence is not sorted in any way, so consecutive points in the list can be basically anywhere along the street.
  2. GPS coordinates are not aligned at the center of the street, but can be anywhere along the width of the street.

To solve the problem I need to sort the sequence of coordinates using some criterion and to align them along the center of the street. But I cannot find an accurate solution to neither of these issues.

How can I go about solving this problem?

Upvotes: 3

Views: 1195

Answers (4)

MrE
MrE

Reputation: 20768

Original answer for an assume straight street:

Your points all fit in a rectangle defined by (min(lat),min(long) , max(lat), max(long))

Assuming the street is much longer than wide, a very simple and good approximation of the length is the diagonal of the rectangle.

You just need to be careful about the points across the meridian, where you need to adjust to avoid a round-trip around the earth.

EDIT:

if you want to be able to follow a street/road, you will need to add TIME to your geo-coordinates. Otherwise you will always have cases where a polyfit won't work.

Look at this road:

enter image description here

Upvotes: 0

Antimony
Antimony

Reputation: 2240

GPS coordinates means that you have two pieces of information: the location at some length down the street, and the location at some point in the width of the street.

Since you're only interested in computing the length of the street, find the coordinate that corresponds to the length (that would be the coordinate with the largest "spread", assuming the length is longer than the width), sort them, and then just find the difference between the minimum and maximum values.

Here's a simplified example. Suppose the points on the grid are the coordinates you have.

enter image description here

You are only interested in the distance in one direction. Assume that is the X axis in this case. Then you only care about the distance between the X-coordinates of C and F, regardless of the Y-coordinates of any of the points.

Update: My previous answer wrongly assumed that the street is aligned along a particular coordinate. For more general street orientations, you can sort the points along any one coordinate, and find the distance between the first and last point. This is just a heuristic and the points could likely lie along a diagonal of the street.

For a better estimate, Mikael N's approach of fitting a least squares line to estimate the mid point would work well.

Upvotes: 3

Oleh Rybalchenko
Oleh Rybalchenko

Reputation: 8039

The problem given is a particular case of a traveling salesman problem (TSP). So you may use one of the algorithms for this sort of problem.

If you don't care about accuracy, solutions from other answers are more suitable. But for optimal solution you can use determinstic algorithms like Branch And Bound (if the dataset is not so huge). For approximated - evolutionary algorithms like Genetic.

Upvotes: 1

Mikael M
Mikael M

Reputation: 81

Mathematically thinking, and to solve your first problem, I'd suggest first approximating the "probable street midline" by basically fitting ordinary least squares to get a linear regression line from the points. You could then count the shortest path of the points to the line, and finally somehow approximate the length using them.

There's probably a good estimation heuristic based on the first and last point on the street added with the amount of points, especially if the points can be expected to be taken at random. Do you have an idea on how to estimate the length once you've got the line figured out?

Upvotes: 2

Related Questions