Пересечение прямой и параллелепипеда

[myf]

Дана плоскость OXYZ. Известны координаты двух точек на прямой в этой плоскости, а также координаты всех восьми вершин параллелепипеда. Как узнать, пересекает эта прямая параллелепипед или нет. Точка пресечения не нужна, нужно установить сам факт пересечения.

[Really]

myf писал(а):

Дана плоскость OXYZ. Известны координаты двух точек на прямой в этой плоскости, а также координаты всех восьми вершин параллелепипеда. Как узнать, пересекает эта прямая параллелепипед или нет. Точка пресечения не нужна, нужно установить сам факт пересечения.

Что значит плоскость OXYZ? - это не понял.
Задача я так понимаю в пространстве.
Я бы нашел параметрическое уравнение прямой. Нашел уравнения всех 6 плоскостей, ограничивающих параллелепипед. Затем составил бы систему неравенств на основе следующего принципа:

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

Получится система трех квадратныхнеравенств. Если система совместна - пересечение есть.

Вроде правильно. Как короче не знаю.

[Brukvalub]

Может, так будет проще:1) Совершить афинное преобразование пространства, переводящее параллелепипед в единичный куб с началом координат в его центре и пересчитать уравнение прямой в новых координатах..
2) Найти решение задачи в этом случае, что совсем просто.
И, конечно, афинное преобразование сохраняет отношение "прямая пересекает параллелепипед"

[Руст]

Это только кажущееся упрощение. На самом деле всё равно надо найти точки пересечения плоскостями, образованными гранями параллелепида, и проверить принадлежит ли точка пересечения грани. Должно найтись по крайней мере 2 грани с этим свойством.
Соответственно записываем уравнение прямой
(1)$r=r_0+at$, r,r0,a векторы и уравнение плоскостей:
(2) $((r-r_A),(r_B-r_A),(r_C-r_A))=0$ (здесь используется смешанное произведение).
Подставив (1) в (2) находим t и координаты точки пересечения. Далее с помощью вычисления значений
$V=((r_D-r_A)(r_B-r_A),(r_C-r_A)),C_*=((r_*-r_A)(r_B-r_A)(r_D-r_A)$
проверяем находится ли точка пересечения между плоскостями ABD и параллельнем к нему через точку С. В случае нахождения число $C_*$ должно находится в интервале от нуля до V. И так проводя все проверки узнаем о пересечении.

[Brukvalub]

Руст писал(а):

... В случае нахождения число $C_*$ должно находится в интервале от нуля до V. И так проводя все проверки узнаем о пересечении.

Алгоритм не годится, если прямая проходит через вершину параллелепипеда.

[Руст]

Если проходит через вершину, то для трёх граней выполняется крайнее значение 0 или V (если уравнения выражены через координаты именно этой вершины, то трижды 0).

[myf]

Спасибо большое за ответы. Мне просто нужно как бы написать программу по определению этого факта. Системку такую не просто будет решить на компе.

[myf]

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

[bot]

Мне больше по душе то, что написал Brukvalub, возможно потому, что и сам подумал то же самое.
А реализация здесь очень простая.
1) Пересчёт параметров прямой при аффинном преобразовании (которое и находить не обязательно)
требует решения двух линейных систем с тремя неизвестными.
Это и есть простая, но самая трудоёмкая часть. Остальное ещё проще - это просто логика, которая на компе производится
наиболее быстро.
2) Просто давайте распишем то "совсем просто", о котором говорил Brukvalub. Итак пусть дан единичный куб,
одна вершина которого в начале координат, а три ей смежные - на осях. Прямая пусть проходит через
точку (a,b,c) с направляющим вектором (m,n,k).
Положим $P(a,b,c, m,n,k) \equiv (m\ne 0) \& $
$((0\le b-\frac{a}{m}n\le 1)\&(0\le c-\frac{a}{m}k\le 1)\vee $
$((0\le b+\frac{1-a}{m}n\le 1)\&(0\le c+\frac{1-a}{m}k\le 1))$

Тогда условие пересечения прямой с кубом равносильно истинности формулы:
$P(a,b,c, m,n,k)\vee P(b,c, a, n,k,m)\vee P(c,a,b, k,m,n)$

Содержательно здесь просто написано, что если прямая пересекает куб, то она пересекает
некоторую грань под ненулевым углом - этим и объясняется отсутстве в формуле дизъюнктов, содержащих m=0, n=0 и k=0.

Разумеется в успешном случае вычисляются и точки пересечения с гранями, но это для этого надо
явно выписать аффинный переход, что впрочем тоже просто.