Encuentra si dos triángulos se cruzan o no en 3D

Question

Dados 2 conjuntos de puntos

((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) y

((p1,q1,r1),(p2,q2,r2),(p3,q3,r3)) formando cada uno un triángulo en el espacio 3D.

¿Cómo vas a averiguar si estos triángulos se cruzan o no?

Una solución obvia a este problema es encontrar la ecuación del plano formado por cada triángulo. Si los planos son paralelos, entonces no se cruzan.

Si no, halla la ecuación de la recta formada por la intersección de estos planos utilizando los vectores normales de los mismos.

Ahora, si esta línea se encuentra en ambas regiones triangulares, entonces estos dos triángulos se intersecan, de lo contrario no.

¿Hay alguna otra solución?

Answer 1

He escrito código exactamente para este problema, pero de momento no lo encuentro :-/. [Utilizado en un artículo: "Sobre la reconstrucción de poliedros a partir de cortes". Int. J. Comput. Geom. & Appl. , 6(1) 1996: 103-112.] Sin embargo, es bastante fácil de describir.

En primer lugar, necesitas un código robusto para decidir si un punto está por encima, por debajo o en el plano determinado por un triángulo. Véase, por ejemplo, el código descrito en Geometría computacional en C para esta tarea de bajo nivel (que equivale a calcular el volumen con signo de un tetraedro), y otros siguientes; o en muchas otras fuentes equivalentes. Si los tres puntos de un triángulo están a un lado del otro la intersección está vacía.

Que el vértice $a$ del triángulo $\triangle abc$ estar por encima del triángulo $t'=\triangle a'b'c'$ y $b$ y $c$ a continuación. (Ignoraré los casos "on" para simplificar, pero por supuesto debes tratarlos con cuidado). Si $t$ y $t'$ se cruzan, entonces debe ser que una arista de una se cruza con la otra; esta es la observación clave (también hecha por anon en otra respuesta). Por lo tanto, o bien $ab \cap t'$ o $ac \cap t'$ es no vacía, o las condiciones análogas con el papel de los triángulos invertido.

La comprobación de estas condiciones requiere un código (de nuevo robusto) para determinar si un segmento intersecta un triángulo. Esto puede calcularse resolviendo simultáneamente una ecuación paramétrica para el segmento y el plano que contiene $\triangle t'$ obteniendo el punto $p$ de intersección, y determinar si $p$ se encuentra dentro de $\triangle t'$ . Esto último es una tarea independiente y fácil.

Así, el conjunto puede realizarse mediante una serie de cálculos elementales, controlados y limitados.

Answer 2

No he tenido tiempo de comprobar las otras respuestas en detalle, así que esto puede ser equivalente... pero el método estándar para hacerlo es mediante el "teorema del eje de separación", que básicamente dice que dos objetos convexos están separados si existe un eje de manera que las proyecciones de los objetos sobre el eje no se superpongan.

En el caso de dos triángulos, esto equivale a un par de productos cruzados, productos punto y comprobaciones de intervalo, que pueden realizarse de forma muy eficiente. Una rápida búsqueda en Google ha dado como resultado lo siguiente:

http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf

Answer 3

Se pide que el sistema lineal de cinco ecuaciones con seis incógnitas $$ a_1+a_2+a_3=1,\quad u_1+u_2+u_3=1,\quad a_1x_1+a_2x_2+a_3x_3=u_1p_1+u_2p_2+u_3p_3, $$ y $$ a_1y_1+a_2y_2+a_3y_3=u_1q_1+u_2q_2+u_3q_3,\quad a_1z_1+a_2z_2+a_3z_3=u_1r_1+u_2r_2+u_3r_3, $$ tiene algunas soluciones tales que cada $a_i$ y cada $u_j$ no es negativo.

Answer 4

He aquí una solución con sabor geométrico.

Primero prueba si los triángulos son paralelos o no. Si lo son, encuentra la distancia mínima $d$ entre los dos planos que ocupan; si $d\ne0$ entonces los triángulos no se cruzan, si $d=0$ entonces nuestro problema se reduce al caso planar que analizaremos en breve. Para cualquier $x\in\pi_1,y\in\pi_2$ dos planos paralelos $\pi_1$ y $\pi_2$ con un vector normal compartido $n$ tienen una distancia nula entre sí si y sólo si $(x-y)\perp n$ . La selección más fácil sería hacer $x,y$ vértices de distintos triángulos.

En el caso plano, dos triángulos se cruzan si y sólo si hay un par de aristas, una de cada triángulo, que se cruzan. Por tanto, el problema se reduce a comprobar si dos segmentos de línea se cruzan o no (para nueve pares de segmentos posibles, aunque sólo hay que comprobar un máximo de siete). Esto se puede conseguir con un método básico de mínimos cuadrados.

Si los triángulos no son paralelos, entonces se intersecan si y sólo si al menos una arista de uno de los triángulos interseca al otro triángulo, y este punto de intersección (para una arista dada) será único. Por lo tanto, diremos que el segundo triángulo está fijado al plano $\pi$ y, debido a la simetría, sólo comprueba si una arista del primer triángulo se cruza con $\pi$ Esta arista tiene puntos finales $a$ y $b$ (en realidad, puede ser necesario aplicar esta prueba hasta tres veces, una por cada arista). Además, utilice una transformación afín en todo el montaje para que el segundo triángulo tenga el origen $O$ como un vértice por conveniencia.

$\hskip 1in $

Cada punto de la línea verde tendrá la forma $r\mathbf{a}+(1-r)\mathbf{b}, r\in[0,1]$ . Todos los puntos dentro del triángulo negro serán de la forma $s\mathbf{u}+t\mathbf{v}, s,t\in[0,1]$ . Al igualar las dos expresiones tendremos una solución única como es el punto de intersección entre la línea verde y el plano en el que se encuentra el triángulo negro. Sea $X$ denotan el $3\times3$ matriz con columnas $\mathbf{b}-\mathbf{a}$ , $\mathbf{u}$ y $\mathbf{v}$ . Entonces el punto de intersección se encuentra dentro del triángulo si y sólo si $X^{-1} \mathbf{b} \in [0,1]^3$ .