CODEWITHSUNDEEP
python
AspirationZ
AspirationZ

Reputation: 39

PYTHON - Distance between closest pair in a list

How do you go about writing a function that analyzes a list or coordinate pairs, selects with pair is the closest using the distance formula, and then only returns that distance d.

Example input and output:

>>>function([[x1,y1],[x2,y2],[x3,y3]])
>>>d

Upvotes: 0

Views: 2655

Answers (2)

vaultah
vaultah

Reputation: 46563

As I said the similar question was asked here. Here's the solution

a = [(5, 3), (9, 0), (4, 6), (2, 2), (0, 0)]

from math import sqrt


def function(a):
    distances = []
    def compute(fp, sp):
        return sqrt((fp[0]-sp[0])**2 + (fp[1] - sp[1])**2)

    for p in a:
        b = a[:]
        b.remove(p)
        distances.append(compute(p, min(b, key=lambda x: compute(x, p))))

    return min(distances)


print(function(a))

Output: 2.8284271247461903, that's equal to sqrt(8), because (2-0)2+(2-0)2 == 8

Upvotes: 1

Pi Marillion
Pi Marillion

Reputation: 4674

A simple brute force approach like the one shown on the Wikipedia article Sukrit links to, but with a small efficiency increase:

def min_dist(pair_list):
    n = len(pair_list)
    new_min_dist = float('inf')
    for i in xrange(n):
        for j in xrange(i + 1, n):
            new_x_dist = pair_list[i][0] - pair_list[j][0]
            new_y_dist = pair_list[i][1] - pair_list[j][1]
            new_min_dist = min(new_x_dist * new_x_dist + new_y_dist * new_y_dist, new_min_dist)
    return new_min_dist ** 0.5

There are a few efficiency additions here:

  • Saving square root for the end so it's only used once (square root and exponentiation are expensive).
  • Using ** 0.5 instead of math.sqrt, because for floats, exponentiation is faster than square root.
  • Using multiplication instead of ** 2, since exponentiation is much more expensive than multiplication.
  • Only considering each pair once (Wikipedia's example also does this).
  • xrange uses less memory, and doesn't have to allocate blocks, so it's slightly faster than range, provided there are fewer than about 32000 points. (Python 3 syntax will differ.)

Upvotes: 1

Related Questions