判断点是否在三角形内
问题:
在二维坐标系中,已知三角形顶点的坐标,那么对于坐标系中的任意一点P,判断是否在三角形内?
-
方法一
如图,将点P与三角形三个点连接,比较三角形ABC的面积与三角形ABD,BCD,ACD面积之和的大小从而判断点是否在三角形内。
double Area(point A, point B, point C)
{
double a, b, c = 0;
a = sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
b = sqrt((B.x - C.x)*(B.x - C.x) + (B.y - C.y)*(B.y - C.y));
c = sqrt((C.x - A.x)*(C.x - A.x) + (C.y - A.y)*(C.y - A.y));
double p = (a + b + c) / 2;
return sqrt((p - a) * (p - b) * (p - c) * p);
}
bool IsTriangle(point A, point B, point C, point D)
{
return (Area(A, B, D) + Area(B, C, D) + Area(A, C, D) <= Area(A, B, C));
}
设S = Area(ABC),S1 = Area(ABD),S2 = Area(BCD),S3 = Area(ACD)。
如果S = S1 + S2 + S3,那么点P在三角形内部或边上;如果S1 + S2 + S3 > S,则点P在三角形外部。
-
方法二
如果有一个点P在三角形的内部,那么它一定在在边AB,BC,CA的左边。
判断一个点P是否在一条射线P1P2的左边,可以通过P1P2,P1P两个向量叉积的正负来判断。
如果叉积为正,则P在射线P1P2的左边,若果叉积为负,则P在射线P1P2的右边,如果叉积为0,则P在射线P1P2上。
double Calcu(point A, point B, point C)
{
return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
}
bool IsTriangle(point A, point B, point C, point D)
{
if (Calcu(A, B, D) >= 0 && Calcu(B, C, D) >= 0 && Calcu(C, A, D) >= 0)//ABC位置不能调换 射线有方向
{
return true;
}
return false;
}