测绘学报
測繪學報
측회학보
ACTA GEODAETICA ET CARTOGRAPHICA SINICA
2015年
3期
338-345
,共8页
范俊甫%孔维华%马廷%周成虎%季民%周玉科
範俊甫%孔維華%馬廷%週成虎%季民%週玉科
범준보%공유화%마정%주성호%계민%주옥과
栅格化%多边形裁剪%点面包含%环绕追踪%面积误差
柵格化%多邊形裁剪%點麵包含%環繞追蹤%麵積誤差
책격화%다변형재전%점면포함%배요추종%면적오차
rasterization%polygon clipping%point in polygon%winding and tracing%area error
传统的基于矢量计算的多边形裁剪算法的时间复杂度介于O(Nlog N )~ O(N 2)之间,且计算过程与特定的复杂数据结构耦合紧密,难以进行底层优化和细粒度并行化。在满足一定误差要求的前提下,采用栅格化处理思想可以实现多边形快速裁剪。本文在已有多边形裁剪算法特征的基础上,提出了一种基于栅格化处理思想的多边形裁剪算法———R a PC算法,并对其误差进行了分析和讨论。试验结果显示,RaPC算法的计算效率随网格单元增大呈幂函数规律降低;当网格大小恒定时,RaPC算法效率随多边形顶点数量呈线性增长,计算时间复杂度为O(N);在处理小数据集时Vatti算法表现出了较高效率,但是在处理包含大量顶点的多边形叠加时,RaPC算法更为高效;RaPC算法的面积误差与网格大小直接相关,提高网格空间分辨率可以有效地降低面积误差。R a PC算法在处理包含大量顶点的多边形叠加分析时比V atti算法更为高效。
傳統的基于矢量計算的多邊形裁剪算法的時間複雜度介于O(Nlog N )~ O(N 2)之間,且計算過程與特定的複雜數據結構耦閤緊密,難以進行底層優化和細粒度併行化。在滿足一定誤差要求的前提下,採用柵格化處理思想可以實現多邊形快速裁剪。本文在已有多邊形裁剪算法特徵的基礎上,提齣瞭一種基于柵格化處理思想的多邊形裁剪算法———R a PC算法,併對其誤差進行瞭分析和討論。試驗結果顯示,RaPC算法的計算效率隨網格單元增大呈冪函數規律降低;噹網格大小恆定時,RaPC算法效率隨多邊形頂點數量呈線性增長,計算時間複雜度為O(N);在處理小數據集時Vatti算法錶現齣瞭較高效率,但是在處理包含大量頂點的多邊形疊加時,RaPC算法更為高效;RaPC算法的麵積誤差與網格大小直接相關,提高網格空間分辨率可以有效地降低麵積誤差。R a PC算法在處理包含大量頂點的多邊形疊加分析時比V atti算法更為高效。
전통적기우시량계산적다변형재전산법적시간복잡도개우O(Nlog N )~ O(N 2)지간,차계산과정여특정적복잡수거결구우합긴밀,난이진행저층우화화세립도병행화。재만족일정오차요구적전제하,채용책격화처리사상가이실현다변형쾌속재전。본문재이유다변형재전산법특정적기출상,제출료일충기우책격화처리사상적다변형재전산법———R a PC산법,병대기오차진행료분석화토론。시험결과현시,RaPC산법적계산효솔수망격단원증대정멱함수규률강저;당망격대소항정시,RaPC산법효솔수다변형정점수량정선성증장,계산시간복잡도위O(N);재처리소수거집시Vatti산법표현출료교고효솔,단시재처리포함대량정점적다변형첩가시,RaPC산법경위고효;RaPC산법적면적오차여망격대소직접상관,제고망격공간분변솔가이유효지강저면적오차。R a PC산법재처리포함대량정점적다변형첩가분석시비V atti산법경위고효。
Computational efficiencies of traditional vector computing‐based polygon clipping algorithms will decrease rapidly when handling polygons contain large amount of vertices .The computing flows of traditional polygon clipping algorithms are tightly coupled with special data structures ,which difficult to be optimized in the underlying of them .Under the premise of meeting a certain degree of area errors ,the polygonclippingproblemcanbesolvedbyintroducingtheideaofrasterizationprocessing.Inthisresearch, we proposed a new rasterization processing‐based polygon clipping algorithm:the RaPC algorithm ,on the basis of analyzing the characteristics of existing algorithms .The area errors of results of the new algorithm are also analyzed and discussed .Experimental results show that the efficiencies of the RaPC algorithm can be enhanced significantly when using l arge grid cells ,and it shows a linear trend growth with the increase of amount of polygon vertices .Compared with the Vatti algorithm ,the RaPC algorithm represents more efficiencies on dealing clipping issues between polygons with large amount of vertices ,the former shows lower time costs when handling polygons with less vertices .The area error of computing results of the RaPC algorithmiscloselyrelatedwiththegridsize,anderrorscanbereducedusingsmallergridsizes.Therefore the RaPC algorithm showed higher efficiencies on processing polygons with large amount of vertices than the Vatti algorithm and presented practical values to some degree .