Calculate distances among a set of coordinates

user_10214448 0
Viewed 215

Is there a more efficient way to calculate the Euclidean distance among a given set of points?

This is the code I use:

def all_distances(position):
    distances = np.zeros((N_circles, N_circles))
    for i in range(N_circles):
        for j in range(i, N_circles):
            distances[i][j]=calculate_distance(position[i], position[j])
    return distances

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

position is an array containing the coordinates of N_circles points.

euclidean-distance numpy optimization python
3 Answers

You could use pdist and squareform from scipy

from scipy.spatial.distance import pdist, squareform

distances = pdist(position, metric="euclidean")
distance_matrix = squareform(distances)
user_13590580

You can use linalg to calculate the norm. Also you can define a function that calculate a hypersphere equation that include circle

import numpy as np

def distance(w, x, b=0):
    w_norm = np.linalg.norm(w,2)
    return abs(np.dot(w,x) + b) / w_norm
user_135850290

**2 may use some "power" subroutine. It may be faster to use a multiply.

If there is a hypot() in the library, use it.

You are keeping the distance from i to j (where i <= j). Maybe you want to store [j][i] also?

Alternatively, when looking up the distance you can use min(i,j) to 'max(i,j)`. (I can't tell whether this is less overhead.)

The code seems to compute [i][i]. Won't that always be zero? That is, perhaps you need range(i+1, N_circles). And you may or may not need to store 0.

Do all the distances change every time? If not, is there some way to recompute only the ones that changed? (This is a sample of "out of the box" thinking. There may be other tricks that can be used.)

Here's another...

Don't use SQRT at all. Instead, keep the squared distances. It is sufficient for deciding which is "closer" -- if that is all you need it for. (I used this out-of-the-box trick successfully in one project.)

How many times do you look up a 'distance' before recomputing it? If <= 'once', then don't bother pre-calculating. Simply calculate on the fly. (Actually the cutoff is a little more than 1.0, because of the overhead of creating and maintaining distance[])

user_17668310
Related