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

Question

Найти точку пересечения для двух отрезков линии 2D легко; формула прямолинейна . Но боюсь, что найти точку пересечения для двух отрезков 3D-линии нет.

Какой алгоритм в C # предпочтительно находит точку пересечения двух трехмерных отрезков?

Я нашел реализацию C ++ здесь . Но я не доверяю решению, потому что оно отдает предпочтение определенной плоскости (посмотрите, как perp реализовано в разделе реализации, оно предполагает предпочтение z plane. Любой универсальный алгоритм не должен предполагать какую-либо ориентацию плоскости или предпочтение).

Есть ли лучшее решение?

Answer 1

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

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

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

Pa = P1 + mua (P2 - P1)

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

Pb = P3 + mub (P4 - P3)

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

Существует два подхода к поиску самого короткого отрезка между линии "а" и "б".

Подход один:

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

|| Pb - Pa ||^2

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

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

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

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

mub = ( d1343 + mua d4321 ) / d4343

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

Answer 2

// 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;
}

Answer 3

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

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

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

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

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

Answer 4

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

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

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

x = A + (B-A) 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 - это B-A, db - это D-C, а dc - это C-A, я просто сохранил имена, предоставленные Биллом.

Тогда, как я уже сказал, вы должны проверить, являются ли оба 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);
}

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

Answer 5

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

На том же сайте есть это для случая 3d: «http://geomalgorithms.com/a07-_distance.html"

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

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

Answer 6

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

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

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

Answer 7

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

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

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

и Intersection Point: P1 + a V1

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