Подгоните отрезок к набору точек - PullRequest
Новая
       23

Подгоните отрезок к набору точек

0 голосов
/ 12 апреля 2020

Я пытаюсь вписать отрезок в набор точек, но у меня проблемы с поиском алгоритма для него. У меня есть отрезок 2D-линии L и набор точек 2D C. L можно представить любым подходящим способом (мне все равно), например, вектором поддержки и определения, двумя точками, линейным уравнением с левой и правой границей ... Единственное, что важно, это то, что линия имеет начало и конец, так что это не бесконечно.

Я хочу вписать L в C, чтобы сумма всех расстояний от c до L (где c - это точка в C) минимизирована. Это проблема наименьших квадратов, но я (думаю) не могу использовать полиномиальную подгонку, потому что L - это только сегмент. Моим математическим знаниям в этой области немного не хватает, поэтому любые советы по дальнейшему чтению также будут оценены.

Вот иллюстрация моей проблемы:

1

Оранжевая линия должна соответствовать синим точкам, чтобы сумма квадратов расстояний каждой точки до линии была минимальной. Я не возражаю, если решение на другом языке или не код вообще, если я могу извлечь из него алгоритм.

Поскольку это больше математический вопрос, я не уверен, если это нормально для SO или должно быть перенесено в перекрестный проверенный или математический обмен.

Ответы [ 2 ]

0 голосов
/ 13 апреля 2020

Это решение относительно похоже на уже опубликованное здесь, но я думаю, что оно несколько более эффективно, элегантно и понятно, поэтому я опубликовал его, несмотря на сходство.

Как уже было написано, min ( Формула max (...)) затрудняет аналитическое решение этой проблемы, поэтому scipy.optimize подходит хорошо.

Решение основано на математической формулировке расстояния между точкой и конечным отрезком обозначено в https://math.stackexchange.com/questions/330269/the-distance-from-a-point-to-a-line-segment

import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import minimize, NonlinearConstraint


def calc_distance_from_point_set(v_):
    #v_ is accepted as 1d array to make easier with scipy.optimize
    #Reshape into two points
    v = (v_[:2].reshape(2, 1), v_[2:].reshape(2, 1))

    #Calculate t* for s(t*) = v_0 + t*(v_1-v_0), for the line segment w.r.t each point
    t_star_matrix = np.minimum(np.maximum(np.matmul(P-v[0].T, v[1]-v[0]) / np.linalg.norm(v[1]-v[0])**2, 0), 1)
    #Calculate s(t*)
    s_t_star_matrix = v[0]+((t_star_matrix.ravel())*(v[1]-v[0]))

    #Take distance between all points and respective point on segment
    distance_from_every_point = np.linalg.norm(P.T -s_t_star_matrix, axis=0)
    return np.sum(distance_from_every_point)

if __name__ == '__main__':

    #Random points from bounding box

    box_1 = np.random.uniform(-5, 5, 20)
    box_2 = np.random.uniform(-5, 5, 20)
    P = np.stack([box_1, box_2], axis=1)
    segment_length = 3
    segment_length_constraint = NonlinearConstraint(fun=lambda x: np.linalg.norm(np.array([x[0], x[1]]) - np.array([x[2] ,x[3]])), lb=[segment_length], ub=[segment_length])
    point = minimize(calc_distance_from_point_set, (0.0,-.0,1.0,1.0), options={'maxiter': 100, 'disp': True},constraints=segment_length_constraint).x
    plt.scatter(box_1, box_2)
    plt.plot([point[0], point[2]], [point[1], point[3]])

Пример результата:

enter image description here

0 голосов
/ 13 апреля 2020

Вот предложение в python. Расстояние между точками и линией вычисляется на основе предложенного здесь подхода: Подгонка отрезка к набору точек

Тот факт, что отрезок имеет конечную длину, что накладывает использование функций min и max или if тестов, чтобы увидеть, нужно ли нам использовать перпендикулярное расстояние или расстояние до одной из конечных точек, делает действительно трудным (невозможным?) получение аналитического c решения .

Таким образом, предлагаемое решение будет использовать алгоритм оптимизации, чтобы приблизиться к наилучшему решению. Он использует scipy.optimize.minimize, см .: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

Поскольку длина сегмента фиксирована, у нас есть только три степени свободы. В предлагаемом решении я использую координаты x и y начальной точки сегмента и наклон сегмента в качестве свободных параметров. Я использую функцию getCoordinates, чтобы получить начальную и конечную точку сегмента из этих 3 параметров и длины.

...