Ytdyklly

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.