包容性测试算法综述黄吉祥
9页1、包容性测试综述学号:2010210556姓名:黄吉祥引言包容性测试指的是判断点是否在多边形内外,是计算机图形学的最基本算法,在计算机图形处理、模式识别、CAD及科学计算可视化中有着广泛的应用。包容性测试常规的算法有符号判别法、角度判别法、Griffiths判别法等方法。角度判别法要使用复杂的三角运算,计算量人;在工程上应用最多的是定向射线法,这种方法简单、可靠,但其难以处理对边界点及边界与射线共线等特殊情况的处理。今年来,人们提出了基于可见边的点在多边形内外判断以及通过多边形进行层次化存储,可以缩短检测处理所需要的时间等方法。这些方法主要从可靠性、计算量等方面进行了改进。本文所提出的一种新的方法通过将有向角和射线法结合,彻底解决了射线法所具有的奇异情况,具有简单、快速、易实现等优点。二算法综述1常规算法符号判别法如果图形是凸n多边形(只含一个坏)。建立形成多边形的环的走向,保证边向量左侧为多边形的内部。求取通过各边向量的直线的方程系数(A,E,G)Q1,2,n)o设被测试点为T(Xt,yt),计算P=A兀+Bxyt+C(1=1,2,n)的值。一旦有一个D0(或D=0),则被测试点在多边
2、形的外部(或在边界上),判断结束。贝IJ,所有的Dx0,而T却在多边形的内部。角度判别法P=ppp2pn是一个顶点为Pi(,),1=1,2,.,n的封闭多角形,R是一个测试点。ptpx为连接pt和px的诸向量,CL、表示向量Rp】到口P】+i的夹角。若工乞二H在P的外面;若工二2,pt在P的里面。角度判别法的特点 这种角度的计算不需要很高的精度,其误差甚至可以达到R也不失判别的正确性。 必须计算两向量间的夹角而涉及到反三角函数的计算,计算工作量较大。 计算量与符号判别法同是O(n),但要比符号判别法的工作增加几倍。 其适用性能从凸多边形扩展到一般多边形。Griffiths判别法为了在角度判别法中避免求取反三角函数,Griffiths在1981年(CADJANUARY1981NUMBER】V0113)提出了一种近似的方法以加快运算速度。其基本原理是:矢量积PtP/PtPi*与sin0】成正比,而数量积以卩図口口*与cosa】成正比,于是坨匕或ctg可由这两个枳的结果导出。角度冬可由卜列近似的线性逼近公式求得:arctgx=n/4xx+C式中7188.35当0SXG时,使用线性逼近公式ar
3、ctgx=ti/4xx+C的最大误差是土C,并且在X=0,X=J-i-l,和X=1处出现。从最坏的情况处看,即使每次都取得最人误差,那么只要多角形不人于88边形,所得的包容性测试还是准确的。这个近似公式直观而简单,且避免了三角函数的计算,能够满足常规应用。半射线交点计数判别法令R是一条以P为起点任何方向的半射线。当R和多角形的交点个数为奇数个时,点P在多角形的内部;当交点个数为偶数或为零时,点P在多角形的外部。用这种方法来判别的困难在于当所选择的半射线通过多角形的顶点,或者和多角形的边重合时,交点应如何记数的问题。r半射线交点计数包容性测试算法建立射线由点Pt(兀,y向点(X8,乳)建立一射线向量。其中X8是一个多角形顶点不可能达到的X人值,X意味着射线和X轴平行;求交点将此射线向量和多角形的各边向量求交。并记录交点几何参数和相对于射线和特征值,并将交点按其射线方向排队; 合并重点判别相邻交点的几何参数,如为重点,则求其特征值的代数和,如代数和为零,则取消两个交点,否则取消其中一个交点; 合并相邻同特征交点判别相邻两个交点的特征,如果相邻两个特征相同,则取消其中一个交点; 判别计算交点
《包容性测试算法综述黄吉祥》由会员桔****分享,可在线阅读,更多相关《包容性测试算法综述黄吉祥》请在金锄头文库上搜索。
2015年小学教学常规生调查问卷
最新沂新中学-上学期第二次月考 八年级生物试题名师精心制作教学资料
制订你的学习计划
2023年房地产销售员工转正工作总结(精选5篇)_销售员工转正工作总结
气化岗位专项说明书终版
沥青混凝土路面综合施工专题方案模板
2023年医院儿科护士长的个人工作计划标准模板(二篇)
锚杆挡土墙施工方案
五一国际劳动节演讲稿:劳动光荣
老师教化感言
吸水率及饱和吸水率测定方法
好用的优秀中学作文集合10篇
审计()--审计概述-课后作业
不间断电源项目创业计划书写作模板
曹妃甸昱海澜湾一期C区施工合同结构设计说明
二级医院等级评审工作实施方案
人教版二年级语文下册教材研说
(发展战略)世界科技强国发展简史
2013年辽宁二级建造师继续教育考试题[1]
转正个人自我鉴定范文六篇
2023-10-01 9页
2023-07-27 5页
2024-01-21 30页
2023-08-13 42页
2022-10-23 13页
2023-08-25 4页
2022-09-18 6页
2022-09-13 5页
2023-07-04 11页
2023-10-15 7页