1 什么是叉乘

a×b=c 其中|c|=|a||b|·sinθ c的方向遵守右手定则
二维向量的叉乘 （ x1 , y1 ） × ( x2 , y2 ) = x1y2 - y1x2 如果值大于0 , 则表明 ( x2 , y2 ) 在 （ x1 , y1 ）左边（左旋） ，反之在右边（右旋） ，等于0则意味着两个向量共线。如果不记得可以用(1,0)(0,1)这两个向量来辅助记忆.

下面代码定义了二维坐标系的点，并且mulCross方法返回了向量 papb × papc 的值。

typedef struct s_Point{
    int x;
    int y;
    s_Point(int  _x, int _y){
        x=_x;
        y=_y;
    }
}Point;

int mulCross(Point pa, Point pb , Point pc){
    return (pb.x-pa.x)*(pc.y-pa.y) - (pb.y-pa.y)*(pc.x-pa.x);
}

2 判断一个点是否在凸多边形的内部。

3FA6A606-6B1B-44B4-B482-70D0CA019BF0.png D1BD086B-EADC-432B-8336-43D4D0AE7147.png

上面两个图分别是点不在凸多边形内部和点在多边形内部的图片，我们沿着凸多边形顶点坐标和目标点做向量向量，若目标点在多边形内部，那么多边形顶点和目标点构成的向量会一直向一个方向旋转，即该顶点和目标点构成的向量和下一个顶点和目标点构成的向量的差集符号保持不变（下图）。

bool checkInRect(Point p[] , Point *pt , vector<int> p_vector){
    vector<int>::iterator ele;
    for (ele = p_vector.begin()+1; ele != p_vector.end(); ele++) {
        if (mulCross(*pt, p[*ele], p[*ele-1]) > 0) {
            return false;
        }
    }
    return true;
}

p_vector 维持着点集的排序的下标，保证遍历的p[i]是紧挨着的 ， 会在下面给出解释。

如果点集并不是按照顺序排列

考虑这种情况，那么我们首先应该将点集按逆(顺)时针排序。(这里选择逆时针)

首先选择最左边的点最为基准点P0，设集合S为已经确定位置的点，并且按照逆时针排序 , 然后遍历点集， 以最左边的PkP0(按逆时针旋转的最后一个向量)作为基准向量, 将PiP0和PkP0叉乘，如果PiP0在PkP0左边，则Pi插入到S最后，并且将基准向量变为PiP0 ， 如果PiP0在PkP0右边 , 则和集合S中Pk上一个点和P0构成的向量做叉集，直到在S中找到在Pi右边的那个点将pi插入到该点后面或者找到基准点直接插入到基准点后面。

例如上图2

我们 点集合 为p = [6,3,2,5,4,1] （序列和图中对应） 显然p并不是按照逆时针顺序排列

以6为基准点 加入S ， 把3也加入S中 ， 向量6-3就是基准向量 ， S = [6,3]

接着找到2 ，向量6-2在6-3的右边，S = [6,2,3]

接着5 , 在基准左边6-3的左边 , S=[6,2,3,5] 并且基准左边变为6-5;

接着4, 6-4在6-5右边 , 但是在6-3左边 ， 所以S= [6，2，3，4，5]

然后1，方法相同 S = [6,1,2,3,4,5]

排序完成了，用一个vector储存排序的下标序列。

vector<int> adjustThePoint( Point p[] , int pnum){
    
    vector<int> p_vector;
    
    if (pnum < 3) {
        return p_vector;
    }
    
    p_vector.push_back(0);
    p_vector.push_back(1);
    
    for (int i = 2; i < pnum; i++) {
        unsigned long int ii = p_vector.size()-1;
        while (ii > 0) {
            if (mulCross(p[0], p[i], p[ii]) < 0) {
                p_vector.insert(p_vector.begin()+ii+1, i);
                break;
            }
            ii--;
        }
        if(!ii){
            p_vector.insert(p_vector.begin()+1, i);
        }
    }
    
   /* vector<int>::iterator ele;
    for (ele = p_vector.begin(); ele != p_vector.end(); ele++) {
        cout << *ele << ' ';
    }*/
    
    return p_vector;
    
}

这样我们使用checkInRect的时候，就可以从p_vector中按照逆时针的顺序取出点。

如果多边形不是凸的

