一种强鲁棒性自适应活性边表算法  

AN ACTIVE-EDGE-TABLE FILLING ALGORITHM WITH ADAPTABILITY AND ROBUSTNESS

作　　者：师硕[1] 姚陈堃 于洋[1] 

机构地区：[1]河北工业大学计算机科学与软件学院,天津300401

出　　处：《计算机应用与软件》2016年第7期213-216,共4页Computer Applications and Software

基　　金：天津市科技计划项目(14RCGFGX00846);河北省教育厅高等学校科学研究计划项目(Z2013078)

摘　　要：为提升多边形的填充效率,在分析和比较常见填充算法后,以活性边表算法为基础,深入挖掘不同扫描方向上的求交次数及多边形自交特性,提出一种强鲁棒性自适应活性边表算法。新算法引入横度和纵度的概念表示横纵扫描方向上的求交次数,并以此为标准自适应选择扫描方向。此外,通过对活性边表中相邻交点的横坐标进行检测和纠正,正确而高效地填充了自交多边形。经实验验证,新算法灵活的自适应性和高效的自交纠正方法,大大提高了时间效率和鲁棒性。To improve the efficiency of polygon filling,after analysing and comparing several common filling algorithms,the paper puts forward an active-edge-table filling algorithm with adaptability and robustness,which is based on active-edge-table algorithm,by thoroughly mining the number of crossover requests in different scanning directions and the self-intersection character of polygon. The new algorithm introduces the concept of horizontal extent and vertical extent to represent the number of crossover requests in horizontal and vertical directions of scanning,and takes them as the standard to adaptively choose the right scanning direction. In addition,by checking and correcting the coordinates of the adjoining crossover points in active-edge-table,this algorithm fills the self-intersected polygon correctly and efficiently. It is verified by experiment that the new algorithm greatly improves the time efficiency and robustness owing to its flexible adaptability and efficient self-intersection correcting way.

关 键 词：多边形填充 自适应扫描 活性边表算法 自相交 鲁棒性 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]