У меня есть два сегмента: X1, Y1, Z1 - X2, Y2, Z2 и X3, Y3, Z3 - X4, Y4, Z4
Я пытаюсь найти кратчайшее расстояние между двумя сегментами.
Я искал решение в течение нескольких часов, но все они работают с линиями, а не с сегментами.
Любые идеи о том, как это сделать, или о любых источниках фуллеров?
Один базовый подход - это то же самое, что вычисление кратчайшего расстояния между двумя строками с одним исключением.
Если вы посмотрите на большинство алгоритмов поиска кратчайшего расстояния между двумя строками, вы обнаружите, что он находит точки в каждой ближайшей строке, а затем вычисляет расстояние от них.
Трюк, чтобы распространить это на сегменты (или лучи), заключается в том, чтобы увидеть, находится ли эта точка за пределами одной из конечных точек линии, и если да, используйте конечную точку вместо фактической ближайшей точки на бесконечной линии.
Для конкретного примера см.
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm
Более конкретно:
http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()
Я отвечу на это в терминах 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
Таким образом, null (P-Q) представляет собой пару базисных векторов, которые охватывают двумерное подпространство, ортогональное прямой PQ.
> r = (R-P)*N
r =
0.83265 -1.4306
> s = (S-P)*N
s =
1.0016 -0.37923
Существенно, что мы сделали, это проецировать вектор RS в двумерное подпространство (плоскость), ортогональное прямой PQ. Вычитая P (точку на линии PQ), чтобы получить r и s, мы гарантируем, что бесконечная линия проходит через начало координат в этой плоскости проектирования.
Таким образом, мы уменьшили это до нахождения минимального расстояния от линии rs (v) до начала координат (0,0) в плоскости проектирования. Напомним, что строка rs (v) определяется параметром v как:
RS(v) = R + v*(S-R)
Нормальный вектор к прямой rs (v) даст нам то, что нам нужно. Поскольку мы уменьшили это до 2 измерений, потому что исходное пространство было 3-d, мы можем сделать это просто. В противном случае я бы просто снова использовал 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 все равно положительно.
> d = dot(n,s)
d =
1.0491
Можем ли мы определить v из этого? Да. Напомним, что начало координат - это расстояние d единиц от линии, соединяющей точки r и s. Поэтому для некоторого значения скаляра v можно написать dn = r + v (s-r). Сопоставьте произведение точек каждой стороны этого уравнения с вектором (s-r) и решим для 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 легко получается из аналогичной логики, как и раньше. Обратите внимание, что я использовал\для выполнения работы.)
> 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
Конечно, все это можно сжать в несколько коротких строк кода. Но это помогает расширить все это, чтобы понять, как это работает.
Я хотел бы параметризовать оба сегмента линии, чтобы использовать один параметр каждый, связанный между 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]. Это довольно простая проблема для решения.
Как продлить сегменты линии на бесконечные линии и найти кратчайшее расстояние между двумя линиями. Затем найдите точки на каждой линии, которые являются конечными точками кратчайшего сегмента линии.
Если точка для каждой строки находится в исходном сегменте линии, тогда у вас есть ответ. Если точка для каждой строки не находится на исходном сегменте, то точка является одной из конечных точек исходного сегмента.
Нахождение расстояния между двумя конечными линиями, основанное на нахождении между двумя бесконечными линиями, а затем связанное бесконечными линиями с конечными линиями, не всегда работает. например, попробуйте эти точки
Q=[5 2 0]
P=[2 2 0]
S=[3 3.25 0]
R=[0 3 0]
На основе бесконечного подхода алгоритм выбирает R и P для расчета расстояния (расстояние = 2.2361), но где-то посередине R и S имеет более близкое расстояние до точки P. По-видимому, выбор P и [2 3.166] из линии R в S имеет меньшее расстояние 1,1666. Даже этот ответ может улучшиться путем точного вычисления и нахождения ортогональной линии от линии P до R S.
Сначала найдите ближайший подход Line Segment, соединяющий их расширенные линии. Позвольте называть этот LineSeg BR.
Если BR.endPt1 падает на LS1, а BR.endPt2 падает на LS2, вы закончили... просто вычислите длину BR.
Если мост BR пересекает LS1, но не LS2, используйте более короткие из этих двух расстояний: lessOf (dist (BR.endPt1, LS2.endPt1), dist (BR.endPt1, LS2.endPt2))
Если мост BR пересекает LS2, но не LS1, используйте более короткие из этих двух расстояний: lessOf (dist (BR.endPt2, LS1.endPt1), dist (BR.endPt2, LS1.endPt2))
Если ни одно из этих условий не выполняется, самое близкое расстояние - это самое близкое сопряжение конечных точек на противоположных линиях Seg.