如果四边形不是凸的，那么上面的方法就不适用了 ， 应该采用另外一种方法 ：射线法

从目标点出发 ， 向某一方向发出一条射线 ， 如果该射线和四边形交点个数是奇数，则该点在四边形内部，若为偶数，则不在内部。（这里不再证明了）

判断两直线相交

1AFD9A8F-A70D-4587-AFD8-78943BDA0923.png B576CA2C-2149-4C3F-9617-629EB5BF53E8.png

从上面两个图可以看出 ，当两个直线相交的时候 ， 向量P1P2是夹在P1P4和P1P3中间，向量P3P4夹在P4P2和P4P1中间，这就是我们判断两直线相交的依据。

交点在其中一条直线上 和 交点在两条直线的端点上 这两种特殊情况我们应该考虑进去

bool checkCross(Point a, Point b, Point c, Point d ){
    return !(mulCross(a, b, c)*mulCross(a, b, d)<0 || mulCross(c, d, a)*mulCross(c, d, b)<0) ;
}

mulCross是上述的叉乘函数

另外我们要注意是两种特殊的情况

054EEE89-3E79-47FC-9E33-770E199E67B4.png

上述第一左边的图在两条线段上都会记做交点 ， 所以我们需要排除他
右边的图也是一样的基准直线和多边形的某边共线， 计算时候交点会变成三个。

所以我们统一成 ， 每条边的终点点坐标不算做线段内的点，共线的边也不算相交 ,代码就改写成

bool isCollineation(Point a, Point b, Point c, Point d){ //是否平行
    
    if ( (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x) ){
        return 0;
    }else{
        return 1 ;
    }
}

bool checkCross(Point a, Point b, Point c, Point d ){

    if (isCollineation(a, b, c, d)) {
        
        return false;
    }
    
    if ( mulCross(c, d, a) * mulCross(c, d, b) <= 0 ) {
        if ( mulCross(a, b, c) * mulCross(a, b, d) <= 0 && mulCross(a, b, d)!= 0 ) {
            return true;
        }
    }
    
    return false;
    
}
bool checkInRectOther(Point p[] , Point *pt , int pNum){
    
    Point basicP = Point(pt->x,1000);
    int crossNum = 0;
    
    for (int i = 1; i<pNum; i++) {
        if (checkCross(*pt, basicP, p[i-1], p[i])) {
            crossNum++;
        }
    }
    
    return crossNum%2;
}

这样就能判断出点是否在任意多边形内部了，但局限性是点P的数组必须按照顺逆时针排序，因为这样我们才能找到多边形的边。

凸包

上面我们提到了凸多边形的概念，那么对于坐标点我们要怎么样判断其是不是多边形呢？或者从众多点中找到最多点围成的凸多边形呢?

A0872D04-B4BD-43A5-99D7-D26A266A9B62.png

在上图中，当我们按逆时针遍历点集的时候，为什么我们放弃边ab而选择了ab?

**当多边形为凸的时候，按照逆时针方向排列的边向量一定是按照同一个方向旋转。所以当我们发现一个边向量和它上一个边向量旋转方向反向了，我们应该回溯到前一个点。

void maxProtrudeRect(Point p[] , size_t l , int res[]){
 
    res[0] = 0;
    res[1] = 1;
    
    int k = 2;
    int ll = 1;
    
    while ( k <= l ) {
        
        if ( ll == 0 || mulCross(p[res[ll]], p[k%l], p[res[ll-1]]) >= 0 ) {
            ll++ ;
            res[ll] = k;
            k++;
        }else{   
            ll--;
        }
    }
}

为了简单起见 我默认了p[0]这个点是在多边形里面的，关于起始点的选择可以选择y轴最小的。res[]数组里面是最大凸变形点的下标。
如果只是需要判断点集组成的是不是凸多边形，只要在else中直接返回false就可以了。

如果点集并没有按照顺序排列，那么就需要采取别的方法了,另一个排序的方法是找到多边形内部的一个点，作为基准点，和上面的点排序算法几乎一模一样，唯一不同的是我们把基准点选在了内部的某一个点，而不是四边形边的端点。这两种排序方法几乎效果一样，并不能满足到非凸多边形的情况。

另一种思考

从数学的角度，如果一个点在凸多边形内部的话，那么他和每个端点连线线段的夹角相加应该等于360度。
显然这种方法比上面的算法更加复杂一点。