determinar si el punto se encuentra dentro del triángulo
El programa necesita leer los valores de tres coordenadas
- P1 (x1,y1)
- P2 (x2,y2)
- P3 (x3,y3)
Así como otra coordenada P(x,y) y determinar si este punto está dentro de un triángulo formado a partir del punto 3 anterior.
3 answers
La forma correcta de hacer esto es calculando las coordenadas baricéntricas del cuarto punto dados los tres puntos de su triángulo. La fórmula para calcularlos se da al final de la sección "Convertir a coordenadas baricéntricas", pero espero proporcionar una explicación menos intensa de las matemáticas aquí.
Supongamos, por simplicidad, que tiene una estructura, point, que tiene valores x y y. Usted definió sus puntos como:
point p1(x1, y1);
point p2(x2, y2);
point p3(x3, y3);
point p(x,y); // <-- You are checking if this point lies in the triangle.
Ahora, el baricéntrico coordenadas, generalmente llamadas alpha, beta, y gamma, se calculan de la siguiente manera:
float alpha = ((p2.y - p3.y)*(p.x - p3.x) + (p3.x - p2.x)*(p.y - p3.y)) /
((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float beta = ((p3.y - p1.y)*(p.x - p3.x) + (p1.x - p3.x)*(p.y - p3.y)) /
((p2.y - p3.y)*(p1.x - p3.x) + (p3.x - p2.x)*(p1.y - p3.y));
float gamma = 1.0f - alpha - beta;
Si todos alpha, beta, y gamma son mayores que 0, entonces el punto p se encuentra dentro del triángulo hecho de puntos p1, p2, y p3.
La explicación detrás de esto es que un punto dentro de un triángulo se puede describir usando los puntos del triángulo, y tres coeficientes (uno para cada punto, en el rango [0,1]):
p = (alpha)*p1 + (beta)*p2 + (gamma)*p3
Reorganizar esta función le da la fórmula para calcular coordenadas baricéntricas, pero siento que los pasos para hacerlo podrían estar más allá del alcance de la pregunta. Se proporcionan en la página de Wikipedia que he vinculado arriba.
Se deduce que cada coeficiente debe ser mayor que 0 para que el punto p se encuentre dentro del área descrita por los tres puntos.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-11-09 02:18:58
En lugar de P1, P2 y P3, asumamos los puntos como A,B y C.
A(10,30)
/ \
/ \
/ \
/ P \ P'
/ \
B (0,0) ----------- C(20,0)
Algoritmo:
1) Calculate area of the given triangle, i.e., area of the triangle ABC in the above diagram.
Area A = [ x1(y2 - y3) + x2(y3 - y1) + x3(y1-y2)]/2
2) Calculate area of the triangle PAB. We can use the same formula for this. Let this area be A1.
3) Calculate area of the triangle PBC. Let this area be A2.
4) Calculate area of the triangle PAC. Let this area be A3.
5) If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.
A continuación se muestra un programa en C:
#include <stdio.h>
#include <stdlib.h>
/* A utility function to calculate area of triangle formed by (x1, y1),
(x2, y2) and (x3, y3) */
float area(int x1, int y1, int x2, int y2, int x3, int y3)
{
return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);
}
/* A function to check whether point P(x, y) lies inside the triangle formed
by A(x1, y1), B(x2, y2) and C(x3, y3) */
bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
/* Calculate area of triangle ABC */
float A = area (x1, y1, x2, y2, x3, y3);
/* Calculate area of triangle PBC */
float A1 = area (x, y, x2, y2, x3, y3);
/* Calculate area of triangle PAC */
float A2 = area (x1, y1, x, y, x3, y3);
/* Calculate area of triangle PAB */
float A3 = area (x1, y1, x2, y2, x, y);
/* Check if sum of A1, A2 and A3 is same as A */
return (A == A1 + A2 + A3);
}
/* Driver program to test above function */
int main()
{
/* Let us check whether the point P(10, 15) lies inside the triangle
formed by A(0, 0), B(20, 0) and C(10, 30) */
if (isInside(0, 0, 20, 0, 10, 30, 10, 15))
printf ("Inside");
else
printf ("Not Inside");
return 0;
}
Tiempo: O (1)
Espacio: O (1)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-07-10 12:26:26
Tome el promedio de los tres puntos dados. Este nuevo punto P4 siempre estará dentro del triángulo.
Ahora compruebe si P y P4 se encuentran en el mismo lado de cada una de las tres líneas P1P2 P2P3 y P3P1. Puede hacer esto comprobando los signos de los productos cruzados (P -> P1) x (P -> P2) y (P4 -> P1) x (P4 -> P2) (donde P->P1 es el vector de P a P1), y luego los otros dos pares.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-11-09 01:49:51