¿Existe un algoritmo para determinar si un punto P se encuentra dentro de un triángulo ABC definido como tres puntos A, B y C? (Los tres segmentos del triángulo pueden determinarse como el centroide si son necesarias.)
Espacio de la red se define como el espacio en la pantalla, es decir, 2D cartesiano con el eje y voltea para "up" es negativo y y el origen es la esquina superior izquierda.
Este es un muy bien conocido algoritmo. Todo se reduce a utilizar el producto cruzado. Definir los vectores $AB$, $BC$ y $CA$ y los vectores $AP$, $BP$ y $CP$. A continuación, $P$ está dentro del triángulo formado por $A, B$ $C$ si y sólo si todos los productos cruzados $AB\times AP$, $BC\times BP$ y $CA\times CP$ apuntan en la misma dirección en relación con el plano. Es decir, o todos ellos punto fuera del plano, o todo punto en el plano.
Actualización: esta prueba puede ser realizada con el uso de productos de puntos.
Actualización 2: Como se destaca en los comentarios, usted sólo tiene que comparar los signos de los componentes tercero.
A prueba de cualquier ppoint $P=(x,y)$, primero mueva el origen en un vértice, como $A$ tal que $$ B \rightarrow B - A $$ $$ C \rightarrow C - A $$ $$ P \rightarrow P - A $$
Entonces me calcular el escalares $ d = x_B y_C - x_C y_B $ y los tres Baricéntrico pesos
$$ \begin{matrix} w_A = \frac{ x ( y_B-y_C) + y ( x_C-x_B) + x_B\; y_C - x_C\; y_B}{d} \\ w_B = \frac{ x\; y_C - y\; x_C }{d} \\ w_C = \frac{ y\; x_B - x\; y_B }{d} \end{de la matriz} $$
El punto está en el interior cuando todos los pesos están entre $0\ldots1$.
Ejemplo: $A=(1,1)$ $B=(4,2)$ $C=(2,7)$. Considere la posibilidad de un punto de $P=(2,3)$, entonces la sclar es $d=17$ y tres pesos son: $w_A = \frac{8}{17}$, $w_B = \frac{4}{17}$ y $ w_C=\frac{5}{17}$ cuales son todos los $|w_i|<1$.
Por otro lado, si $P=(1.5,5)$ $w_A = \frac{13}{34} $, $w_B = -\frac{1}{17}$ y $ w_C=\frac{23}{34}$ y desde $w_B$ no se caen entre las $0\ldots1$, entonces el punto está fuera.
El uso de coordenadas homogéneas con $A=(x_A,y_A,1)$, $B=(x_B,y_B,1)$, $C=(x_C,y_C,1)$, $P=(x,y,1)$ y el uso de la siguiente relación $$ P = w_A\;A + w_B\;B+w_C\;C $$ para resolver $w_A$, $w_B$ y $w_C$.
El aviso de que la ecuación de $w_A=0$ describe la línea de $BC$ y la ecuación de $w_A=1$ una línea paralela a $BC$ a través de $A$. Análogamente para los otros pesos. La región donde todos los pesos son $w_i\geq0$ $ w_i\leq1$ es el triángulo descrito por $ABC$.
Sí, este problema sin duda ha llegado mucho antes. Eric Haines escribió sobre el problema más general de "punto en Polígono" (cuyos algoritmos pueden ser enormemente simplificados para el caso triangular) en Graphics Gems IV. También presentó un método usando Baricéntrico coordenadas en este artículo del Dr. Dobb ' s.
Creo que se puede comprobar al computar el área de $\triangle ABC$, $\triangle ABP$, $\triangle BCP$ y $\triangle ACP$ (que se puede hacer relativamente fácil de las coordenadas de los puntos) y si $k_{\triangle ABC}=k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$ (donde $k_\_$ es el área), a continuación, $P$ dentro del triángulo (o posiblemente en su límite), pero si $k_{\triangle ABC}< k_{\triangle ABP}+k_{\triangle BCP}+k_{\triangle ACP}$, $P$ está fuera del triángulo.
Escribí un artículo completo sobre el punto en el triángulo de la prueba. Se muestra el baricéntrico, paramétrico y el producto escalar de los métodos basados en.
A continuación, se aborda el problema de precisión que ocurren cuando un punto se encuentra exactamente sobre uno de los bordes (con ejemplos). Finalmente se expone un nuevo método basado en punto a la distancia al borde.
http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html
¡A disfrutar !
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
