摘 要 本文提出一种新方法以检测一个点是否在多边形内。该方法将矢量和射线法结合，彻底解决了射线法所具有的奇异情况。实验结果证明，该方法具有简单、易实现、快速等优点。
1．引言
判断点在多边形内外是计算机图形学的最基本算法，在计算机图形处理、模式识别、CAD 及科学计算可视化中有着广泛的应用。判断点在多边形内外的算法有主要有定向射线法、角度法。角度法要使用复杂的三角运算，计算量大；在工程上应用最多的是定向射线法，这种方法简单、可靠，但其难以处理对边界点及边界与射线共线等特殊情况的处理。
2．基本概念
假设OA、OB是非零矢量，将OA绕点O旋转到与OB方向相同的位置时，所形成的角称为有向角<AOB。规定逆时针旋转为正方向，顺时针旋转为负方向。
设线段s的两个顶点为a和b，则s与直线l所形成的关系可划分为三大类：（a）ｓ有且仅有一个顶点（a或者b）在ｌ上，称这种关系为半跨越；（b）ｓ的两个顶点a和b分别在ｌ的两侧，称这种关系为跨越；（c）ｓ的两个顶点a和b在ｌ的同一侧或线上，称这种关系为未跨越。
过点Q作ｘ正方向的水平射线ｌ。若线段s跨越（或半跨越）射线ｌ且与点Q所成的有向角为正，称为正向跨越（或正向半跨越），否则称为负向跨越（负向半跨越）。如图1
附件:
您所在的用户组无法下载或查看附件 ，线段P1P2、P3P4、P4P5、P6P7都属于正向半跨越直线l，P2P3、P5P6属于负向半跨越直线l，线段P7P8属于负向跨越直线l，线段P8P9、P0P1属于未跨越直线l。设线段s与射线ｌ交于点ｋ，那么线段s可以看作线段ak，kb组合而成（如图1中的P7P8可看作由P7k、kP8矢量和）。若将s与l的关系用f（s，l）的值来表示其权重，如下表示：
附件:
您所在的用户组无法下载或查看附件3．多边形内外点判定算法
在本文中，假定多边形P的顶点P0、P1、…，Pn（=P0）按逆时针方向存储，同样可将多边形看作有n条有向线段Si，即 （i=1，…，n-1），头尾相连而成。
定理1．过平面上任意一点Ｑ作ｘ正方向的水平射线ｌ，若∑f(Si,l)=0(其中i>=0,i<n)，则点Ｑ在多边形P外。
证明：设射线ｌ与多边形Ｐ的Si交点为kj，且kj不属于多边形P的顶点，则将交点分别插入到Pi、Ｐi+1之间形成两条有向线段Pikj、kjPi+1。将所有此类交点都添加进到顶点序列中，形成一个新的多边形P’，顶点序列为P0、…、Pi、kj、Pi＋1、…Pm、kk、Pm＋1、 Pn（=P0），如图2
附件:
您所在的用户组无法下载或查看附件（a）形成的顶点序列为P0、P1、k0、P2、P3、P0。因此多边形Ｐ’的有向线段与射线ｌ的跨越情况全部转换为半跨越，如图2（b、c、d、e）四类情况。若将点Ｑ与多边形P’的各个顶点相连，组成一系列有向角。在多边形P’中任选一个在射线ｌ上的点ki作为起始点，则每两个交点之间的所有有向线段所组成的有向角的代数和的关系如图2（b、c、d、e）所示。显然可以得出时，有向角的角度代数和为0，所以点Ｑ在多边形P’外，因P’与Ｐ同构，因此，点Ｑ在多边形Ｐ外。
定理2．过平面上任意一点Ｑ作ｘ正方向的水平射线ｌ，若∑f(Si,l)=0(其中i>=0,i<n) 的值为2或者-2，则点Ｑ在多边形P内。
证明过程与定理1证明类似，可以得出 值为2或者-2时，有向角的角度代数和为360或者-360度，从而可以得出点Q在多边形Ｐ内。
算法的具体描述：
（1）获得一个点Pi相对与点Ｑ的位置，如果Pi的ｙ坐标值大于Ｑ的ｙ坐标值，status=1，若小于，则status=-1，否则statue=0；用lastStatus记录上一点的相对位置值。cnt表示f（si,l）的代数和。
2）temp = status – lastStatus;
if(temp > 0)
{
if(点Ｑ在有向线段Pi－1Pi的右侧)
cnt = cnt + temp;
else if (点Ｑ在有向线段Pi－1Pi上)
return(“点Ｑ在有向线段Pi－1Pi上”);
}
else if(temp < 0)
{
if(点Ｑ在有向线段Pi－1Pi的左侧)
cnt = cnt + temp;
else if (点Ｑ在有向线段Pi－1Pi上)
return(“点Ｑ在有向线段Pi－1Pi上”);
}
（3）循环（2），直到多边形所有的顶点遍历完毕，
if(cnt == 0)
return(“点在多边形外”);
else return(“点在多边形内”);
4．算法分析和小结
射线法的复杂度为O(n)，本文算法的复杂度也为O(n)。射线法中对每一条边都要进行两次以上的乘法运算，而本算法只对跨越或者半跨越射线的边最多进行一次叉积运算；射线法需要对奇异情况进行特殊处理，而本算法彻底解决了奇异情况的发生。在本文中，最坏的情况是所需的计算量为（8次加减运算，2次乘法运算）*ｎ。
