Averiguar si dos rectángulos se cruzan en el espacio 3D

Question

Tengo dos rectángulos en el espacio 3D, cada uno dado por las coordenadas de sus 4 esquinas. No están alineados con los ejes, lo que significa que sus bordes no son necesariamente paralelos/perpendiculares a los ejes del mundo. Cada rectángulo puede tener cualquier orientación.

¿Existe una manera fácil de saber si los dos rectángulos se cruzan o no?

Answer 1

Encuentra los puntos de intersección de ambos rectángulos en el plano del otro. Esto se consigue introduciendo las coordenadas de los vértices en la ecuación implícita del plano y detectando un cambio de signo.

Si se obtienen cuatro puntos de intersección, que definen dos segmentos de línea, basta con comprobar si estos segmentos se solapan (y dónde si se necesitan los puntos finales). Proyecte los puntos en la dirección de la línea común (producto cruzado de los vectores normales), y obtendrá valores escalares correspondientes a las abscisas a lo largo de esa línea.

Comprobar el solapamiento en 1D es trivial.

Answer 2

Hay formas fáciles de decidir (en algunos casos) el complemento de esta pregunta, por lo que se puede idear una prueba para eliminar los falsos positivos. El problema son todos los casos patológicos de vallas, que tendrás que abordar sistemáticamente (un vértice común, una arista común, etc.) y los problemas de punto flotante / precisión, que son la perdición de la geometría computacional.

Para la primera prueba de eliminación, yo utilizaría los cuadros delimitadores de los rectángulos. Si no hay más de dos de los tres rangos de coordenadas $\{min(x), max(x)\},\{min(y), max(y)\},\{min(z), max(z) \}$ de los dos rectángulos se superponen, no hay intersección. Puedes convencerte de ello. Puedes comprobar los rangos x, y y z sucesivamente eliminando así los falsos positivos. ("Solapamiento" debe entenderse como un conjunto no vacío que se produce al tomar la intersección de conjuntos de los respectivos intervalos).

Después de una ronda de eliminación viene la parte más dura. Aunque haya solapamiento en los rangos x,y y z de dos rectángulos espaciales, no significa que se crucen (piensa en rectángulos paralelos). Sin embargo, puedes encontrar fácilmente las ecuaciones de los planos que contienen a los dos rectángulos (tomando tres puntos de cada uno), así que puedes eliminar los planos paralelos.

Los pares de rectángulos que superan ambas pruebas no tienen por qué intersecarse. En esta fase puedes intentar resolver la ecuación de la recta en la que se cruzan los dos planos que contienen los rectángulos. Ahora tienes que probar la línea (los puntos finales de la misma) con tu caja delimitadora de la intersección. Si se encuentra fuera, es otro falso positivo eliminado. Si se encuentra dentro, bueno, todavía tienes más trabajo que hacer.

Answer 3

Si se puede comprobar la intersección línea-rectángulo, entonces dos rectángulos A y B se intersecan si y sólo si una línea de A interseca a B o una línea de B interseca a A (incluidos los puntos extremos). Cada uno de los rectángulos A y B tiene sólo cuatro líneas, por lo que no debería ser tan difícil de comprobar.

Answer 4

Un punto de cada rectángulo se individualiza vectorialmente por $$ \eqalign{ & {\bf P}_{\,1} = {\bf t}_{\,1} + a{\bf u}_{\,1} + b{\bf v}_{\,1} \quad \left| {\;0 \le a,b \le 1} \right. \cr & {\bf P}_{\,2} = {\bf t}_{\,2} + c{\bf u}_{\,2} + d{\bf v}_{\,2} \quad \left| {\;0 \le c,d \le 1} \right. \cr} $$ con un significado obvio de los vectores
- ${\bf t} _k$ vector de un vértice elegido;
- ${\bf u} _k$ : vector paralelo a un lado desde el vértice elegido;
- ${\bf v} _k$ : vector paralelo al otro lado desde el vértice elegido;

Por lo tanto, para que los puntos coincidan tendremos $$ {\bf P}_{\,1} = {\bf P}_{\,2} \quad \Rightarrow \quad a{\bf u}_{\,1} + b{\bf v}_{\,1} - c{\bf u}_{\,2} - d{\bf v}_{\,2} = {\bf t}_{\,2} - {\bf t}_{\,1} $$ que es un sistema lineal de $3$ ecuaciones en $4$ desconocidos .

Para que los rectángulos se intersequen entre sí, comprobaremos que
- el sistema es solucionable (en $a,b,c,d$ );
- el conjunto de soluciones interseca el dominio $[0,1]^4$ .

Hay varios enfoques para verificar la primera condición.
Podemos, por ejemplo, ir algebraicamente y comprobar el rango de la matriz de coeficientes, y el de la matriz completa:
- si ambos tienen rango $3$ tenemos un conjunto de $\infty ^1$ soluciones (una línea), en función de una de las incógnitas tomadas como parámetro,
geométricamente eso significa que los planos de los ractángulos se cruzan en una línea; - si la matriz de coeficientes tiene rango $2$ , entonces los planos de los rectángulos son paralelos,
y serán coincidentes o no dependiendo de si la matriz completa tiene rango $2$ o $3$ ,
si tienen ambos rango $2$ entonces tenemos $\infty ^2$ soluciones (dos parámetros);
- si la matriz de coeficientes tiene rango $1$ uno o ambos rectángulos están degenerados
(y puede comprobar este caso por adelantado).