Las coordenadas baricéntricas parecen un camino razonable. Para repasar, las coordenadas baricéntricas de un punto $\mathbf p=(x,y)$ relativa a un triángulo con vértices $\mathbf v_0=(x_0,y_0)$ , $\mathbf v_1=(x_1,y_1)$ , $\mathbf v_2=(x_2,y_2)$ son un triple $\mathbf\lambda=[\lambda_0:\lambda_1:\lambda_2]$ tal que $\mathbf p=\lambda_0\mathbf v_0+\lambda_1\mathbf v_1+\lambda_2\mathbf v_2$ y $\lambda_0+\lambda_1+\lambda_2=1$ . Una forma de pensar en estas coordenadas es como las masas que deben colocarse en los vértices del triángulo para que el centro de masa esté en $\mathbf p$ . Podemos eliminar la condición de normalización y trabajar con coordenadas no normalizadas, en cuyo caso $\mathbf p={\lambda_0\mathbf v_0+\lambda_1\mathbf v_1+\lambda_2\mathbf v_2\over\lambda_0+\lambda_1+\lambda_2}$ . Estas coordenadas son homogéneo -lo importante son las relaciones entre ellas, y dos conjuntos de coordenadas que son múltiplos escalares no nulos entre sí representan el mismo punto.
Las características de las coordenadas baricéntricas (normalizadas) que utilizaré son las siguientes:
- Las coordenadas baricéntricas y cartesianas se relacionan mediante una transformación lineal.
- Si un punto es interior o está en el triángulo, entonces todas sus coordenadas baricéntricas están en el intervalo cerrado $[0,1]$ .
- Una coordenada cero indica que el punto se encuentra en la línea lateral opuesta al vértice correspondiente. Una coordenada negativa indica que el punto se encuentra en el lado opuesto de esa línea lateral al vértice. Por ejemplo, si la primera coordenada es negativa, el punto se encuentra en el lado opuesto de la línea que pasa por $v_1$ y $v_2$ al igual que $v_0$ .
El mapeo cartesiano a baricéntrico puede calcularse expresando la definición de coordenadas baricéntricas como la ecuación matricial $$\begin{bmatrix}x_0&x_1&x_2\\y_0&y_1&y_2\\1&1&1\end{bmatrix}\begin{bmatrix}\lambda_0\\\lambda_1\\\lambda_2\end{bmatrix}=\begin{bmatrix}x\\y\\1\end{bmatrix}.$$ The triangle is not degenerate, so that the matrix on the left is nonsingular and thus the barycentric coordinates are found by multiplying $(x,y,1)^T$ by the inverse of that matrix. This $3\times3$ inversion can be reduced to $2\times2$ by rewriting the coordinate equation as $$\begin{bmatrix}\mathbf v_0-\mathbf v_2 & \mathbf v_1-\mathbf v_2\end{bmatrix}\begin{bmatrix}\lambda_0\\\lambda_1\end{bmatrix}=\mathbf p-\mathbf v_2.$$ La tercera coordenada puede calcularse entonces como $\lambda_2=1-\lambda_0-\lambda_1$ .
Otra forma de evitar la inversión de la matriz es utilizar el hecho de que las relaciones de coordenadas baricéntricas son iguales a las relaciones de las áreas con signo de los triángulos formados por el punto y los pares de vértices del triángulo de referencia. Estas áreas pueden calcularse como $$\frac12\begin{vmatrix}x_{i+1} & x_{i+2} & x \\ y_{i+1} & y_{i+2} & y \\ 1&1&1 \end{vmatrix}=\frac12(x_{i+1},y_{i+1},1)\times(x_{i+2},y_{i+2},1)\cdot(x,y,1)$$ con índices que envuelven el mod 3. Recordando que los componentes del producto de una matriz y un vector columna son los productos punto del vector con las filas de la matriz, los cálculos del área pueden escribirse como $$\frac12\begin{bmatrix}(\tilde{\mathbf v}_1\times\tilde{\mathbf v}_2)^T \\ (\tilde{\mathbf v}_2\times\tilde{\mathbf v}_0)^T \\ (\tilde{\mathbf v}_0\times\tilde{\mathbf v}_1)^T \end{bmatrix}\tilde{\mathbf p}.$$ (Las tildes denotan las coordenadas homogéneas obtenidas añadiendo un $1$ al par de coordenadas cartesianas). Estas coordenadas se pueden normalizar dividiendo por el área del triángulo de referencia, de modo que las coordenadas baricéntricas normalizadas de $\mathbf p=(x,y)$ son $$\mathbf\lambda=\frac1{\det\begin{bmatrix}\tilde{\mathbf v}_0&\tilde{\mathbf v}_1&\tilde{\mathbf v}_2\end{bmatrix}}\begin{bmatrix}(\tilde{\mathbf v}_1\times\tilde{\mathbf v}_2)^T \\ (\tilde{\mathbf v}_2\times\tilde{\mathbf v}_0)^T \\ (\tilde{\mathbf v}_0\times\tilde{\mathbf v}_1)^T \end{bmatrix}\tilde{\mathbf p}.$$ (También puede trabajar con coordenadas no normalizadas, pero tendrá que utilizar un intervalo diferente para determinar cuándo un punto está en/sobre el triángulo: las coordenadas deben estar limitadas por $0$ y $\lambda_1+\lambda_2+\lambda_3$ pero esto último podría ser negativo).
Sean las coordenadas baricéntricas de los puntos extremos del segmento de línea $\mathbf P=[\lambda_1:\lambda_2:\lambda_3]$ y $\mathbf Q=[\mu_1:\mu_2:\mu_3]$ . Si cualquiera de estos puntos está en/sobre el triángulo, es decir, $0\le\lambda_1,\lambda_2,\lambda_3\le1$ o $0\le\mu_1,\mu_2,\mu_3\le1$ entonces hemos terminado: el segmento de línea obviamente interseca el triángulo.
Si no, tenemos dos puntos exteriores. Gracias a la linealidad del mapeo cartesiano a baricéntrico, la línea que pasa por $\mathbf P$ y $\mathbf Q$ puede parametrizarse como $(1-t)\,\mathbf P+t\,\mathbf Q$ en ambos sistemas de coordenadas, con $t\in[0,1]$ dando el segmento de línea. Los valores de $t$ para la cual una coordenada baricéntrica de la combinación lineal anterior es $0$ son las intersecciones con las líneas laterales correspondientes. Estos valores de $t$ se encuentran fácilmente $t_i={\lambda_i\over\lambda_i-\mu_i}$ , a menos que $\lambda_i=\mu_i$ en cuyo caso la línea es paralela a ese lado del triángulo. El segmento de línea interseca al triángulo si cualquiera de estos cruces de líneas laterales ocurre en el triángulo. Además, para que un segmento de línea con dos puntos extremos exteriores intersecte al triángulo, debe haber al menos dos cruces de líneas laterales, independientemente de dónde estén esos puntos de cruce.
Por lo tanto, compara las coordenadas baricéntricas correspondientes de $\mathbf P$ y $\mathbf Q$ . Si menos de dos pares tienen signos opuestos, entonces el segmento no interseca al triángulo y hemos terminado. En caso contrario, para cada par de coordenadas $\lambda_i$ y $\mu_i$ calcula el punto de intersección ${\mu_i\over\mu_i-\lambda_i}\mathbf P+{\lambda_i\over\lambda_i-\mu_i}\mathbf Q$ . (Podría ser más conveniente utilizar $1-{\lambda_i\over\lambda_i-\mu_i}$ para el coeficiente de $\mathbf P$ .) Si alguno de estos puntos de intersección se encuentra en el triángulo, entonces el segmento interseca al triángulo.
Los cálculos anteriores fueron para puntos en $\mathbb R^2$ pero estás trabajando en $\mathbb R^3$ . Las transformaciones afines conservan las líneas, sus intersecciones y las longitudes relativas de los segmentos a lo largo de una línea, por lo que el problema puede convertirse en bidimensional mediante una proyección paralela sobre cualquier plano conveniente que no sea ortogonal al plano del triángulo. La proyección sobre uno de los planos de coordenadas es la más sencilla, ya que sólo hay que eliminar una de las coordenadas cartesianas. Si se utiliza el $3\times3$ matriz de transformación de coordenadas, proyectando sobre $z=1$ es conveniente ya que establece la tercera coordenada en $1$ como se requiere para utilizar la matriz.
También es posible evitar una proyección explícita si el plano del triángulo no pasa por el origen. En ese caso, las áreas de los triángulos en el plano son proporcionales a los volúmenes de los tetraedros definidos por los vértices del triángulo y el origen, por lo que podemos utilizar directamente los productos triples de los puntos para calcular las coordenadas baricéntricas. Es decir, podemos calcular $$\mathbf\lambda=\begin{bmatrix}(\mathbf v_1\times\mathbf v_2)^T\\(\mathbf v_2\times\mathbf v_0)^T\\(\mathbf v_0\times\mathbf v_1)^T\end{bmatrix}\mathbf p$$ utilizando los triples de coordenadas en bruto de estos puntos. Si el plano del triángulo pasa por el origen, desplaza todos los puntos una pequeña distancia en una dirección no paralela al plano.
Esta solución es fundamentalmente similar a el que da el Animal Nominal . Sin embargo, el uso de coordenadas baricéntricas permite tratar todos los lados del triángulo de manera uniforme. Además, si lo piensas un poco, verás que estos cálculos son una serie de pruebas de "izquierda", desenrolladas.
La forma de producto cruzado del mapeo cartesiano a baricéntrico me lleva a descartar esto también, aunque dudo que sea tan eficiente como otras soluciones que se han presentado. Aprovecha el hecho de que en $\mathbb{RP}^2$ La línea que pasa por dos puntos y la intersección de dos líneas pueden calcularse tomando productos cruzados de vectores de coordenadas homogéneas. Por lo tanto, la matriz de asignación de coordenadas puede verse como si tuviera las tres líneas laterales del triángulo como sus filas.
Las coordenadas baricéntricas de las tres intersecciones de las líneas laterales pueden calcularse "en bloque" como $B(\tilde{\mathbf p}\times\tilde{\mathbf q})_\times B^T$ , donde $B$ es la matriz de transformación de coordenadas de arriba y la matriz central es la "matriz de producto cruzado" definida como sigue: para cualquier vector $\mathbf w=(w_1,w_2,w_3)T$ , $$\mathbf w_\times=\begin{bmatrix}0&-w_3&w_2\\w_3&0&-w_1\\-w_2&w_1&0\end{bmatrix}.$$ Al igual que antes, tendrás que comprobar si alguno de estos puntos está en el triángulo y también tendrá que comprobar que los candidatos viables para las intersecciones de los triángulos se encuentran entre $\mathbf p$ y $\mathbf q$ . Además, estas coordenadas no estarán normalizadas, por lo que tendrás que tenerlo en cuenta al hacer estas pruebas. También tendrás que lidiar con los puntos en el infinito, que se producirán cuando el segmento sea paralelo a uno de los lados del triángulo. En forma baricéntrica, las coordenadas de los puntos en el infinito suman cero.
