Расстояние между линией, образованной двумя точками, до каждой другой точки, для каждой возможной линии

Question

Учитывая набор точек, для всех перестановок из 2 точек в наборе я хочу вычислить общее квадратное расстояние от каждой другой точки до линии, определенной этой парой.

Вот что у меня такfar:

import numpy as np
import itertools

def dist_point2line(a, b, c):
    return np.linalg.norm(np.cross(a-b, c-b))/np.linalg.norm(c-b)

points = np.array([(1,2), (2,3), (3,2), (0,4), (4,1), (3,3)])

pairs = itertools.permutations(points, 2)
distances = []
for (p2, p3) in pairs:
    total = 0
    for p1 in points:
        distance = dist_point2line(p1, p2, p3)
        total += distance*distance
    distances.append(total)

Проблема в том, что в настоящее время также рассчитывается расстояние до p2 и p3, которые, очевидно, равны нулю.Как я могу сделать это более эффективным?

Answer 1

Вместо того, чтобы переставлять ваши очки, переставьте индексы очков.Затем самый внутренний цикл может перебирать каждый индекс точки и исключать те, которые соответствуют любому в паре.

Что-то вроде:

for pair in itertools.permutations(range(0, len(points)), 2):
    p1, p2 = points[pair, :]
    total = 0
    for other in range(0, len(points)):
        if other in pair:
            continue
        p3 = points[other]
        distance = dist_point2line(p1, p2, p3)
        total += distance**2
    distances.append(total)

Также, чтобы повысить производительность, вы можете инициализировать переменную distances в виде пустого массива вместо списка:

n = len(points)
distances = np.zeros([n * (n-1)], dtype=np.float32)

Вам нужно немного исправить приведенный выше код:

for k, pair in enumerate(itertools.permutations(range(0, len(points)), 2)):
    total = 0
    ...
    distances[k] = total