从公众号转载，关注微信公众号掌握更多技术动态

---------------------------------------------------------------

普遍有三种方式

• 面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。

• 夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。

• 引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。

今天我们主要讲解一下引射线法。

一、理论基础

1.引射线法是什么

    将测试点的Y坐标与多边形的每一个点进行比较，会得到一个测试点所在的行与多边形边的交点的列表。在下图的这个例子中有8条边与测试点所在的行相交，而有6条边没有相交。如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。在这个例子中测试点的左边有5个交点，右边有三个交点，它们都是奇数，所以点在多边形内。

2.数理基础

(1)斜率

斜率公式(yi - y)/(A - xi)=(yi - yi+1)/(xi+1-xi)====>(yi-y)/(yi-yi+1)=(A-xi)/(xi+1-xi)===>A=( y -yi)/( yi+1-yi)* (xi+1-xi)+ xi

(2)三角函数

sin，称为正弦，sinθ=对边/斜边；

cos，称为余弦，cosθ=邻边/斜边；

tan，称为正切，tanθ=对边/邻边。

(3)叉乘

向量a×向量b（×为向量叉乘），若结果小于0，表示向量b在向量a的顺时针方向；若结果大于0，表示向量b在向量a的逆时针方向；若等于0，表示向量a与向量b平行。（顺逆时针是指两向量平移至起点相连，从某个方向旋转到另一个向量小于180度）

OA×OB = 2 > 0， OB在OA的逆时针方向；OA×OC = -2 < 0,OC在OA的顺势针方向。即叉乘结果大于0，后一个在前一个的逆时针方向；小于零，后一个在前一个的顺时针方向。

(4)叉积用法

①矢量的概念

如果一条线段的端点是有次序之分的，把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。

矢量加减法及距离公式：

设二维矢量P(x1,y1),Q(x2,y2),则矢量加法定义为：P+Q=(x1+x2,y1+y2)，同样有矢量减法就不赘述了。并且有满足交换律，和结合律，分配律。

距离公式：

假设两点P(x1,y1),Q(x2,y2)，其距离为sqrt((x1-x2)(x1-x2)+(y1-y2)(y1-y2)

double dist(point p,point q){ return sqrt((x1-x2)(x1-x2)-(y1-y2)(y1-y2)); }

②矢量叉积

计算叉积的作用有非常多，是直线和线段的核心算法。设P(x1,y1),Q(x2,y2),则其叉积为P×Q=x1y2-x2y1。

double cross(point a,point b){ return a.xb.y-a.yb.x; }

叉积具有一个重要性质是可以通过它的符号判断两个矢量相互之间的顺逆时针关系：

若P×Q>0 则P在Q的顺时针方向

若P×Q<0 则P在Q的逆时针方向

若P×Q=0 则P与Q共线，但有可能为同向或反向

矢量叉积可以看作原点,P点,Q点三点，因此可以推广成任意的3个点来判断它们之间的关系。

假设P(x1,y1)，Q(x2,y2)，R(x3,y3)三点,

将P和Q连接,对P,Q,R三点进行叉积即:

K=x1y2-x2y1+x2y3-x3y2+x3y1-x1y3

若K>0,其意义为在P点，面向Q点，R在PQ线段的左边

若K<0,其意义为在P点，面向Q点，R在PQ线段的右边

若K=0,其意义为在P点，面向Q点，R在PQ线段上

int mul(point a,point b,point c){    double k=x1y2-x2y1+x2y3-x3y2+x3y1-x1y3;    if(k>eps)return 1;    else if(k<-eps)return -1;    else return 0;}

③判断点是否在矩形中

    只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。但如果点不规则就不好判断，那么我们又可以用到叉积：判断一个点是否在两条线段之间夹着就转化成，判断一个点是否在某条线段的一边上，就可以利用叉乘的方向性，来判断夹角是否超过了180度

设E为任意点，ABCD为矩形

那么我们只要判断(AB×AE)（CD×CE）>=0并且(DA×DE)（BC×BE)>=0。

struct Rec{point a,b,c,d;}bool pointisinRectangle(point e,Rec r){if(mul(r.a,r.b,r.e)*mul(r.c,r.d,e)>=0&&mul(r.d,r.a,e)*mul(r.b,r.c,e)>=0)return true;else return false;}

④判断两条线段是否相交

判断两条线段的 x , y 区间在坐标轴上的投影有没有重合，设两条线段 A-B, C-D

若

 则两条线断必定不相交

假设有两条线段AB，CD，若AB，CD相交，我们可以确定：

• 线段AB与CD所在的直线相交，即点A和点B分别在直线CD的两边；

• 线段CD与AB所在的直线相交，即点C和点D分别在直线AB的两边；

上面两个条件同时满足是两线段相交的充要条件，所以我们只需要证明点A和点B分别在直线CD的两边，点C和点D分别在直线AB的两边，这样便可以证明线段AB与CD相交了。

线段AB与线段CD相交，于是我们可以得到两个向量AC，AD，C和D分别在AB的两边，向量AC在向量AB的逆势针方向，AB×AC > 0；向量AD在向量AB的顺势针方向，AB×AD < 0，两叉乘结果异号。

这样，方法就出来了：如果线段CD的两个端点C和D，与另一条线段的一个端点（A或B，只能是其中一个）连成的向量，与向量AB做叉乘，若结果异号，表示C和D分别在直线AB的两边，若结果同号，则表示CD两点都在AB的一边，则肯定不相交。

