资源描述：
《基于顶点与邻边相关性的多边形填充算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第9卷第11期中国图象图形学报Vol.9,No.112004年11月JournalofImageandGraphicsNov.2004基于顶点与邻边相关性的多边形填充算法马辉陆国栋谭建荣吴良(浙江大学CAD&CG国家重点实验室,杭州310027)(BrownUniversity,Providence,RhodeIsland,U.S.A)摘要为了加快多边形填充算法的运算速度,在深入挖掘顶点与相邻边关系对填充算法影响的基础上,提出了一种基于顶点与邻边相关性的多边形填充算法。该算法首先归纳了多边形顶点与邻边相关性的5种典型类型,然后依据顶点与邻边的相
2、关性,对原有多边形进行了分割与重新组合,使其完全由简单的三角形和梯形这样的单元区域组成,这样就将复杂的多边形填充问题转化为这些单元区域的填充问题,并由此将扫描线与多边形边求交的乘除计算转化为加减运算。通过实验分析,新算法大大减少了运算的时间和复杂度,从而为多边形填充创造了一种有效的新途径。关键词多边形填充顶点与邻边相关性中图法分类号:TP391.41文献标识码:A文章编号:100628961(2004)1121336206ANewPolygonFillingAlgorithmBasedonPertinenceBetweenPointandIts
3、AbuttingSidesMAHui,LUGuo2dong,TANJian2rong(StateKeyLaboratoryofCAD&CGatZhejiangUniversity,Hangzhou310027)WULiang(BrownUniversity,Providence,RhodeIsland,U.S.A)AbstractPresentpolygonfillingalgorithmsincludingscanlinealgorithm,seedfillingalgorithmandthealgorithmsbasedonthetwocl
4、assicalfillingtheories,areanalyzedandcomparedinthispaper.Anewfillingalgorithmisputforward,whichisbasedonthoroughanalysisoftherelationsbetweenpointanditsabuttingsides.Thisnewfillingalgorithmdividesallpointsofapolygonintofivetypesatfirstly,andtransformsthepolygonintounitareasw
5、hicharesimpletrianglesandtrapeziumsbythelinepassingthepoints.Usingthecharacteristicsofbeveledges,theunitareasfillingcanreplacethemultiplication2divisionwiththeaddition2subtraction.Itdecreasesthetimeandcomplexityoffillingthewholepolygon.Thispaperexplainsthedesignofthealgorith
6、mandhowitisgoingon,andalsopresentsthedatastructuresstoringtheinformationofpointsandunitareas.Intheend,someexperimentalresultsshowthatthenewalgorithmhasahighefficiencyandagoodstability.Keywordspolygon,fillalgorithm,pertinencebetweenpointanditsabuttingsides的底端为止,即先用一根根水平线进行扫描,
7、并求得1引言每一条水平扫描线与多边形各边的交点,然后将交点配成“交点对”,并在其间进行填充;后者是先给定众所周知,多边形的填充问题是计算机图形学区域内的一点为种子点,并对其赋予指定的颜色,然的基本问题之一。近年来,随着多媒体技术的不断发后将这种颜色扩充到区域内所有的点。展,对这一问题的研究更是引起了人们的关注。传统此后,在经典算法的基础上有了很多改进,如,的多边形填充经典算法有扫描线填充算法和种子填对于扫描线填充算法,文献[1]归纳了奇偶扫描转换充算法两种。前者是从多边形的顶端开始,到多边形算法和有序边表扫描算法以及这两种算法的改进;基金项目:
8、创新群体科学研究基金项目(60021201);教育部博士点基金项目(20020335093)收稿日期:2004202206;改回日期:20042062
