26

I'm writing a small program and to improve efficiency, I need to be able to find the closest latitude and longitude in my array.

Assume you have the following code:

tempDataList = [{'lat': 39.7612992 , 'lon': -86.1519681}, 
                {"lat": 39.762241, "lon": -86.158436}, 
                {"lat": 39.7622292, "lon": -86.1578917}]

tempLatList = []
tempLonList = []

for item in tempDataList:
    tempLatList.append(item['lat'])
    tempLonList.append(item['lon'])

closestLatValue = lambda myvalue: min(tempLatList, key=lambda x: abs(x - myvalue))
closestLonValue = lambda myvalue: min(tempLonList, key=lambda x: abs(x - myvalue))

print(closestLatValue(39.7622290), closestLonValue(-86.1519750))

The result I get is:

(39.7622292, -86.1519681)

What it should be is (in this example, the last object in the list)

(39.7622292, -86.1578917)

I know how to get a single value's closest cell but, I would like to make the lambda function to consider both values but I'm not entirely sure how. Help?

booky99
  • 1,436
  • 4
  • 27
  • 45
  • Use `min` on the original list of dicts - no use in separating it into two lists - and use Pythagoras' theorem in your key function. – Alex Hall Dec 26 '16 at 22:11
  • You are correctly getting the lowest longitude value. You are separating out those values. Don't separate out the values, calculate the distance for the latitude and longitude *together*. – Martijn Pieters Dec 26 '16 at 22:11
  • just use euclidean distance -)) – marmeladze Dec 26 '16 at 22:11
  • @MartijnPieters, I realize they need to be computed together but I'm not entirely sure how. Can you show me? – booky99 Dec 26 '16 at 22:14
  • @booky99: see [Getting distance between two points based on latitude/longitude \[python\]](//stackoverflow.com/q/19412462) or [How can I quickly estimate the distance between two (latitude, longitude) points?](//stackoverflow.com/q/15736995) – Martijn Pieters Dec 26 '16 at 22:16
  • @MartijnPieters, this isn't a matter of calculating distance. This is a matter of finding the values closest to the sets found in my original array – booky99 Dec 26 '16 at 22:18
  • @booky99: yes, and you then need to calculate the distance between your target and each dictionary. – Martijn Pieters Dec 26 '16 at 22:19
  • @marmeladze, can you put that into code? – booky99 Dec 26 '16 at 22:25
  • sure, wait a minute. – marmeladze Dec 26 '16 at 22:42

3 Answers3

59

For a correct calculation of the distance between points on the globe, you need something like the Haversine formula. Using the Python implementation offered in this answer, you could code it like this:

from math import cos, asin, sqrt

def distance(lat1, lon1, lat2, lon2):
    p = 0.017453292519943295
    hav = 0.5 - cos((lat2-lat1)*p)/2 + cos(lat1*p)*cos(lat2*p) * (1-cos((lon2-lon1)*p)) / 2
    return 12742 * asin(sqrt(hav))

def closest(data, v):
    return min(data, key=lambda p: distance(v['lat'],v['lon'],p['lat'],p['lon']))

tempDataList = [{'lat': 39.7612992, 'lon': -86.1519681}, 
                {'lat': 39.762241,  'lon': -86.158436 }, 
                {'lat': 39.7622292, 'lon': -86.1578917}]

v = {'lat': 39.7622290, 'lon': -86.1519750}
print(closest(tempDataList, v))

Haversine formula

The formula is given on Wikipedia as follows:

              1 − cos()  
     hav() = ──────────  
                  2

...where is either the difference in latitude (), or the difference in longitude (). For the actual angle between two points, the formula is given as:

     hav() = hav(₂ − ₁) + cos(₁)cos(₂)hav(₂ − ₁)

So that becomes:

              1 − cos(₂ − ₁)                 1 − cos(₂ − ₁)
     hav() = ──────────────── + cos(₁)cos(₂)────────────────
                  2                                   2

The distance is calculated from that, using this formula (also on Wikipedia):

      = 2 arcsin(√hav())

In the above script:

  • p is the factor to convert an angle expressed in degrees to radians: π/180 = 0.017453292519943295...

  • hav is the haversine calculated using the above formula

  • 12742 is the diameter of the earth expressed in km, and is thus the value of 2 in the above formula.

trincot
  • 317,000
  • 35
  • 244
  • 286
  • 2
    Goodness gracious great balls of fire. Thats perfect. So fast too. It clocked in at 0.03 MS on an old laptop. thanks! – booky99 Dec 28 '16 at 01:21
  • Hi any one please mention what is p ,a , float value 0.017453292519943295 with unit and 0.5 with unit in the above answer – Jasir May 20 '21 at 07:38
  • 1
    @Jasir, I added a section with some explanations. Let me know if this clarifies it. – trincot May 20 '21 at 08:27
2

Also u can simple do:

import mpu
def distance(point1, point2):
    return mpu.haversine_distance(point1, point2)

def closest(data, this_point):
    return min(data, key=lambda x: distance(this_point, x))
Chiefir
  • 2,561
  • 1
  • 27
  • 46
  • Why does somebody disliked this solution? Explain, please what's wrong? – Chiefir Nov 17 '18 at 19:22
  • 2
    if you have like 1M points and you have to find closest point from them then this solution will not work. The correct solution is to create a kd-tree or ball-tree using available lat longs and then find closest point – abggcv Apr 17 '19 at 06:52
  • 1
    @abggcv yep, but OP said he writes a *small* program. so this will work for exact this case. – Chiefir Apr 17 '19 at 06:57
  • Well not sure if by *small* OP means the number of lines of code or size of available lat longs. I do not see anything wrong with your code for small number of lat longs. – abggcv Apr 17 '19 at 07:07
  • @Chiefir probably because you have to pip install an additional module vs doing it with built in math module instead. – radtek Apr 02 '22 at 15:39
0

if earth is plane,

from itertools import combinations
from math import sqrt

coords = [{'lat': 39.7612992 , 'lon': -86.1519681}, 
                {"lat": 39.762241, "lon": -86.158436}, 
                {"lat": 39.7622292, "lon": -86.1578917}]


def euclidean(l1, l2):
    return ((l1[0]**2)-(l2[0]**2)) + ((l1[1]**2)-(l2[1]**2)) 

pairs = [j for j in combinations([i.values() for i in coords], 2)]
pairs.sort(key= lambda x: euclidean(*x))
print pairs[-1]
marmeladze
  • 6,468
  • 3
  • 24
  • 45