Пересечение отрезков, в 3D - пространстве Опции

[Isaev]

Вот переклинило меня на простой задаче:
3D пространство, 2 отрезка, заданные 4мя точками...
отрезок A, точки - A1(x1,y1,z1), A2(x2,y2,z2)
отрезок B, точки - B3(x3,y3,z3), B4(x4,y4,z4)
Как узнать:
1. пересекаются ли они?
2. если да, то найти точку пересечения C(x5,y5,z5)

Тривиальная задачка, но за 10 лет забыл всё нахрен
Помогите, please!

[Michael_Rybak]

Вычислили... Теперь знаем, есть ли точка пересечения...

Не совсем. Если не в одной плоскости, то точки пересечения точно нет, если в одной - то может и есть.

Чтобы узнать, задаем прямые, содержащие отрезки, параметрически; для первой прямой:

x = A.x + (B.x - A.x) * t
y = A.y + (B.y - A.y) * t
z = A.z + (B.z - A.z) * t

Для второй аналогично.

Получаем систему:

A.x + (B.x - A.x) * t1 = C.x + (D.x - C.x) * t2
A.y + (B.y - A.y) * t1 = C.y + (D.y - C.y) * t2
A.z + (B.z - A.z) * t1 = C.z + (D.z - C.z) * t2

3 уравнения, 2 неизвестных. Система избыточна, но все три уравнения нужны на случай, если обе прямые параллельны какой-то из осевых плоскостей.

Решать ее лучше не вручную (если первое уравение имеет вид const = const то если константы разные, то решения нет, а иначе выбрасываем уравнение; а если один из коэффициентов (B.x - A.x) или (D.x - C.x) равен нулю, то сразу вычисляем соответственно t2 или t1 и смотрим куда подставить и т.д и т.д и т.д.), а просто полностью реализовать метод Гаусса.

Если решения нет - прямые параллельны. Если решений бесконечно много - прямые совпадают, и можно, например, проверить каждый конец каждого отрезка на принадлежность другому отрезку. Если решение единственно - прямые пересекаются, теперь проверяем условие 0 <= t1, t2 <= 1 чтобы узнать, принадлежит ли точка пересечения обоим отрезкам. Если да, подставляем t1 в параметрическое уравнение первой прямой (или t2 - в уравнение второй), получаем ответ.

[Isaev]

Не совсем. Если не в одной плоскости, то точки пересечения точно нет, если в одной - то может и есть.

Ну так если определитель 3 порядка (он же "объем тетраэдра A1A2B3B4") равен нулю, значит полюбому в одной плоскости...

Если решения нет - прямые параллельны.

Я бы сказал лежат в параллельных плоскостях

Система жестокая получилась...
Если допустить, что решение существует и причём только одно, как это свернётся?
Частный случай: A(5;7;4) B(9;17;16) C(7;14;2) D(7;10;18)
Если это нарисовать, то видим точку пересечения E(7;12;10)
Векторы: AB(4;10;12) CB(2;3;14) CD(0;-4;16)
Определитель 3 порядка: 4*(-4)*14+10*16*2+0*3*12-2*(-4)*12-0*10*14-3*16*4=-224+320+96-192=0 (точка пересечения точно есть)
Как выйти на её координаты E(7;12;10)?

[Michael_Rybak]

Ну так если определитель 3 порядка (он же "объем тетраэдра A1A2B3B4") равен нулю, значит полюбому в одной плоскости...

Ну да. По-любому в одной. Но это совсем ведь не значит, что отрезки имеют общие точки.

Я бы сказал лежат в параллельных плоскостях

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

Система жестокая получилась...
Если допустить, что решение существует и причём только одно, как это свернётся?
Частный случай: A(5;7;4) B(9;17;16) C(7;14;2) D(7;10;18)
Если это нарисовать, то видим точку пересечения E(7;12;10)
Векторы: AB(4;10;12) CB(2;3;14) CD(0;-4;16)
Определитель 3 порядка: 4*(-4)*14+10*16*2+0*3*12-2*(-4)*12-0*10*14-3*16*4=-224+320+96-192=0 (точка пересечения точно есть)
Как выйти на её координаты E(7;12;10)?

Я уже на это ответил. Решить систему относительно t1 и t2 методом Гаусса и подставить значение t1 в параметрическое уравнение первой прямой. Откуда вообще система взялась понятно?

P.S. На всякий случай еще раз: если определитель равен нулю, это еще не значит, что точка пересечения точно есть. А если точка пересечения *прямых* есть, это еще не значит, что *отрезки* пересекаются.

Пожалуйста, перечитай внимательно весь мой предыдущий пост.

[Isaev]

Пожалуйста, перечитай внимательно весь мой предыдущий пост.

Перечитал... Всё, разобрался...

только не понял:

3 уравнения, 2 неизвестных. Система избыточна, но все три уравнения нужны на случай, если обе прямые параллельны какой-то из осевых плоскостей.

на что это может повлиять?

Сообщение отредактировано: Isaev - 3.10.2007 20:53