42

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

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

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

4

3 回答 3

63

正确的方法是在给定三角形的三个点的情况下计算第四个点的重心坐标。计算它们的公式在“转换为重心坐标”部分的末尾给出，但我希望在这里提供一个较少数学强度的解释。

为简单起见，假设您有一个结构体 ，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

重新排列此函数可为您提供计算重心坐标的公式，但我觉得这样做的步骤可能超出了问题的范围。它们在我链接到顶部的 Wikipedia 页面上提供。

因此，每个系数必须大于 0，才能使该点p位于三个点所描述的区域内。

于 2012-11-09T01:56:57.870 回答
21

假设点为 A、B 和 C，而不是 P1、P2 和 P3。

          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)

于 2014-07-10T12:26:26.217 回答
5

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

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

于 2012-11-09T01:41:03.297 回答