Optimized function for returning changing distances in Cartesian plane

Question

Bit of a challenging Python problem for me. I have from one to six points in constant motion but only in a Cartesian(2D) plane. I need to create a function that would calculate all the possible distances between these points and return a collection of some sort with theses distances and corresponding points. So for a maximum of six points there would be 15 unique distances that need calculating (see diagram)

I assume I can use this for calculating the actual distance

import math

def calcDist(x1,y1,x2,y2):
     dist = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
     return dist       

distance = calcDist(x1, y1, x2, y2)

What I need help with is how to best create the input and output. ie I know I need to pass from 1 to 6 possible points (x,y coordinates and associated point reference) . So does this suggest 1-6 dictionary objects would first need to be created?

And as well the returned collection needs both the calculated distances and associated point pairs for each distance. Since I'm more concerned with minimum distances sorting on the distance value would be optional.

Lastly since this is constantly running, optimization is important. Any feedback appreciated.

This [answer provides a more efficient method using cdist](https://stackoverflow.com/questions/33760643/finding-squared-distances-beteen-n-points-to-m-points-in-numpy) — DarrylG, Apr 28 '20 at 13:22
@DarrylG but it needs scipy, which might be an overkill to install just to calculate 15 distances — bb1950328, Apr 28 '20 at 13:26
@Sadap--True unless this is just a toy problem and the real problem is on a larger dataset. If so, then cdist provides better performance than pure Python code as other answers suggest such as [Why cdist from scipy.spatial.distance is so fast?](https://stackoverflow.com/questions/51630056/why-cdist-from-scipy-spatial-distance-is-so-fast) — DarrylG, Apr 28 '20 at 13:32

score 0 · Accepted Answer · answered Apr 28 '20 at 13:35

This is not optimized, because I don't know what "fast enough" is, and neither do you, since you haven't actually implemented this and found the naive solution to be too slow :)

As always, make a working implementation, see if it's fast enough, and if profiling reveals it to be too slow, then optimize. The working implementation can then be your ground truth to be sure your optimized implementation is doing the same thing (write tests!).

import math
import random

# little handier to have the points as objects
# you may want to add functionality later
class Point(object):
    def __init__(self, x, y):
        super(Point, self).__init__()
        self.x = x
        self.y = y

    def __repr__(self):
        # just nicer to have a human-readable representation
        return f"<Point x={self.x}, y={self.y}>"

# generate the same random points each time
random.seed(1)
# generate 6 random points
points = [Point(random.randint(-10,10), random.randint(-10, 10)) for dummy in range(6)]

# find distance between two points
def find_distance(point_a, point_b):
    dist = math.sqrt((point_a.x - point_b.x)**2 + (point_a.y - point_b.y)**2)
    return dist

# find all the point-pair distances
# outer dict is keyed by point, inner dicts are keyed by distance
def find_distances(points):
    output = {}
    # loop through the points
    for point_a in points:
        distances = {}
        # loop through the points again to find the distances
        for point_b in points:
            # bail fast to avoid comparing the points to themselves
            if point_a is point_b:
                continue
            distance = find_distance(point_a, point_b)
            # inner dict stores distance as key and companion point as value
            distances[distance] = point_b
        output[point_a] = distances
    return output

all_distances = find_distances(points)
print (all_distances)

score -1 · Answer 2 · answered Apr 28 '20 at 13:25

dict supports tuple keys:

points = [  # just an example
    (1, 2),
    (3, 4),
    (4, 8),
    (2, 9),
    (5, 2),
    (7, 3),
]

distances = {}

for i1, p1 in enumerate(points):
    for i2, p2 in enumerate(points):
        if p1 != p2:
            distances[(i1, i2)] = calcDist(*p1, *p2)

# getting distance between first and third points
print(distances[(0, 2)])

Optimized function for returning changing distances in Cartesian plane

2 Answers2