math - triangulo - como saber si un punto pertenece a una recta

determinar si el punto se encuentra dentro del triángulo

Question

El programa necesita leer los valores de tres coordenadas

• P1 (x1, y1)
• P2 (x2, y2)
• P3 (x3, y3)

así como también otra coordenada P (x, y) y determinar si este punto está dentro de un triángulo formado a partir del punto 3 anterior.

Answer 1

En lugar de P1, P2 y P3, supongamos que los puntos son 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 incluye 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)

Answer 2

La forma correcta de hacerlo es calculando las coordenadas baricéntricas del cuarto punto dados los tres puntos de tu triángulo. La fórmula para calcularlos se da al final de la sección "Convertir a coordenadas baricéntricas", pero espero proporcionar aquí una explicación menos matemática.

Supongamos, por simplicidad, que tiene una estructura, point , que tiene valores 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, las coordenadas baricéntricas, 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 todas las alpha , beta y gamma son mayores que 0 , entonces el punto p encuentra dentro del triángulo formado por los 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 las coordenadas baricéntricas, pero creo 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 conecté arriba.

Se deduce que cada coeficiente debe ser mayor que 0 para que el punto p encuentre dentro del área descrita por los tres puntos.

Answer 3

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 hacerlo 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.