包容性测试算法综述黄吉祥

1、包容性测试综述学号：2010210556姓名：黄吉祥引言包容性测试指的是判断点是否在多边形内外，是计算机图形学的最基本算法，在计算机图形处理、模式识别、CAD及科学计算可视化中有着广泛的应用。包容性测试常规的算法有符号判别法、角度判别法、Griffiths判别法等方法。角度判别法要使用复杂的三角运算，计算量人；在工程上应用最多的是定向射线法，这种方法简单、可靠，但其难以处理对边界点及边界与射线共线等特殊情况的处理。今年来，人们提出了基于可见边的点在多边形内外判断以及通过多边形进行层次化存储，可以缩短检测处理所需要的时间等方法。这些方法主要从可靠性、计算量等方面进行了改进。本文所提出的一种新的方

2、法通过将有向角和射线法结合,彻底解决了射线法所具有的奇异情况，具有简单、快速、易实现等优点。二算法综述1常规算法符号判别法如果图形是凸n多边形（只含一个坏）。建立形成多边形的环的走向，保证边向量左侧为多边形的内部。求取通过各边向量的直线的方程系数（A，E，G）Q1,2,n）o设被测试点为T（Xt，yt）,计算P=A兀+Bxyt+C（1=1,2,n）的值。一旦有一个D0（或D=0）,则被测试点在多边形的外部（或在边界上），判断结束。贝IJ,所有的Dx0,而T却在多边形的内部。角度判别法P=ppp2pn是一个顶点为Pi(，),1=1,2,.,n的封闭多角形,R是一个测试点。ptpx为连接pt和px

3、的诸向量，CL、表示向量Rp】到口P】+i的夹角。若工乞二H在P的外面;若工二2,pt在P的里面。角度判别法的特点这种角度的计算不需要很高的精度，其误差甚至可以达到R也不失判别的正确性。必须计算两向量间的夹角而涉及到反三角函数的计算，计算工作量较大。计算量与符号判别法同是O(n),但要比符号判别法的工作增加几倍。其适用性能从凸多边形扩展到一般多边形。Griffiths判别法为了在角度判别法中避免求取反三角函数，Griffiths在1981年(CADJANUARY1981NUMBER】V0113)提出了一种近似的方法以加快运算速度。其基本原理是：矢量积PtP/PtPi*与sin0】成正比，而数量

4、积以卩図口口*与cosa】成正比，于是坨匕或ctg可由这两个枳的结果导出。角度冬可由卜列近似的线性逼近公式求得:arctgx=n/4xx+C式中7188.35当0SXG时，使用线性逼近公式arctgx=ti/4xx+C的最大误差是土C,并且在X=0,X=J-i-l,和X=1处出现。从最坏的情况处看，即使每次都取得最人误差，那么只要多角形不人于88边形，所得的包容性测试还是准确的。这个近似公式直观而简单，且避免了三角函数的计算，能够满足常规应用。半射线交点计数判别法令R是一条以P为起点任何方向的半射线。当R和多角形的交点个数为奇数个时，点P在多角形的内部；当交点个数为偶数或为零时，点P在多角形的

5、外部。用这种方法来判别的困难在于当所选择的半射线通过多角形的顶点，或者和多角形的边重合时，交点应如何记数的问题。r半射线交点计数包容性测试算法建立射线由点Pt（兀，y向点（X8,乳）建立一射线向量。其中X8是一个多角形顶点不可能达到的X人值，X意味着射线和X轴平行；求交点将此射线向量和多角形的各边向量求交。并记录交点几何参数和相对于射线和特征值，并将交点按其射线方向排队；合并重点判别相邻交点的几何参数，如为重点，则求其特征值的代数和，如代数和为零，则取消两个交点，否则取消其中一个交点；合并相邻同特征交点判别相邻两个交点的特征，如果相邻两个特征相同，则取消其中一个交点；判别计算交点个数，如为奇数

