图学学报
圖學學報
도학학보
Journal of Graphics
2012年
6期
45-49
,共5页
凹多边形%多边形裁剪%跟踪策略%网格划分%单线性链表
凹多邊形%多邊形裁剪%跟蹤策略%網格劃分%單線性鏈錶
요다변형%다변형재전%근종책략%망격화분%단선성련표
论文提出了一种高效稳定的多边形裁剪算法,算法支持带内环的平面简单多边形,同时也支持多边形的“并”和“差”等布尔运算.首先,设计了算法所需的数据结构；其次,基于直线扫描转换Bresenham算法原理提出了边网格划分的有效算法,并应用一个简单的方法避免不同网格内边的重复求交；最后,将交点分类为普通交点和顶交点,并针对这两类交点构造了不同的跟踪策略,在跟踪过程中交替、递归地应用这两个策略来确保算法处理特殊情况时的稳定性.与其它同类算法的比较表明,新算法具有更高的效率.
論文提齣瞭一種高效穩定的多邊形裁剪算法,算法支持帶內環的平麵簡單多邊形,同時也支持多邊形的“併”和“差”等佈爾運算.首先,設計瞭算法所需的數據結構；其次,基于直線掃描轉換Bresenham算法原理提齣瞭邊網格劃分的有效算法,併應用一箇簡單的方法避免不同網格內邊的重複求交；最後,將交點分類為普通交點和頂交點,併針對這兩類交點構造瞭不同的跟蹤策略,在跟蹤過程中交替、遞歸地應用這兩箇策略來確保算法處理特殊情況時的穩定性.與其它同類算法的比較錶明,新算法具有更高的效率.
논문제출료일충고효은정적다변형재전산법,산법지지대내배적평면간단다변형,동시야지지다변형적“병”화“차”등포이운산.수선,설계료산법소수적수거결구；기차,기우직선소묘전환Bresenham산법원리제출료변망격화분적유효산법,병응용일개간단적방법피면불동망격내변적중복구교；최후,장교점분류위보통교점화정교점,병침대저량류교점구조료불동적근종책략,재근종과정중교체、체귀지응용저량개책략래학보산법처리특수정황시적은정성.여기타동류산법적비교표명,신산법구유경고적효솔.
