CODEWITHSUNDEEP
pythonmath
morcutt
morcutt

Reputation: 3749

Distance formula between two points in a list

I need to take a list I have created and find the closest two points and print them out. How can I go about comparing each point in the list?

There isn't any need to plot or anything, just compare the points and find the closest two in the list.

import math # 'math' needed for 'sqrt'

# Distance function
def distance(xi,xii,yi,yii):
    sq1 = (xi-xii)*(xi-xii)
    sq2 = (yi-yii)*(yi-yii)
    return math.sqrt(sq1 + sq2)

# Run through input and reorder in [(x, y), (x,y) ...] format
oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # Original input list (entered by spacing the two points).
mInput = [] # Manipulated list
fList = [] # Final list
for o in oInput:
    mInput = o.split()
    x,y = float(mInput[0]), float(mInput[1])
    fList += [(x, y)] # outputs [(9.5, 7.5), (10.2, 19.1), (9.7, 10.2)]

Upvotes: 20

Views: 96135

Answers (7)

Yashraj Nigam
Yashraj Nigam

Reputation: 348

Many of the above questions suggest finding square root using math.sqrt which is slow as well as not a good approach to find square root. In spite of using such approach just recall the basic concepts from school: think of taking the square root of any positive number, x. The square root is then written as a power of one-half: x½. Thus, a fractional exponent indicates that some root is to be taken.

so rather than using math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

Use

def distance(a,b):
  euclidean_distance = ((b[0]-a[0])**2 + (a[1]-a[1])**2)**0.5
  return(euclidean_distance)

Hope it helps

Upvotes: 0

JoshAdel
JoshAdel

Reputation: 68682

I realize that there are library constraints on this question, but for completeness if you have N points in an Nx2 numpy ndarray (2D system):

from scipy.spatial.distance import pdist
x = numpy.array([[9.5,7.5],[10.2,19.1],[9.7,10.2]])
mindist = numpy.min(pdist(x))

I always try to encourage people to use numpy/scipy if they are dealing with data that is best stored in a numerical array and it's good to know that the tools are out there for future reference.

Upvotes: 12

Sven Marnach
Sven Marnach

Reputation: 601599

It is more convenient to rewrite your distance() function to take two (x, y) tuples as parameters:

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

Now you want to iterate over all pairs of points from your list fList. The function iterools.combinations() is handy for this purpose:

min_distance = distance(fList[0], fList[1])
for p0, p1 in itertools.combinations(fList, 2):
    min_distance = min(min_distance, distance(p0, p1))

An alternative is to define distance() to accept the pair of points in a single parameter

def distance(points):
    p0, p1 = points
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

and use the key parameter to the built-in min() function:

min_pair = min(itertools.combinations(fList, 2), key=distance)
min_distance = distance(min_pair)

Upvotes: 35

orlp
orlp

Reputation: 117681

Your fixed code. No efficient algorithm, just the brute force one.

import math # math needed for sqrt

# distance function
def dist(p1, p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)

# run through input and reorder in [(x, y), (x,y) ...] format
input = ["9.5 7.5", "10.2 19.1", "9.7 10.2"] # original input list (entered by spacing the two points)
points = [map(float, point.split()) for point in input] # final list

# http://en.wikipedia.org/wiki/Closest_pair_of_points
mindist = float("inf")
for p1, p2 in itertools.combinations(points, 2):
    if dist(p1, p2) < mindist:
        mindist = dist(p1, p2)
        closestpair = (p1, p2)

print(closestpair)

Upvotes: 2

HumanCatfood
HumanCatfood

Reputation: 1001

This might work:

oInput = ["9.5 7.5", "10.2 19.1", "9.7 10.2"]

# parse inputs
inp = [(float(j[0]), float(j[1])) for j in [i.split() for i in oInput]]

# initialize results with a really large value
min_distance = float('infinity')
min_pair = None

# loop over inputs
length = len(inp)
for i in xrange(length):
    for j in xrange(i+1, length):
        point1 = inp[i]
        point2 = inp[j]

        if math.hypot(point1[0] - point2[0], point1[1] - point2[0]) < min_distance:
            min_pair = [point1, point2]

once the loops are done, min_pair should be the pair with the smallest distance.

Using float() to parse the text leaves room for improvement.

math.hypot is about a third faster than calculating the distance in a handwritten python-function

Upvotes: 2

Aaron Dufour
Aaron Dufour

Reputation: 17505

Note that the math.sqrt function is both slow and, in this case, unnecessary. Try comparing the distance squared to speed it up (sorting distances vs. distance squared will always produce the same ordering):

def distSquared(p0, p1):
    return (p0[0] - p1[0])**2 + (p0[1] - p1[1])**2

Upvotes: 3

nmichaels
nmichaels

Reputation: 50941

First, some notes:

a**2 # squares a
(xi - xii)**2 # squares the expression in parentheses.

mInput doesn't need to be declared in advance.
fList.append((x, y)) is more pythonic than using +=.

Now you have fList. Your distance function can be rewritten to take 2 2-tuple (point) arguments, which I won't bother with here.

Then you can just write:

shortest = float('inf')
for pair in itertools.combinations(fList, 2):
    shortest = min(shortest, distance(*pair))

Upvotes: 0

Related Questions