Формула расстояния между двумя точками в списке

Question

Мне нужно взять созданный мной список, найти две ближайшие точки и распечатать их.Как я могу сравнить каждую точку в списке?

Нет необходимости строить графики или что-либо еще, просто сравните точки и найдите две самые близкие в списке.

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

Answer 1

Удобнее переписать вашу distance() функцию, чтобы взять два (x, y) кортежа в качестве параметров:

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

Теперь вы хотите перебрать все пары точек из вашего списка fList. Для этого удобна функция iterools.combinations():

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

Альтернативой является определение distance() для принятия пары точек в одном параметре

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

и использовать параметр key для встроенной функции min():

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

Answer 2

Я понимаю, что в этом вопросе есть библиотечные ограничения, но для полноты, если у вас есть N баллов в Nx2 Numpy ndarray (2D-система):

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

Я всегда стараюсь побудить людейиспользуйте numpy / scipy, если они имеют дело с данными, которые лучше всего хранить в числовом массиве, и полезно знать, что инструменты доступны для дальнейшего использования.

Answer 3

Это может сработать:

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]

как только цикл завершен, min_pair должна быть парой с наименьшим расстоянием.

Использование float () для разбора текста оставляет место для улучшения.

math.hypot примерно на треть быстрее, чем вычисление расстояния в написанной от руки функции Python

Answer 4

Ваш фиксированный код.Нет эффективного алгоритма, только перебор.

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)

Answer 5

Обратите внимание, что функция math.sqrt является медленной и, в этом случае, ненужной.Попробуйте сравнить расстояние в квадрате, чтобы ускорить его (сортировка расстояний и расстояния в квадрате всегда будет иметь одинаковый порядок):

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

Answer 6

Во-первых, некоторые примечания:

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

mВход не должен быть объявлен заранее.
fList.append((x, y)) более питоничен, чем использование +=.

Теперьу вас есть fList.Ваша функция расстояния может быть переписана так, чтобы она принимала 2 аргумента из двух кортежей (точек), которые я не буду здесь беспокоить.

Тогда вы можете просто написать:

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