Comprobar si un punto está dentro de un triángulo 3D

Question

Tengo un plano 3D definido por tres puntos: $P_0$ , $P_1$ y $P_2$ . Cómo comprobar si un punto $P$ se encuentra justo en y dentro de ¿el triángulo 3D?

Así, por ejemplo, si tengo un plano definido por $({0,0,0})$ , $({10,0,0})$ y $({0,10,0})$ , entonces el punto $({50,0,0})$ se considera no situado en el plano, mientras que el punto $({5,0,0})$ es.

Answer 1

Una técnica habitual en un programa informático es utilizar coordenadas baricéntricas.

Las coordenadas baricéntricas son mucho más fáciles de encontrar de lo que indican los recursos de la web, así que no las enlazo.

La forma más fácil de obtener las coordenadas baricéntricas de un punto P, dado un triángulo con vértices descritos por los vectores A, B, C es probablemente este método:

$ AreaABC = \frac{ \left| \overline{AB} \times \overline{AC} \right| }{ 2 } $

$ \alpha = \frac{ \left| \overline{PB} \times \overline{PC} \right| }{ 2AreaABC } $

$ \beta = \frac{ \left| \overline{PC} \times \overline{PA} \right| }{ 2AreaABC } $

$ \gamma = 1 - \alpha - \beta $

Aquí $\alpha$ es el cociente del área de un subtriángulo PBC sobre el área del triángulo entero ABC, como se muestra en esta imagen de El libro de Peter Shirley :

Si se cumplen TODAS las siguientes 4 restricciones:

• $ 0 \le \alpha \le 1 $
• $ 0 \le \beta \le 1 $
• $ 0 \le \gamma \le 1 $
• $\alpha + \beta + \gamma = 1$

entonces el punto P está dentro del triángulo.

Tenga en cuenta que si calcula $\gamma$ como lo hice anteriormente (usando $\gamma = 1 - \alpha - \beta$ ) entonces no tiene que comprobar $\alpha + \beta + \gamma = 1$ pero lo harías si encontraras $\gamma$ usando áreas (como se muestra en el diagrama).

Si cualquiera de $\alpha$ , $\beta$ , $\gamma$ están fuera de esos rangos, o si la suma de $ \alpha + \beta + \gamma \ne 1 $ entonces el punto P no está dentro del triángulo.

Tenga en cuenta también cuando uno de $\alpha$ , $\beta$ , $\gamma$ es 0, y las otras 2 coordenadas están entre 0 y 1, el punto P está en un borde del triángulo.

Cuando uno de $\alpha$ , $\beta$ , $\gamma$ es 1 y los otros dos son 0 , entonces el punto P está exactamente en un vértice del triángulo.

Por supuesto, estos cálculos suponen que P ya está en el plano del triángulo. Si P no está en el plano del triángulo, entonces hay que proyectarlo allí primero, antes de calcular las coordenadas baricéntricas.

Answer 2

Intenta resolver el sistema $$ x * (P_1 - P_0) + y * (P_2 - P_0) = P - P_0 $$ Si se puede resolver, el punto $P$ se encuentra en el avión. Si además $x \geq 0$ , $y \geq 0$ y $x + y \leq 1$ entonces $P$ se encuentra dentro del triángulo.

Answer 3

Vectores $V_{01}=P_1-P_0$ y $V_{02}=P_2-P_0$ se encuentran en el plano del triángulo, y $V_{01}\times V_{02}$ es normal a este plano. Sea $V_{0p}=P-P_0$ y si $V_{0p} \cdot (V_{01}\times V_{02}) = 0$ entonces $P$ se encuentra en el plano.

Dejemos que $P=cP_0+aP_1+bP_2$ donde $c=1-a-b$ . Entonces $P=(1-a-b)P_0+aP_1+bP_2$ o $V_{0p}=aV_{01}+bV_{02}$ . Si $0 \le a,b,c \le 1$ entonces $P$ se encuentra en el triángulo o en su borde.

Vector $V_{01} \times (V_{01}\times V_{02})$ es ortogonal a $V_{01}$ así que $V_{02} \cdot(V_{01} \times (V_{01}\times V_{02}))b=V_{0p} \cdot(V_{01} \times (V_{01}\times V_{02}))$ puede resolverse para b.

Asimismo, $V_{02} \times (V_{01}\times V_{02})$ es ortogonal a $V_{02}$ así que $V_{01} \cdot(V_{02} \times (V_{01}\times V_{02}))a=V_{0p} \cdot(V_{02} \times (V_{01}\times V_{02}))$ puede resolverse para a.

Answer 4

Es muy posible que haya un algoritmo más eficiente, pero aquí hay una forma de comprobarlo P está en el triángulo definido por los tres puntos

Comparar los productos cruzados $\vec {P_0 P_1} \times \vec {P_0 P_2} = \vec a$ y $\vec {P P_1} \times \vec {P P_2} = \vec b$ . Si $\vec b = k_1 \vec a$ con $k_1 \geq 0$ entonces P está en el plano y está en el lado correcto de la línea que pasa por P ₁ y P ₂ .

Ahora, calcula $\vec {P P_2} \times \vec {P P_0} = \vec c$ y $\vec {P P_0} \times \vec {P P_1} = \vec d$ . Si $\vec c = k_2 \vec a$ y $\vec d = k_3 \vec a$ con $k_2, k_3 \geq 0$ entonces P se encuentra dentro del triángulo.

Por supuesto, hay mucha redundancia en este cálculo. Una vez que sabemos P está en el plano, podríamos simplemente comprobar una coordenada del $\vec c$ y $\vec d$ para ver que tienen el signo correcto. Esto no es más que proyectar el problema sobre uno de los planos de coordenadas.

---

Mi antigua respuesta a continuación explica cómo comprobarlo P está en el plano infinito definido por los tres primeros puntos, no cómo comprobar si está dentro del triángulo definido por los tres primeros puntos, que es lo que pretendía la pregunta.

---

Una ecuación general del plano es Ax + By + Cz = D . El vector tridimensional < A,B,C > es perpendicular al plano.

(Obsérvese que no hay una ecuación única de esta forma; se puede multiplicar la ecuación por cualquier número distinto de cero y obtener otra ecuación del plano. -Así que puedes intentar encontrar una solución con D=1 y si eso no funciona, utilice D=0 .)

Si encuentras una ecuación del plano definido por tus tres primeros puntos, puedes simplemente introducir el cuarto punto para comprobar si satisface la ecuación.

Se puede resolver la ecuación del plano a mano estableciendo la ecuación a partir de los tres primeros puntos; pero un método más eficiente es tomar el producto cruzado del vector $\vec {P_0 P_1}$ y el vector $\vec {P_0 P_2}$ y utilizar el vector resultante como < A,B,C >. Te resultará muy útil entender el producto cruzado si te gusta trabajar en el espacio tridimensional.