编程之美 4.4点是否在三角形内

问题：如果一个二维坐标系中，已知三角形三个点的坐标，那么对于任意一点，如何判断其在三角形内呢？（点在三角形边上也算在三角形内）

解法一：面积法

S=Area（ABC）、S1=Area（ABP）、S2=Area（BCP）、S3=Area（CAP）

若P点在三角形内，S=S1+S2+S3

若P在三角形外，S1+S2+S3>S

计算三角形的面积可以使用海伦公式

而公式里的p为半周长（周长的一半）：

但注意了我们可以利用向量积的几何意义以两个向量为邻边的平行四边形的面积（即三角形面积的2倍）

若 |AB×BP| + |BC×CP| + |CA×AP| = |AB×BC|，则得点 P 在 △ABC 内。

解法二：叉乘法

沿 △ABC 各有向边按一定方向走（顺时针或逆时针），判断点 P 是否在该边的某侧（右侧或左侧），若点 P 在三条边的同侧，则点 P 在 △ABC 内。

分别计算向量 AB、BC、CA 与向量 AP、BP、CP 的向量积（叉乘），若三个结果均同号（正或负，为零表示 P 在边上），则可得点 P 在 △ABC 内。

其中AB = B - A，AB×AP = AB.x*AP.y - AB.y*AP.x即 x1y2-y1x2。

其实不止三角形对于凸多边形也是可以通过叉乘法来判断的。

补充知识：

所谓凸多边形，就是把一个多边形任意一边向两方无限延长成为一条直线，如果多边形的其他各边均在此直线的同旁，那么这个多边形就叫做凸多边形。

下面是示例代码：注意面积法对输入的点序没要求，叉乘法就要按逆时针的顺序。

#include <iostream>
#include <cmath>
using namespace std;

struct point
{
    double x,y;
    point(double _x=0,double _y=0)
    {
        x=_x;
        y=_y;
    }
};

inline double VecProduct(point A,point B,point P)
{
    return (B.x-A.x)*(P.y-A.y)-(B.y-A.y)*(P.x-A.x);
}

double TriArea(point A,point B,point P)
{
    return abs((B.x-A.x)*(P.y-B.y)-(B.y-A.y)*(P.x-B.x));
}

//method:Area
bool isInTriangle1(point A,point B,point C,point P)
{
    double sABP,sBCP,sCAP,sABC;
    sABP=TriArea(A,B,P);
    sBCP=TriArea(B,C,P);
    sCAP=TriArea(C,A,P);
    sABC=TriArea(A,B,C);
    if (sABC==sABP+sBCP+sCAP)
    {
        return true;
    }
    return false;
}
//method:Vector Product,ABC anticlockwise
bool isInTriangle2(point A,point B,point C,point P)
{
    if (VecProduct(A,B,P)>=0 && VecProduct(B,C,P)>=0 && VecProduct(C,A,P)>=0)
    {
        return true;
    }
    return false;
}

void main()
{
    point A(0,2);
    point B(0,0);
    point C(2,0);

    point P1(1,1);//in the Triangle
    point P2(4,4);//outside the Triangle 
    point P3(2,0);//on the edge of the Triangle

    cout<<boolalpha<<isInTriangle1(A,B,C,P1)<<endl;
    cout<<boolalpha<<isInTriangle1(A,B,C,P2)<<endl;
    cout<<boolalpha<<isInTriangle1(A,B,C,P3)<<endl;

    cout<<boolalpha<<isInTriangle2(A,B,C,P1)<<endl;
    cout<<boolalpha<<isInTriangle2(A,B,C,P2)<<endl;
    cout<<boolalpha<<isInTriangle2(A,B,C,P3)<<endl;
}

编程之美 4.4点是否在三角形内

推荐阅读