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

Ответ 1

Я нашел решение: здесь.

Идея состоит в том, чтобы использовать векторную алгебру, чтобы использовать dot и cross просто вопрос до этого этапа:

a (V1 X V2) = (P2 - P1) X V2

и вычислить a.

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

Ответ 2

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

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

В дальнейшем линия будет определяться двумя лежащими на ней точками, а точка на линии "а", определяемая точками 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 в исходные уравнения линии.

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

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

(Pa - Pb) dot (P2 - P1) = 0
(Pa - Pb) dot (P4 - P3) = 0

Расширяя их, учитывая уравнение линий

( P1 - P3 + mua (P2 - P1) - mub (P4 - P3) ) dot (P2 - P1) = 0
( 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 = ( d1343 d4321 - d1321 d4343 ) / ( d2121 d4343 - d4321 d4321 )

и обратно заменив дает муб

mub = ( d1343 + mua d4321 ) / d4343

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

Ответ 3

// This code in C++ works for me in 2d and 3d

// assume Coord has members x(), y() and z() and supports arithmetic operations
// that is Coord u + Coord v = u.x() + v.x(), u.y() + v.y(), u.z() + v.z()

inline Point
dot(const Coord& u, const Coord& v) 
{
return u.x() * v.x() + u.y() * v.y() + u.z() * v.z();   
}

inline Point
norm2( const Coord& v )
{
return v.x() * v.x() + v.y() * v.y() + v.z() * v.z();
}

inline Point
norm( const Coord& v ) 
{
return sqrt(norm2(v));
}

inline
Coord
cross( const Coord& b, const Coord& c) // cross product
{
return Coord(b.y() * c.z() - c.y() * b.z(), b.z() * c.x() - c.z() * b.x(), b.x() *  c.y() - c.x() * b.y());
}

bool 
intersection(const Line& a, const Line& b, Coord& ip)
// http://mathworld.wolfram.com/Line-LineIntersection.html
// in 3d; will also work in 2d if z components are 0
{
Coord da = a.second - a.first; 
Coord db = b.second - b.first;
    Coord dc = b.first - a.first;

if (dot(dc, cross(da,db)) != 0.0) // lines are not coplanar
    return false;

Point s = dot(cross(dc,db),cross(da,db)) / norm2(cross(da,db));
if (s >= 0.0 && s <= 1.0)
{
    ip = a.first + da * Coord(s,s,s);
    return true;
}

return false;
}

Ответ 4

Я попытался ответить @Bill, и на самом деле он не работает каждый раз, что я могу объяснить. На основании ссылки в его коде. Пусть есть, например, эти два отрезка AB и CD.

A = (2,1,5), B = (1,2,5) и C = (2,1,3) и D = (2,1,2)

когда вы пытаетесь получить перекресток, он может сказать вам, что точка А (неверная) или пересечения нет (правильная). В зависимости от порядка размещения этих сегментов.

х = A+ (BA) с
х = C+ (DC) т

Билл решил за s, но так и не решил t. А поскольку вы хотите, чтобы эта точка пересечения находилась на обоих отрезках, s и t должны быть из интервала <0,1>. Что на самом деле происходит в моем примере, так это то, что только s, если из этого интервала и t -2. A лежит на линии, определенной C и D, но не на линейном сегменте CD.

var s = Vector3.Dot(Vector3.Cross(dc, db), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));

var t = Vector3.Dot(Vector3.Cross(dc, da), Vector3.Cross(da, db)) / Norm2(Vector3.Cross(da, db));

где da - BA, db - DC, а dc - CA, я просто сохранил имена, предоставленные Биллом.

Тогда, как я уже сказал, вы должны проверить, что и s, и t имеют значение <0,1>, и вы можете вычислить результат. На основе формулы выше.

if ((s >= 0 && s <= 1) && (k >= 0 && k <= 1))
{
   Vector3 res = new Vector3(this.A.x + da.x * s, this.A.y + da.y * s, this.A.z + da.z * s);
}

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

Ответ 5

Вам может показаться полезным взглянуть на соответствующую статью в Википедии - у нее нет кода, но алгоритм описан довольно хорошо, imho (но вы все равно должны знать математику).

http://en.wikipedia.org/wiki/Bentley%e2%80%93Ottmann_algorithm

Обновление: достаточно смешно, что русская версия той же записи в Википедии содержит более подробную информацию (и формулярную), а описание алгоритма также является псевдокодом. Здесь ссылка на перевод этой записи на английский (через Google Translate):

http://translate.google.com/translate?hl=en&sl=ru&tl=en&u=http%3A%2F%2Fru.wikipedia.org%2Fwiki%2F%25D0%259F%25D0%25B5%25D1%2580%25D0%25B5%25D1%2581%25D0%25B5%25D1%2587%25D0%25B5%25D0%25BD%25D0%25B8%25D0%25B5_%25D0%25BE%25D1%2582%25D1%2580%25D0%25B5%25D0%25B7%25D0%25BA%25D0%25BE%25D0%25B2

Ответ 6

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

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

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

Ответ 7

Оригинальный источник, который вы упоминаете, предназначен только для 2-го случая. Реализация для perp в порядке. Использование x и y - это просто переменные, а не указание на предпочтение конкретной плоскости.

На том же сайте есть это для трехмерного случая: " http://geomalgorithms.com/a07-_distance.html "

Похоже, Эберли написал ответ: " https://www.geometrictools.com/Documentation/DistanceLine3Line3.pdf "

Помещение этого материала здесь, потому что Google указывает на геомалгоритмы и на этот пост.

Ответ 8

Вот решение ссылка 3D пересечение линии

Но это решение не совсем правильно. Поскольку в соответствии с этим значением раствора всегда будет положительным. a

a = |(P2-P1) X V2| / |V1 X V2|

и Intersection Point: P1 + a V1

знак a должен быть определен следующим образом: если вектор числителя (P2-P1) X V2 и вектор знаменателя V1 X V2 указывают в одном направлении, то знак равен +; в противном случае знак -.