当然，不能只证明C，D在直线AB的两边，还要用相同的方法证明A，B在直线CD的两边，两者同时满足才是线段相交的充要条件。

否则，用叉积判断；

若Ｐ×Ｑ > 0，则Ｐ在Q的顺时针方向

若Ｐ×Ｑ < 0，则Ｐ在Q的逆时针方向

若Ｐ×Ｑ == 0，则P与Ｑ平行

对于线段Ａ-B, C-D

若　(A-C × C-D )*(B-C × C-D) <= 0,　则Ａ和Ｂ在C-D的异侧，等号表示临界情况

若　Ａ和Ｂ在C-D的异侧＆＆Ｃ和Ｄ在Ａ-Ｂ的异侧，则 A-C 和 B-D 相交

否则不相交

⑤线段相交特殊情况——只有1点相交

线段AB与CD相交于C点，按照之前介绍的方法，我们可以连成两向量AD和AC，这时候，我们发现，AC与AB共线，AB×AC = 0；而AB×AD < 0；两者并不异号，可实际上仍然相交。所以当出现两叉乘结果中，有一方为0，也可以看成点CD在直线AB的两边。

⑥线段相交特殊情况——两条线段重合

线段AB与线段CD重合，重合部分为CB，这种重合的情况要特殊判断：

首先，我们给没条线段的两个端点排序，大小判断方法如下：横坐标大的点更大，横坐标相同，纵坐标大的点更大。

排好序后，每条线段中，小的点当起点，大的当终点。我们计算向量AB×向量CD，若结果为0，表示线段AB平行CD，平行才有了重合的可能；但平行也分共线和不共线，只有共线才有可能重合

第一种情况不共线，第二种情况共线。那如何来判断是否共线呢？

我们可以在两条线段中各取一点，用这两点组成的向量与其中一条线段进行叉乘，结果若为0，就表示两线段共线，如下图：

我们取向量BC，若BC×CD = 0，表示两点共线，即是第二种情况，否则就是第一种情况。第一种情况肯定不相交。即使他们共线，却还是不一定重合，就如上图中第二种情况。这时候，之前给点排序的妙处就体现出来了：若一条线段AB与另一条线段CD共线，且线段AB的起点小于等于线段CD的起点，但线段AB的终点（注意是终点）大于等于线段CD的起点（注意是起点），或者交换一下顺序，CD的起点小于AB的起点......只要满足其中一个，就表示有重合部分。

3.射线法产生原理

    首先，对于平面内任意闭合曲线，都可以直观地认为，曲线把平面分割成了内、外两部分，其中“内”就是我们所谓的多边形区域。

基于这一认识，对于平面内任意一条直线，可以得出下面这些结论：

• 直线穿越多边形边界时，有且只有两种情况：进入多边形或穿出多边形。

• 在不考虑非欧空间的情况下，直线不可能从内部再次进入多边形，或从外部再次穿出多边形，即连续两次穿越边界的情况必然成对(穿入一定会穿出)。

• 直线可以无限延伸，而闭合曲线包围的区域是有限的，因此最后一次穿越多边形边界，一定是穿出多边形，到达外部。

假如从一个给定的点做射线，还可以得出下面两条结论：

• 如果点在多边形内部，射线第一次穿越边界一定是穿出多边形。

• 如果点在多边形外部，射线第一次穿越边界一定是进入多边形。

可以归纳出：

当射线穿越多边形边界的次数为偶数时，所有第偶数次（包括最后一次）穿越都是穿出，因此所有第奇数次（包括第一次）穿越为穿入，由此可推断点在多边形外部。 

当射线穿越多边形边界的次数为奇数时，所有第奇数次（包括第一次和最后一次）穿越都是穿出，由此可推断点在多边形内部。 

4.特殊情况

(1)点在多边形的边上

判断点是否在线上的方法有很多，比较简单直接的就是计算点与两个多边形顶点的连线斜率是否相等

(2)点在多边形顶点上

点和多边形顶点重合的情况更简单，直接比较点的坐标就行了。

(3)射线经过多边形顶点

射线刚好经过多边形顶点的时候，应该算一次还是两次穿越？

顶点穿越看似棘手，其实我们换一个角度，思路会大不相同。射线穿越一条线段需要什么前提条件？没错，就是线段两个端点分别在射线两侧。只要想通这一点，顶点穿越就迎刃而解了。这样一来，只需要规定被射线穿越的点都算作其中一侧。

假如我们规定射线经过的点都属于射线以上的一侧，显然点D和发生顶点穿越的点C都位于射线Y的同一侧，所以射线Y其实并没有穿越CD这条边。而点C和点B则分别位于射线Y的两侧，所以射线Y和BC发生了穿越，由此我们可以断定点Y在多边形内。同理，射线X分别与AD和CD都发生了穿越，因此点X在多边形外，而射线Z没有和多边形发生穿越，点Z位于多边形外。

(4)射线刚好经过多边形的一条边

射线连续经过了多边形的两个相邻顶点。

射线连续经过的两个顶点显然都位于射线以上的一侧，因此这种情况看作没有发生穿越就可以了。由于第三点的解决方案实际上已经覆盖到这种特例，因此不需要再做特别的处理。