Ttykuu

I am extracting 10 lat/long points from Google Maps and placing these into a text file. The program should be able to read in the text file, calculate the haversine distance between each point, and store in an adjacency matrix. The adjacency matrix will eventually be fed to a 2-opt algorithm, which is outside the scope of the code I am about to present.

The following code is functional, but extremely inefficient. If I had 1000 points instead of 10, the adjacency matrix would need 1000 x 1000 iterations to be filled. Can this be optimized?

import csv
from haversine import haversine
import matplotlib.pyplot as plt
import numpy as np


def read_two_column_file(file_name):
 with open(file_name, 'r') as f_input:
 csv_input = csv.reader(f_input, delimiter=' ', skipinitialspace=True, )
 long = []
 lat = []
 for col in csv_input:
 x = float(col[0]) # converting to float
 y = float(col[1])
 long.append(x)
 lat.append(y)

 return long, lat


def display_points(long, lat):
 plt.figure()
 plt.ylabel('longitude')
 plt.xlabel('latitude')
 plt.title('longitude vs latitude')
 plt.scatter(long, lat)
 plt.show()


def main():
 long, lat = read_two_column_file('latlong.txt')

 points = []
 for i in range(len(lat)):
 coords = tuple([lat[i], long[i]]) # converting to tuple to be able to perform haverine calc. 
 points.append(coords)

 hav = []
 for i in range(len(lat)):
 for j in range(len(long)):
 hav.append(haversine(points[i], points[j]))

 np.asarray(hav)
 adj_matrix = np.reshape(hav, (10, 10)) # reshaping to 10 x 10 matrix
 print(adj_matrix)

 display_points(long, lat)


main()

Sample Input:

35.905333, 14.471970
35.896389, 14.477780
35.901281, 14.518173
35.860491, 14.572245
35.807607, 14.535320
35.832267, 14.455894
35.882414, 14.373217
35.983794, 14.336096
35.974463, 14.351006
35.930951, 14.401137

Sample Output:

[[ 0. 1.15959635 5.15603243 12.15003864 12.66090817 8.06760374
 11.25481465 17.31108648 15.37358741 8.34541481]
 [ 1.15959635 0. 4.52227294 11.19223786 11.50131214 7.32033758
 11.72388583 18.35259685 16.41378987 9.29953014]
 [ 5.15603243 4.52227294 0. 7.44480948 10.26177912 10.15688933
 16.24592213 22.1101544 20.18967731 13.40020548]
 [12.15003864 11.19223786 7.44480948 0. 7.01813758 13.28961044
 22.25645098 29.42422794 27.49154954 20.48281039]
 [12.66090817 11.50131214 10.26177912 7.01813758 0. 9.22215871
 19.74293886 29.16680205 27.25540014 19.97465594]
 [ 8.06760374 7.32033758 10.15688933 13.28961044 9.22215871 0.
 10.66219491 21.06632671 19.24994647 12.24773666]
 [11.25481465 11.72388583 16.24592213 22.25645098 19.74293886 10.66219491
 0. 11.67502344 10.21846781 6.08016463]
 [17.31108648 18.35259685 22.1101544 29.42422794 29.16680205 21.06632671
 11.67502344 0. 1.93885474 9.20353461]
 [15.37358741 16.41378987 20.18967731 27.49154954 27.25540014 19.24994647
 10.21846781 1.93885474 0. 7.28280909]
 [ 8.34541481 9.29953014 13.40020548 20.48281039 19.97465594 12.24773666
 6.08016463 9.20353461 7.28280909 0. ]]

Plot:

More than half of your code is being used to convert from one data format to another (from two lat and long list to tuples and then from a list of lists to an array).

The easiest to understand version would be to use numpy.loadtxt:

def read_two_column_file(file_name):
 return np.loadtxt(file_name, delimiter=", ")

This is then a 2D numpy.array. However, this is actually a lot slower than it could be, so you could also use pandas.read_csv instead:

import pandas as pd

def read_two_column_file(file_name):
 return pd.read_csv(file_name, header=None).values

Which one is faster depends on the size of your file.

Now we need to modify the display_points function to work with this new data format:

def display_points(points):
 plt.figure()
 plt.ylabel('longitude')
 plt.xlabel('latitude')
 plt.title('longitude vs latitude')
 plt.scatter(points[:, 0], points[:, 1])
 plt.show()

Now for the actual calculation. First, you can use itertools.combinations_with_replacement to get all pairs of points. Then you can insert them directly into the correct row of an array:

from itertools import combinations_with_replacement

def main():

 points = read_two_column_file(file_name)

 adj_matrix = np.empty(len(points)**2)
 for i, (point1, point2) in enumerate(combinations_with_replacement(points, 2)):
 adj_matrix[i] = haversine(point1, point2)
 adj_matrix.reshape((len(points), len(points))

 print(adj_matrix)
 display_points(points)

This can probably be further improved by using numpy.meshgrid to get the combinations of points and using a vectorized version of the haversine function.

I am trying to Extract an adjacency matrix distance from points on a map (latitude and longitude) in Python, can you share the optimized code?