Найти ближайшую точку к группе 3D линий

Question

Эта проблема ставила меня в тупик в течение нескольких дней.

У меня есть группа линий, сформированная из некоторых данных, которая создает трехмерные линии вида:

P = a + d t

Где a - вектор положения, а d - вектор направления единицы.

Так что в основном я хочу найти ближайшую точку ко всем этим линиям, используя метод наименьших квадратов.Я не смог найти алгоритм онлайн или как реализовать его на Java.Я использую математическую библиотеку apache commons с использованием Vector3D или RealVectors для вычисления линейных уравнений.Поэтому любая помощь по алгоритму или примеру кода для решения этой проблемы будет полезна.

Answer 1

Расширенная версия ответа @YvesDaoust:

С учетом параметрической линии:

L(t) = A + t D

, где D - единичный вектор, т.е. D • D = 1

Расстояние от точки P до линии L равно:

t = D • (P - A)

Ближайшая точка P к набору линий в смысле наименьших квадратов сводит к минимуму сумму ошибок E:

E = (P - L(t))^2

E = (P - (A + tD))^2

E = (P - A - tD)^2

E = (P - A - (D • (P - A))D)^2

E = (P - A - (D•P - D•A)D)^2

E = (P - A - (D•P)D + (D•A)D)^2

E = (P - (D•P)D - A + (D•A)D)^2

E = (P - (D D^T)P - A + (D•A)D)^2

E = ((I - (D D^T)) P - A + (D•A)D)^2

E = (C x - b)^2

Где

C = I - (D D^T)
x = P
b = A - (D•A)D

Где «I» - единичная матрица 3x3. Решение наименьших квадратов:

C^T C x = C^T b

Другой способ получить ту же систему - взять производную уравнения:

E = (P - A - tD)^2

E = P•P - 2 P•A - 2t P•D + A•A + 2t A•D + t^2

Взяв производную по P и упрощая, мы получим (не забывайте применять правило цепочки, когда берете производную от «t», так как она является функцией от P):

dE/dP = 2(P - A  - ((P - A) • D) D)

Приравнивая это к нулю:

dE/dP = 0

2(P - A  - ((P - A)•D) D) = 0

P - ((P - A)•D) D = A

P - (P•D) D + (A•D) D = A

P - (P•D) D = A - (A•D) D

P - (D D^T) P = A - (A•D) D

(I - D D^T) P = A - (A•D) D

Где «I» - это единичная матрица 3x3. Это опять-таки линейная система вида C x = b.

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

Sum(C^T C) x = Sum(C^T b)

Итак, наконец:

x = Sum(C^T C)^-1 Sum(C^T b)

Answer 2

Предполагая, что вы хотите минимизировать сумму квадратов расстояний до линий, и предполагая, что WLOG векторы d являются единицами, общее квадратное расстояние составляет

Σ (( ap ) ² - ( ap . d ) ²)

, где сумма берется за все ( a , d ) строк.

Градиент этого выражения равен

Σ (2 ap - 2 ( ap . * 1025).* d ) d )

и, отменив его, мы получим линейную систему в p .

Answer 3

В конце концов я нашел хорошее решение этой проблемы для моего сценария с использованием анализа основных компонентов и просто написал о них, поэтому подумал, что добавлю сюда ссылки, чтобы показать, как я это сделал:

http://jamesdpeters.com/principal-component-analysis-fitting-a-straight-line-in-3d/