计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
17期
178-181
,共4页
徐胜攀%刘正军%左志权%程耀东
徐勝攀%劉正軍%左誌權%程耀東
서성반%류정군%좌지권%정요동
区域填充%活性边表%动态发现机制%自相交
區域填充%活性邊錶%動態髮現機製%自相交
구역전충%활성변표%동태발현궤제%자상교
area-filling%active-edge-table%dynamic discovery mechanism%self-intersection
为提高区域填充效率,对三种常见的区域填充算法进行了介绍和分析,并对其中优势较为明显的活性边表区域填充算法进行了进一步改进。改进算法针对原始算法的不足,充分利用多边形顶点信息,建立了活性边动态发现机制,使得算法时间效率和空间效率都得到提高;同时,为填充自相交多边形,又提出一种简单有效的基于扫描线的多边形自相交点探测方法,使得算法的适用性得到进一步增强。实验结果表明,算法的改进取得了很好的效果。
為提高區域填充效率,對三種常見的區域填充算法進行瞭介紹和分析,併對其中優勢較為明顯的活性邊錶區域填充算法進行瞭進一步改進。改進算法針對原始算法的不足,充分利用多邊形頂點信息,建立瞭活性邊動態髮現機製,使得算法時間效率和空間效率都得到提高;同時,為填充自相交多邊形,又提齣一種簡單有效的基于掃描線的多邊形自相交點探測方法,使得算法的適用性得到進一步增彊。實驗結果錶明,算法的改進取得瞭很好的效果。
위제고구역전충효솔,대삼충상견적구역전충산법진행료개소화분석,병대기중우세교위명현적활성변표구역전충산법진행료진일보개진。개진산법침대원시산법적불족,충분이용다변형정점신식,건립료활성변동태발현궤제,사득산법시간효솔화공간효솔도득도제고;동시,위전충자상교다변형,우제출일충간단유효적기우소묘선적다변형자상교점탐측방법,사득산법적괄용성득도진일보증강。실험결과표명,산법적개진취득료흔호적효과。
To improve the efficiency of area filling, the paper makes an introduction and analysis for the three common area filling algorithms and further improves the active-edge-table algorithm which has more obvious advantages compared with the others. For the deficiency of traditional algorithm, the improved algorithm makes full use of vertex information and establishes the dynamic discovery mechanism of active edges, making the time efficiency and space efficiency both improved;meanwhile, in order to fill the self-intersected polygons, an easy and effective method to detect self-intersected vertices based on scan line is proposed, making the adaptability of the algorithm enhanced. Experimental results demon-strate that the improved algorithm achieves very good results.