python: finding smallest distance between two points in two arrays

Question

I've got two lists containing a series of tuples (x,y), representing different points on a Cartesian plane:

a = [(0, 0), (1, 2), (1, 3), (2, 4)]
b = [(3, 4), (4, 1), (5, 3)]

I'd like to find the two points (one for each list, not within the same list) at the smaller distance, in this specific case:

[((2, 4), (3, 4))]

whose distance is equal to 1. I was using list comprehension, as:

[(Pa, Pb) for Pa in a for Pb in b \
if math.sqrt(math.pow(Pa[0]-Pb[0],2) + math.pow(Pa[1]-Pb[1],2)) <= 2.0]

but this uses a threshold value. Is there a way to append an argmin() somewhere or something like that and get only the pair [((xa, ya), (xb, yb))] smallest distance? Thanks.

You can create dictionary of pair and distance between them ...then u can select pair having min dist — Dark Matter
– Dark Matter, Commented Mar 3, 2016 at 9:31

DevShark · Accepted Answer · 2016-03-03 09:46:03Z

1

import numpy
e = [(Pa, Pb) for Pa in a for Pb in b]
e[numpy.argmin([math.sqrt(math.pow(Pa[0]-Pb[0],2) + math.pow(Pa[1]-Pb[1],2)) for (Pa, Pb) in e])]

Will use argmin as you suggested and return ((2, 4), (3, 4))

edited Mar 3, 2016 at 9:46

answered Mar 3, 2016 at 9:34

DevShark

9,18810 gold badges36 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mvelay Over a year ago

NameError: name 'numpy' is not defined, fix it by calling np.argmin

DevShark Over a year ago

No problem urgeo, happy to help :) Feel free to accept an answer by clicking on the checkmark if it solves your problem.

mvelay · Accepted Answer · 2016-03-03 09:33:56Z

1

Just use list comprehension and min as follows:

dist = [(Pa, Pb, math.sqrt(math.pow(Pa[0]-Pb[0],2) + math.pow(Pa[1]-Pb[1],2)))
        for Pa in a for Pb in b]

print min(dist, key=lambda x:x[2])[0:2]

answered Mar 3, 2016 at 9:33

mvelay

1,5201 gold badge10 silver badges23 bronze badges

Comments

MaxU - stand with Ukraine · Accepted Answer · 2016-03-03 11:05:26Z

1

Solution similar to DevShark's one with a few optimization tricks:

import math
import itertools
import numpy as np

def distance(p1, p2):
    return math.hypot(p2[0] - p1[0], p2[1] - p1[1])

a = [(0, 0), (1, 2), (1, 3), (2, 4)]
b = [(3, 4), (4, 1), (5, 3)]

points = [tup for tup in itertools.product(a, b)]

print(points[np.argmin([distance(Pa, Pb) for (Pa, Pb) in points])])

answered Mar 3, 2016 at 11:05

MaxU - stand with Ukraine

212k37 gold badges402 silver badges436 bronze badges

Comments

Kramer84 · Accepted Answer · 2020-04-13 13:46:00Z

0

You could also use the scipy.spatial library with the following :

import scipy.spatial as spspat
import numpy as np
distanceMatrix = spspat.distance_matrix(a,b)
args = np.argwhere(distanceMatrix==distanceMatrix.min())
print(args)

This will return you the following : array([[3, 0]]) , being the position of the points in each list. This should also work in any dimension.

answered Apr 13, 2020 at 13:46

Kramer84

476 bronze badges

Collectives™ on Stack Overflow

python: finding smallest distance between two points in two arrays

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related