CODEWITHSUNDEEP
pythonlistcoordinatesdistance
Andrea De Cillia
Andrea De Cillia

Reputation: 9

How to calculate distance between coordinates stored in a list?

so I have two lists which each contain multiple points, like so :

list1 = [(1,2),(3,4),(5,6),(7,8),...]
list2 = [(1,1),(2,2),(3,3,),...]

(these are just examples, as my normal data contains up to 10.000 points)

I managed to calculate the distance between each point of one list to each point in the second list, with these lines of code :

dist = []
from math import sqrt

def distance(p1, p2):
    return sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

for p1 in list1:
    for p2 in list2:
        d = distance(p1, p2)
        dist.append(d)

(Note: dist = [] and dist.append are used for storing the calculated distances in a list)

But infact for my analysis I only need the distances from the point in list1 to the nearest point in list2!

To make this more understandable i plotted the points from my list here: Plotted points from list

As you can see, for each blue point I only want to calculate the distance to the nearest red point, and not all of them. (I thought this could be done by calculating the distance from one blue point to all of the red ones, and then just storing the smallest distance, an/or discarding the other ones)

Does anyone have an idea how this could be done ?

Upvotes: 0

Views: 2571

Answers (2)

Serge Ballesta
Serge Ballesta

Reputation: 148910

As you said that the lists are large, it could be a nice use case for numpy if using it is an option. It is a (large) library optimised for numeric and array processing at C speed. Here you could do:

import numpy as np

list1 = [(1,2),(3,4),(5,6),(7,8)]
list2 = [(1,1),(2,2),(3,3,)]

# build numpy arrays
arr1 = np.array(list1).reshape((len(list1), 1, len(list1[0]))) # add a dimension to allow broadcasting
arr2 = np.array(list2)

d = arr1 - arr2              # compute element wise difference on a (4,3,2) array
d2 = d * d                   # squares of above elements
ds = np.sum(d2, axis=2)      # sum the individual coordinates => square of distances
dsn = np.min(ds, axis=1)     # min of (square of) distance along list1
dist = np.sqrt(dsn)          # array (4) of minimum distance from a point from list1 to a point from list2

# all the operation in one single line, same result
dist2 = np.sqrt(np.min(np.sum(np.power(arr1 - arr2, 2), axis=2), axis=1))

It gives for dist or dist2 (same values):

array([1.        , 1.        , 3.60555128, 6.40312424])

Not very useful for small arrays, because loading numpy is expensive, but it should be much quicker that pure python loops for large ones.

Upvotes: 0

Luke Storry
Luke Storry

Reputation: 6702

You can map through one list, passing in a lambda function that maps through the other list, and finds the min distance:

list(map(lambda x: min(map(lambda y: distance(x, y), list2)), list1))

or as a list comprehension:

[min((distance(x,y)) for y in list2) for x in list1]

Upvotes: 1

Related Questions