Пересечение отрезков, в 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 - в уравнение второй), получаем ответ.