Я отвечу на это в терминах 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-м, мы можем сделать это просто. В противном случае, я бы просто использовал null снова. Этот маленький трюк работает в 2-й:
> n = (s - r)*[0 -1;1 0];
> n = n/norm(n);
n теперь вектор с единицей длины. Расстояние от бесконечной линии rs (v) до начала координат простое.
> d = dot(n,r)
d =
1.0491
Видите, я мог бы также использовать s, чтобы получить то же расстояние. Фактическое расстояние - abs (d), но, как оказалось, здесь все равно было положительным.
> d = dot(n,s)
d =
1.0491
Можем ли мы определить V из этого? Да. Напомним, что начало координат - это расстояние d единиц от линии, соединяющей точки r и s. Поэтому мы можем записать d n = r + v (sr) для некоторого значения скаляра v. Сформировать точечное произведение каждой стороны этого уравнения с вектором (sr) и решить для v.
> 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
Конечно, все это можно сжать в несколько коротких строк кода. Но это помогает расширить все это, чтобы понять, как это работает.