Алгоритм для нахождения точки пересечения двух 3D линейных сегментов

Большинство трехмерных линий не пересекаются. Надежный метод - найти самую короткую линию между двумя 3D линиями. Если длина самой короткой линии равна нулю (или расстояние меньше указанного вами допуска), вы знаете, что две исходные линии пересекаются.

Метод поиска кратчайшей линии между двумя трехмерными линиями, написанный Полом Бурком , резюмируется / перефразируется следующим образом:

Далее линия будет определяться двумя лежащими на ней точками, точка на прямой "a", определяемая точками P1 и P2, имеет уравнение

 Pa = P1 + mua (P2 - P1) 
 

аналогично точке на второй прямой " b ", определяемый точками P4 и P4 , будет записан как

 Pb = P3 + mub (P4 - P3) 
 

Значения mua и mub находятся в диапазоне от отрицательной до положительной бесконечности. . Отрезки между P1 P2 и P3 P4 имеют соответствующие mu от 0 до 1.

Есть два подхода к нахождению самого короткого отрезка между линиями " а "и" б ".

Первый подход:

Первый - записать длину отрезка линии , соединяющего две линии, а затем найти минимум. То есть минимизирует следующие

 || Pb - Pa || ^ 2 
 

Подстановка уравнений линий дает

 || P1 - P3 + mua (P2 - P1) - mub (P4 - P3) || ^ 2 
 

Вышеупомянутое можно затем развернуть в компонентах (x, y, z).

Есть условия, которые должны выполняться как минимум, производная с по mua и mub должна быть равна нулю. ... указанная выше функция имеет только один минимум и никаких других минимумов или максимумов. Затем эти два уравнения могут быть решены для mua и mub, фактических точек пересечения, найденных путем подстановки значений mu в исходные уравнения линии.

Подход второй:

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

 (Па - Pb) точка (P2 - P1) = 0 
 (Па - Pb) точка (P4 - P3) = 0 
 

Расширяя их, получим уравнение прямых

 (P1 - P3 + mua (P2 - P1) - mub (P4 - P3)) dot (P2 - P1) = 0 {{1 }} (P1 - P3 + mua (P2 - P1) - mub (P4 - P3)) dot (P4 - P3) = 0 
 

Раскладывая их в терминах координат (x, y, z ) ... результат будет следующим:

 d1321 + mua d2121 - mub d4321 = 0 
d1343 + mua d4321 - mub d4343 = 0 
 

где

 dmnop = (xm - xn) (xo - xp) + (ym - yn) (yo - yp) + (zm - zn) (zo - zp) 
 

Обратите внимание, что dmnop = dopmn

Наконец, решение для mua дает

 mua = (d1343 d4321 - d1321 d4343) / (d2121 d4343 - d4321 d4321) 
 

, а обратная подстановка дает mub

 mub = (d1343 + mua d4321) / d4343 
 

Этот метод был найден на веб-сайте Пола Бурка , который является отличным ресурсом по геометрии. Сайт был реорганизован, поэтому прокрутите вниз, чтобы найти тему.

Но нахождение точки пересечения для двух 3D отрезков не является, я боюсь.

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

Вы можете решить общие уравнения вручную и просто использовать свое решение, или решить его программно, используя, например, гауссову элеминацию.