确定点是否位于三角形内

Question

程序需要读取三个坐标的值

• P1(X1,Y1)
• P2(x2,y2)
• P3(X3,Y3)

以及另一个坐标P(x,y)并确定该点是否在由上述3点形成的三角形内.

Answer 1

这样做的正确方法是在给定三角形的三个点的情况下计算第四个点的重心坐标.计算它们的公式在"转换为重心坐标"一节的末尾给出,但我希望在这里提供一个不那么数学强烈的解释.

为简单起见,假设您有一个结构point,它具有值x和y.您将点数定义为:

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.

现在,重心坐标,通常被称为alpha,beta和gamma,计算如下:

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;

如果所有的alpha,beta以及gamma是大于0,然后点p在于提出的各点的三角形内p1,p2和p3.

这背后的解释是,可以使用三角形的点和三个系数(每个点一个,在[0,1]范围内)描述三角形内的点:

p = (alpha)*p1 + (beta)*p2 + (gamma)*p3

重新排列此功能为您提供计算重心坐标的公式,但我觉得这样做的步骤可能超出了问题的范围.它们在我链接到的维基百科页面上提供.

因此,每个系数必须大于0,以使该点p位于由三个点描述的区域内.

Answer 2

而不是P1,P2和P3,让我们假设点为A,B和C.

          A(10,30)
            / \
           /   \
          /     \
         /   P   \      P'
        /         \
B (0,0) ----------- C(20,0) 

算法:

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.

以下是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;
}

时间: O(1)

空间: O(1)

Answer 3

取三个给定点的平均值.这个新点P4将始终位于三角形内.

现在检查P和P4躺在每三行的同一侧P1P2 P2P3和P3P1.您可以通过检查交叉积的符号(P -> P1) x (P -> P2)和(P4 -> P1) x (P4 -> P2)(其中P-> P1是从P到P1的向量),然后检查其他两对来做到这一点.