Iteration of a 2d list in Python, distance between two locations

Question

I have a 2d list (list of lists) in which I have several locations in the U.S. and their associated latitudes and longitudes. Here's an example of the first few cities:

"Millersville","CA",35.303850,-118.457860    #(city 1)
"Millersville","IL",39.451150,-89.158140     #(city 2)
"Millersville","IN",39.853100,‐86.091650     #(city 3)
"Millersville","MD",39.059550,-76.648020     #(city 4)

I'm attempting to setup an iteration that will go through and calculate the distance between city 1 and city 2 using their latitudes and longitudes, then save that value to loc1_loc2, then move on and calculate the distance between city 1 and city 3, save value to loc1_loc3, etc, etc. It needs to do this for all possible combinations and save each value. Here's what I was tinkering with, but I simply can't get it to go through the iteration:

for i in range(len(places)):
    dlat = math.radians(float(places[i][2])-float(places[0][2]))
    dlon = math.radians(float(places[i][3])-float(places[0][3]))
    a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(float(places[0][2]))) \
        * math.cos(math.radians(float(places[i][2]))) * math.sin(dlon/2) * math.sin(dlon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = radius * c
    loc0_loc0 = d * 0.621371

print loc0_loc0

What am I doing wrong and how do I get this iteration setup to go through all my cities (unknown number of them depending on which list I'm using) and calculate all the possible distances between each and every one?

I appreciate the help!

Answer 1

Something like this might work...

resultDict = {}
for startCity in places:
    for endCity in places:
        startLocation = startCity[0] + ' ' + startCity[1]
        endLocation = endCity[0] + ' ' + endCity[1]
        resultLocations = [startLocation, endLocation]
        resultId = ','.join(resultLocations.sort())

        if startLocation == endLocation or resultId in resultDict:
            continue

        dlat = math.radians(float(startCity[2])-float(endCity[2]))
        dlon = math.radians(float(startCity[3])-float(endCity[3]))
        a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(float(endCity[2]))) \
            * math.cos(math.radians(float(startCity[2]))) * math.sin(dlon/2) * math.sin(dlon/2)
        c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
        d = radius * c
        resultDict[resultId] = d * 0.621371

print resultDict

Answer 2

Your code is very difficult to read, which obscures what you are trying to do. With four locations there are (4 x (4-1)) / 2 = 6 distances you need, but the number grows rapidly as the place count increases. Here I cop out and compute the full 4 x 4 distance matrix - obviously I am doing some redundant work which you may be able to eliminate.

Your subscripting makes it very difficult to understand what is going on, so instead I use unpacking assignments in the for loops to avoid it and bind each element of the data to a name.

import math
places = [
    ["Millersville", "CA", 35.303850, -118.457860],    #(city 1)
    ["Millersville", "IL", 39.451150, -89.158140 ],    #(city 2)
    ["Millersville", "IN", 39.853100, -86.091650 ],     #(city 3)
    ["Millersville", "MD", 39.059550, -76.648020 ]      #(city 4)
]
# One of the minus signs was weird
radius = 6371 # Mean radius in Km
distances = []
for nameA, stateA, latA, longA in places:
    dists_row = []
    for nameB, stateB, latB, longB in places:
        dlat = math.radians(latA-latB)
        dlon = math.radians(longA-longB)
        a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(latA)) \
            * math.cos(math.radians(latB)) * math.sin(dlon/2) * math.sin(dlon/2)
        c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
        d = radius * c
        distance = d * 0.621371
        dists_row.append(distance)
    distances.append(dists_row)

for row in distances:
    print(row)

This prints out

[0.0, 1626.6140655454842, 1789.8845362720158, 2295.8829666956335]
[1626.6140655454842, 0.0, 165.46706149552824, 669.3166714199295]
[1789.8845362720158, 165.46706149552824, 0.0, 506.5281329453448]
[2295.8829666956335, 669.3166714199295, 506.5281329453448, 0.0]

which is nicely symmetrical and reassuringly has zeroes in the diagonal, meaning I maybe didn't screw your formulae up as I was rewriting them. Here's a version that prints the results out rather than storing them in a matrix. In this one I only compute each distance once.

radius = 6371 # Mean radius in Km
for stnum, (nameA, stateA, latA, longA) in enumerate(places):
    for nameB, stateB, latB, longB in places[stnum+1:]:
        dlat = math.radians(latA-latB)
        dlon = math.radians(longA-longB)
        a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(latA)) \
            * math.cos(math.radians(latB)) * math.sin(dlon/2) * math.sin(dlon/2)
        c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
        d = radius * c
        distance = d * 0.621371
        print(nameA, stateA, "to", nameB, stateB, "is", distance, "miles")

from which the output is

Millersville CA to Millersville IL is 1626.6140655454842 miles
Millersville CA to Millersville IN is 1789.8845362720158 miles
Millersville CA to Millersville MD is 2295.8829666956335 miles
Millersville IL to Millersville IN is 165.46706149552824 miles
Millersville IL to Millersville MD is 669.3166714199295 miles
Millersville IN to Millersville MD is 506.5281329453448 miles