从字典中点计算大圆距离

Question

我有下面的代码是用来计算地图上点之间的距离。我的目标是：

• 先确定一个起始点和一个地点字典里的位置，

• 然后遍历这个字典，计算所有点到起始点的距离。

• 找出离起始点最近的位置。

• 然后把这个位置和起始点配对，形成一对节点，以便连接一条边。

• 完成后，把这个最近的位置设为新的起始点，并从地点字典中移除它。

接着我会回到之前的步骤，处理剩下的点。

目前我能计算出第一个起始点的距离，但无法遍历地点字典中的其他点。

任何建议都非常感谢。

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

你的代码现在看起来有点混乱。我觉得你想要实现的目标是：

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)

注意，我把 start 明确地作为 calc_distance 的一个参数，同时把 start 和 locations 也作为 dis 的明确参数——尽量不要依赖作用域来访问变量。我在 nodes 中得到的输出是：

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