6、，则点在多角形内部，否则在多角形外部。一种新的算法1基本概念设OA、OB是非零矢量，将OA绕点0旋转到与OB方向相同的位置。所形成的ZAOB称为有向角。规定逆时针旋转为正方向，顺时针旋转为负方向。设线段s的两个顶点为a和b,则s与直线1所形成的关系可划分为三大类：1-12-2a）s有且仅有一个顶点（a或者b）在1上，称这种关系为半跨越；b）s的两个顶点a和b分别在1的两侧，称这种关系为跨越；c）$的两个顶点a和b在1的同一侧或线上，称这种关系为未跨越。过点Q作x正方向的水平射线L若线段s跨越（或半跨越）射线/且与点Q所成的有向角ZaQb为正，称为正向跨越（或正向半跨越），否则称为负向跨越（负向

7、半跨越）。如图1线段PiP?、p3p4P4P5、P6P7都属于正向半跨越直线1，P2P3、P5P6属于负向半跨越直线I，线段P?Ps属于负向跨越直线I，线段PsP9、PoPi属于未跨越直线1。设线段S与射线1交于点k,那么线段S可以看作线段ak,kb组合而成（如图1中的p?Ps可看作由p7k.kps矢量和）。若将s与1的关系用f（s,1丿的值来表示其权重，如下表示：正向半跨越负向半跨越未跨越正向跨越负向全跨越2多边形内外点判定算法在本文中，假定多边形P的顶点Po、P、，Pn（=PO）按逆时针方向存储，同样可将定理一：过平面上任意一点Q作X正方向的水平射线1,若f（si?l）=O,则点Q在多边1

8、=0形P外。证明：设射线1与多边形P的s交点为kj,且kj不属于多边形P的顶点，则将交点分别插入到P：、P出之间形成两条有向线段PK、气p1+1。将所有此类交点都添加进到顶点序列中，形成一个新的多边形P,顶点序列为Po、P、kj、Apmskk、p血、pn（=p0）,如图2（a丿形成的顶点序列为Po、Pi、k。、p?、P3、p0o因此多边形P的有向线段与射线1的跨越情况全部转换为半跨越，如图2（b、c、d、e）四类情况。若将点Q与多边形P的各个顶点相连，组成一系列有向角。在多边形P中任选一个在射线/上的点k作为起始点，则每两个交点之间的所有有向线段所组成的有向角的代数和的关系如图26、c、d、e

9、；所示。显然可以得出工=0时，有向角的角度代数和为0,所以点Q在多边形P，夕卜,1=0因P与尸同构，因此，点Q在多边形P外。定理二：过平面上任意一点Q作x正方向的水平射线/,若f（6,2）的值为2或者1=0则点Q在多边形P内。n1证明过程与定理1证明类似，可以得出工f（s,l）的值为2或者-2时，有向角的角度代1=0数和为360或者-360度，从而可以得出点Q在多边形F内。算法的具体描述：1）获得一个点口相对与点Q的位置，如果P1的y坐标值人于Q的y坐标值，status,若小于，则status,否则statue=0；用laststatus记录上一点的相对位置值。ent表示f（s,l）的代数和。

10、2）temp=status-laststatus;if（temp0）if（点Q在有向线段Pi-lPi的右侧）ent=ent+temp;elseif（点Q在有向线段Pi-lPi上）return）“点Q在有向线段PiTPi上”）；elseif（temp0）if（点Q在有向线段Pi-lPi的左侧）ent=ent+temp;elseif（点Q在有向线段Pi-lPi上）return（“点Q在有向线段PilPi上”）;3)循环(2),直到多边形所有的顶点遍历完毕,if(cnt=0)return)“点在多边形外”);elsereturn)“点在多边形内”);三总结射线法的复杂度为0(11),本文算法的复杂度也为0(11)。射线法中对每一条边都要进行两次以上的乘法运算，而本算