资源描述：
《区域填充扫描线算法的改进_任继成 (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第10卷第6期计算机辅助设计与图形学学报Vol.10,No.61998年11月J.CAD&CGNov.,1998区域填充扫描线算法的改进任继成刘慎权(中国科学院计算技术研究所CAD开放实验室北京100080)摘要对经典区域填充扫描线算法进行了改进,改进算法不但消除了经典算法中象素点颜色判读的重复操作,而且利用相邻扫描线填充次序上的连贯性,消除了不必要的回溯处理,并减少了回溯扫描区间.最后,给出了算法之间的效率比较,由比较结果可以看出本文的算法较大幅度地提高了算法的效率.关键词区域填充,扫描线算法,4-连通区域,种子点中图分类号TP391IMPROVEMENTOFAREAFILLIN
2、GSCANLINEALGORITHMRENJi-ChengLIUShen-Quan(CADLaboratory,InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080)AbstractThispaperpresentsanimprovedscanlinealgorithmforareafilling.Thenewalgorithmnotonlyeliminatestherepeatingoperationsforgettingpixelcolorsinclassicalalgorithm,butal
3、soavoidstheredundantexaminationsofthepreviouslyfilledadjacentlineandreducestherescanspanbyusingthecoherenceofthefillingorderofadjacentlines.Atlast,thepaperalsocomparestheefficiencyofseveralalgorithms.Itcanbeconcludedthatthenewalgorithmincreasesefficiencygreatly.Keywordsareafilling,scanlinealgo
4、rithm,4-adjacentconnection,seedpoint1引言区域填充是指将区域内的一点(常称种子点)赋予给定颜色,然后将这种颜色扩展到整个区域内的过程.它是光栅计算机图形学中的一个基本操作,在交互式图形设计、动画、计算机辅助设计等领域有着广泛的应用,区域填充算法的效率是计算机图形学中的一个关键问题.在光栅图形学中,区域指的是已经表示成点阵形式的象素的集合.区域填充算法要求区域具备一定的连通性:4连通或8连通.由于区域填充扫描线算法是适用于4连通区域的,在本文以下的讨论中,所有区域均约定为4连通区域.1997-01-31收稿,1997-05-26收到修改稿.本文得到
5、国家863高技术基金、中科院计算所所长基金及科学与工程计算国家重点实验室的资助.任继成,1971年10月生,博士研究生,主要研究方向为计算机图形学、科学计算可视化等.刘慎权,研究员,博士生导师,主要研究方向为计算机图形学、科学计算可视化、计算机动画等.482计算机辅助设计与图形学学报1998年[1,2]区域填充的递归算法是一种简单、直观的算法,它具有程序简单、表达清楚的优点,但由于多层递归,系统堆栈反复进出,就不可避免地造成费时、费内存的缺点.区域填[1,2]充扫描线算法则很好地利用了区域在扫描线上的连贯性和相邻扫描线之间的连贯性,克服了递归算法的缺点,成为目前应用广泛的区域填充算
6、法.但经典的区域填充扫描线算法仍存在着缺陷,首先经典算法中存在大量的象素点颜色判读的重复操作,再者经典算法中并没有很好地利用相邻扫描线填充次序上的连贯性,存在着不必要的回溯操作.本文在分析经典算法缺陷的基础上,给出了改进的区域填充扫描线算法.新算法修改了原算法中的堆栈结构,消除了经典算法中象素点颜色判读的重复操作,而且消除了不必要的回溯,并减少了回溯扫描区间.最后本文给出了新的改进算法与经典算法及其它改进算法之间的效率比较,通过比较可以看出本文的改进算法较大幅度地提高了算法的效率,其效率平均为经典算法效率的2.95倍.2经典算法缺陷分析经典区域填充扫描线算法的基本思想是:首先利用区
7、域在扫描线上的连贯性,填充当前扫描线上的一个区段,然后利用相邻扫描线上区段的连贯性,在上下两条相邻扫描线上寻找新的区段,并以种子点堆栈的形式保存这些区段.反复处理堆栈内的区段,直到保存的所有区段都处理完为止.这一过程可以分为如下5个步骤进行:步骤1(初始化)将算法设置的堆栈置为空,将给定的种子点(x,y)压入堆栈.步骤2(出栈)如果堆栈为空,算法结束;否则取栈顶元素(x,y)作为种子点.步骤3(区段填充)从种子点(x,y)开始沿纵坐标y的当前扫描线向左右两个方向逐个象
