在字典中寻找点的大圆距离

Question

我有下面的代码来计算地图上各点之间的距离。我的目标是做以下工作：

• 有一个起点和位置字典的位置，
• 循环遍历字典并计算从所有点到起始点的距离。
• 找到与起点的最小距离的位置。
• 然后将该位置与起始点配对，形成一对节点以连接边缘。
• 完成此操作后，将最小位置作为新的起点，并将其从locations字典中删除。

然后，我将回到前一步，为其余的要点。

我目前能够得到距离从第一个起点，但无法循环通过其余的点在位置字典。

任何建议都是非常感谢的。

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))]