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).
开发者_JAVA技巧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)]

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)

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.

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

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

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)

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))

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