Finding Great circle distances from points in dictionary

Question

I have the code below to calculate the distance between points on a map. My aim is to do the following:

• Have a start point and the locations from the locations dictionary,

• Loop through the dictionary and calculate the distance from all points to the start point.

• Find the location with the minimum distance from the start point.

• Then pair that location with the start point to form a pair of nodes to connect an edge.

• After doing that, make the minimum location as the new start point and remove it from the locations dictionary.

I will then go back to the previous step for the rest of the points.

I am currently able to get the distance from the first start point, but unable to loop through the rest of the points in the locations dictionary.

Any advice is highly appreciated.

from math import atan2, cos, sin, sqrt, radians

start = (43.82846160000000000000, -79.53560419999997000000)

locations = {
        'one':(43.65162010000000000000, -79.73558579999997000000),
        'two':(43.75846240000000000000, -79.22252100000003000000),
        'thr':(43.71773540000000000000, -79.74897190000002000000)
        }

cal_distances = {}

nodes = []

def dis():    

    y = len(locations)

    x = 0       

    while x != y:

        for key, value in locations.iteritems():                        
            d = calc_distance(value)
            cal_distances.setdefault(key,[])
            cal_distances[key].append(d)

        print cal_distances               

        min_distance = min(cal_distances, key = cal_distances.get)     

        if locations.has_key(min_distance):
            for ky, val in locations.iteritems():
                if ky == min_distance:
                    start = val   
            locations.pop(ky)                
        x = x+1  

    print locations

    print nodes

def calc_distance(destination):
     """great-circle distance between two points on a sphere from their longitudes and latitudes"""
    lat1, lon1 = start
    lat2, lon2 = destination
    radius     = 6371 # km. earth

    dlat = radians(lat2-lat1)
    dlon = radians(lon2-lon1) 

    a = (sin(dlat/2) * sin(dlat/2) + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon/2) * sin(dlon/2))
    c = 2 * atan2(sqrt(a), sqrt(1-a))
    d = radius * c

    return d

dis()

Answer 1

Your code as it stands is quite confusing. I think what you are trying to achieve is:

start = (43.82846160000000000000, -79.53560419999997000000)

locations = {'one':(43.65162010000000000000, -79.73558579999997000000),
             'two':(43.75846240000000000000, -79.22252100000003000000),
             'thr':(43.71773540000000000000, -79.74897190000002000000)}

def dis(start, locations):

    nodes = []       

    while locations:
    # until the dictionary of locations is empty

        nearest = min(locations, key=lambda k: calc_distance(start, locations[k]))
        # find the key of the closest location to start

        nodes.append((start, locations[nearest]))
        # add a tuple (start, closest location) to the node list

        start = locations.pop(nearest)
        # remove the closest location from locations and assign to start

    return nodes

def calc_distance(start, destination):
    # ...

nodes = dis(start, locations)

Note that I have made start an explicit argument to calc_distance, and start and locations explicit arguments to dis - wherever possible, don't rely on scope for access to variables. The output I get in nodes is:

[((43.8284616, -79.53560419999997), (43.7177354, -79.74897190000002)), 
 ((43.7177354, -79.74897190000002), (43.6516201, -79.73558579999997)), 
 ((43.6516201, -79.73558579999997), (43.7584624, -79.22252100000003))]