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

Question

У меня есть два сегмента линии: X1, Y1, Z1 - X2, Y2, Z2 и X3, Y3, Z3 - X4, Y4, Z4

Я я пытаюсь найти кратчайшее расстояние между двумя сегментами.

Я искал решение в течение нескольких часов, но все они работают с линиями, а не с линейными сегментами.

Любые идеи о том, как это сделать, или о каких-либо источниках фуллеров?

Answer 1

Один базовый подход - это то же самое, что вычислять кратчайшее расстояние между двумя строками, за одним исключением.

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

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

Для конкретного образца, см:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm

Более конкретно:

http://softsurfer.com/Archive/algorithm_0106/algorithm_0106.htm#dist3D_Segment_to_Segment()

Answer 2

Я хотел бы параметризовать оба сегмента, чтобы использовать один параметр каждый, связанный между 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]. Это довольно простая проблема.

Answer 3

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

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

Answer 4

Я отвечу на это в терминах 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 (т) легко определяется как

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 

Таким образом, нулевой (PQ) представляет собой пару базисных векторов, которые охватывают два мерное подпространство, ортогональное к линии 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-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. Поэтому можно записать д п = R + v (SR), при некотором значении скалярного ст. Форма скалярного произведения каждой части этого уравнения с вектором (SR), и решить для ст.

> 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 

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

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

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

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

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

Answer 5

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

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.

Answer 6

Сначала найдите самый близкий подход. Линия сегментов соединяется между их протяженными линиями. Назовем это LineSeg BR.

Если BR.endPt1 падает на LS1, а BR.endPt2 падает на LS2, вы закончили ... просто вычислите длину BR.

Если мост БР пересекает LS1, но не LS2, использовать более короткий из этих двух расстояний: smallerOf (DIST (BR.endPt1, LS2.endPt1), Dist (BR.endPt1, LS2.endPt2))

Если мост BR пересекает LS2, но не LS1, используйте более короткий из этих двух расстояний: lessOf (dist (BR.endPt2, LS1.endPt1), dist (BR.endPt2, LS1.endPt2))

Если ни один из этих условия сохраняются, самое близкое расстояние - это самое близкое сопряжение конечных точек на противоположных линиях Segs.