How to Interpolate Lat/Long Points (Route) between Two Lat Long Points-CodePudding

Lets say we have two addresses that are provided. I grabbed two random ones from the web below:

# Google headquarters:
google_lat = 37.422131
google_lon = -122.084801

# Apple headquarters
apple_lat = 37.33467267707233
apple_lon = -122.0089722675975

Now, lets say I'd like to interpolate a series of points between these two addresses. Maybe for starters a simple linear interpolation (or one that takes into account the spherical nature of the Earth) would work. In practice, a road route like provided via Google Maps would work if I could obtain an array of lat/longs for every n miles between each point. Might there be a REST API to obtain points between two addresses?

Just to get started on some ideas, how could I start approaching a task like this if I cannot go the API approach above? Bare minimum I would want is an array of lat/longs between each address with the points therein.

An example in Python would be nice but a language agnostic discussion is welcome too. Thanks.

CodePudding user response：

You offered a pair of (x1, y1) and (x2, y2) locations, with a line segment connecting them.

Compute a pair of deltas:

delta_x = x2 - x1
delta_y = y2 - y1

Now use parametric form of equation for line segment to interpolate. Let t vary from 0 .. 1 in step sizes as small as you like, and emit

(x1   t * delta_x, y1   t * delta_y)

for your interpolated points.

CodePudding user response：

Here is a basic linear interpolation example for starters.

import matplotlib.pyplot as plt
import numpy as np

fig, ax = plt.subplots()

# Google headquarters:
google_lat = 37.422131
google_lon = -122.084801

# Apple headquarters
apple_lat = 37.33467267707233
apple_lon = -122.0089722675975

# latitude is the x-coordinate
# longitude is the y-coordinate
# lets say we wanted to figure out a series of points between the two given with linear interpolation

latitudes = np.linspace(apple_lat, google_lat, 10)  # ten points
longitudes = (google_lon - apple_lon)/(google_lat - apple_lat)*(latitudes - apple_lat)   apple_lon

ax.plot(latitudes, longitudes, marker='o')
ax.set_xlabel('Latitude')
ax.set_ylabel('Longitude')

for x, y in zip(latitudes, longitudes):
    print(x, y)

plt.show()

Output:

Points Between:

37.33467267707233 -122.0089722675975
37.34439026850873 -122.01739768230888
37.354107859945145 -122.02582309702028
37.36382545138155 -122.03424851173166
37.37354304281796 -122.04267392644306
37.38326063425437 -122.05109934115444
37.392978225690776 -122.05952475586584
37.40269581712718 -122.06795017057722
37.412413408563594 -122.07637558528862
37.422131 -122.084801

But like you said, you need to account for the curvature of the earth, which means there is an extra z-axis to deal with. This requires further research and more honing on your linear algebra skills as this will certainly require some sort of transform from the x-y plane to the three dimensional space.

CodePudding user response：

Shapely may be a library worth looking into if you're going to be working a lot with geometries:

You can also project the points to a map, so that the earth's curvature is accounted for. Documentation on how that's done can be found here.

import shapely
from shapely.geometry import Point, LineString
from shapely.ops import interpolate
import numpy as np

# Google headquarters:
google_lat = 37.422131
google_lon = -122.084801

# Apple headquarters
apple_lat = 37.33467267707233
apple_lon = -122.0089722675975

google = Point(google_lat, google_lon)
apple = Point(apple_lat, apple_lon)

line = LineString([google, apple])

pts = []
for div in np.arange(0.1,1,0.1):
   pts.extend(line.interpolate(div, normalized=True).coords[:])

print(pts)

Output:

[(37.41338516770723, -122.07721812675975), (37.404639335414466, -122.0696352535195),
 (37.3958935031217, -122.06205238027925), (37.38714767082893, -122.054469507039),
 (37.37840183853616, -122.04688663379875), (37.369656006243396, -122.0393037605585),
 (37.36091017395063, -122.03172088731824), (37.35216434165786, -122.024138014078),
 (37.343418509365094, -122.01655514083775)]