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

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

Нет необходимости в сюжете или что-то в этом роде, просто сравните точки и найдите самые близкие два в списке.

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

Ответ 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)

Ответ 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, если они имеют дело с данными, которые лучше всего хранятся в числовом массиве, и хорошо знать, что инструменты доступны для дальнейшего использования.

Ответ 3

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

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

Ответ 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)

Ответ 5

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

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 примерно на треть быстрее, чем вычисление расстояния в рукописной питон-функции

Ответ 6

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

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

mInput не нужно объявлять заранее.
fList.append((x, y)) более pythonic, чем использование +=.

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

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

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