判断点是否在三角形内

判断点是否在三角形内

问题：

在二维坐标系中，已知三角形顶点的坐标，那么对于坐标系中的任意一点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;
}