Вычисление кратчайшего расстояния между двумя строками (линейные сегменты) в 3D

Я параметризовал бы оба линейных сегмента для использования одного параметра каждый, связанный между 0 и 1, включительно. Тогда найдите различие и между функциями строки и между использованием что как целевая функция в проблеме линейной оптимизации с параметрами как переменные.

Так говорят, что у Вас есть строка от (0,0,0) до (1,0,0) и другой от (0,1,0) до (0,0,0) (Да, я использую легкие). Строки могут быть параметризованы как (1*t, 0*t, 0*t), где t находится в [0,1] и (0*s, 1*s, 0*s), где s находится в [0,1], независимый от t.

Тогда необходимо минимизировать || (1*t, 1*s, 0) ||, где t, s лежат в [0,1]. Это - довольно простая проблема для решения.

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

, Если точка для каждой строки находится на исходном линейном сегменте, то Вы имеют ответ. Если точка для каждой строки не находится на исходном сегменте, то точка является одной из конечных точек исходных линейных сегментов.

Я отвечу на это с точки зрения matlab, но другие среды программирования могут использоваться. Я добавлю, что это решение допустимо для решения проблемы в любом количестве размеров (> = 3).

Предположите, что у нас есть два линейных сегмента в пространстве, PQ и RS. Вот несколько случайных наборов точек.

> P = randn(1,3)
P =
     -0.43256      -1.6656      0.12533

> Q = randn(1,3)
Q =
      0.28768      -1.1465       1.1909

> R = randn(1,3)
R =
       1.1892    -0.037633      0.32729

> S = randn(1,3)
S =
      0.17464     -0.18671      0.72579

Бесконечная строка PQ (t) легко определяется как

PQ(u) = P + u*(Q-P)

Аналогично, мы имеем

RS(v) = R + v*(S-R)

Посмотрите, что для каждой строки, когда параметр в 0 или 1, мы получаем одну из исходных конечных точек на возвращенной строке. Таким образом мы знаем что PQ (0) == P, PQ (1) == Q, RS (0) == R и RS (1) == S.

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

Затем, предположите, что мы смотрели вниз вдоль строки PQ. Мы можем найти точку наименьшего расстояния от RS линейного сегмента до бесконечной строки PQ? Это наиболее легко сделано проекцией в пустое пространство строки PQ.

> N = null(P-Q)
N =
     -0.37428     -0.76828
       0.9078     -0.18927
     -0.18927      0.61149

Таким образом пустой указатель (P-Q) является парой базисных векторов, которые охватывают двумерное подпространство, ортогональное к строке PQ.

> r = (R-P)*N
r =
      0.83265      -1.4306

> s = (S-P)*N
s =
       1.0016     -0.37923

По существу то, что мы сделали, должно спроектировать векторный RS в 2 размерных подпространства (плоскость), ортогональная к строке PQ. Путем вычитания от P (точка на строке PQ) для получения r и s мы удостоверяемся, что бесконечная строка проходит через источник в этой плоскости проекции.

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

rs(v) = r + v*(s-r)

Вектор нормали к RS строки (v) даст нам, в чем мы нуждаемся. Так как мы уменьшили это до 2 размеров, потому что исходное пространство было 3-м, мы можем сделать это просто. Иначе я просто использовал бы пустой указатель снова. Этот небольшой прием работает в 2-м:

> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);

n является теперь вектором с единичной длиной. Расстояние от бесконечного RS строки (v) к источнику просто.

> d = dot(n,r)
d =
       1.0491

Посмотрите, что я, возможно, также использовал s, для получения того же расстояния. Фактическое расстояние является брюшным прессом (d), но как оказалось, d был положителен здесь так или иначе.

> d = dot(n,s)
d =
       1.0491

Мы можем определить v от этого? Да. Вспомните, что источник является расстоянием d единиц от строки, которая соединяет точки r и s. Поэтому мы можем записать dn = r + v (s-r), для некоторого значения скаляра против Формы скалярное произведение каждой стороны этого уравнения с вектором (s-r), и решить для против.

> v = dot(s-r,d*n-r)/dot(s-r,s-r)
v =
       1.2024

Это говорит нам, что самый близкий подход RS линейного сегмента к источнику произошел вне конечных точек линейного сегмента. Таким образом, действительно самая близкая точка на RS к источнику была RS точки (1) = s.

Отступая из проекции, это говорит нам, что самая близкая точка на RS линейного сегмента к бесконечной строке PQ была точкой S.

Существует еще один шаг в анализе для взятия. Какова самая близкая точка на линейном сегменте PQ? Это указывает на падение в линейном сегменте, или это также выходит за пределы конечных точек?

Мы проектируем точку S на строку PQ. (Это выражение для Вас легко достаточно получено из подобной логики, как я сделал прежде. Обратите внимание здесь, что я использовал \, чтобы сделать работу.)

> u = (Q-P)'\((S - (S*N)*N') - P)'
u =
      0.95903

Посмотрите, что u находится в интервале [0,1]. Мы решили проблему. Точка на строке PQ

> P + u*(Q-P)
ans =
      0.25817      -1.1677       1.1473

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

> norm(P + u*(Q-P) - S)
ans =
        1.071

Конечно, все это может быть сжато во всего несколько коротких строк кода. Но это помогает развернуть все это для получения понимания того, как это работает.