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

Question

Я ищу быстрый способ вычисления отрезка двух заданных прямоугольников в 3D. Например, каждый трехмерный прямоугольник определяется своими четырьмя вершинами.

Подойдет решение на любом разумном языке программирования.

Answer 1

На основании ответа Аарона, который, как я считаю, содержит ошибку:

1. Превратите два прямоугольника в две плоскости (просто возьмите три из четырех вершин и постройте из этого плоскость).
2. Пересечь две плоскости, чтобы получить бесконечную линию (*).
3. Пересечь эту линию с ограничивающими линиями первого прямоугольника.
4. Пересечь результат 3 с ограничивающими линиями второго прямоугольника.

Если вы пропустите шаг 4, вы получите ложное пересечение, когда первый прямоугольник пересекает плоскость второго прямоугольника, но не сам прямоугольник. Пример:

rectangle1=[(-1,-1,0),(-1,1,0),(1,1,0),(1,-1,0)]  
rectangle2=[(0,50,50),(0,50,40),(0,40,40),(0,40,50)]

Plane1 - это z = 0, plane2 - это x = 0, их пересечение - это ось y, которая пересекает прямоугольник 1 в 1 и -1. Однако прямоугольники не пересекаются.

(*) Если плоскости перекрываются, пересечение прямоугольников все еще может быть линией, но это довольно неприятный случай.

Answer 2

Вам нужно будет объединить три обычных 3D-операции:

1. Превратите два прямоугольника в две плоскости (просто возьмите три из четырех вершин и постройте из этого плоскость).

2. Пересечь две плоскости, чтобы получить бесконечную линию (см. здесь ).

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