计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2012年
11期
96-103
,共8页
李楠%吴信才%马金金%王中
李楠%吳信纔%馬金金%王中
리남%오신재%마금금%왕중
R-树%网格索引%线裁剪%局部射线法
R-樹%網格索引%線裁剪%跼部射線法
R-수%망격색인%선재전%국부사선법
针对大规模矢量线与大量裁剪窗口同时出现的线裁剪算法存在的三个主要问题,减少线段求交次数、简化交点出入属性计算以及无交点矢量线的取舍,本文提出了一种基于双空间索引的大规模线图任意多边形裁剪算法.算法根据裁剪多边形的边分别建立R-树索引和均匀Cell索引,应用两种索引各自的优点大幅减少被裁剪线段与裁剪多边形上线段的求交次数.在此基础上,基于均匀网格索引,提出局部射线法,简化交点出入属性计算和无交点矢量线的取舍.本文在传统算法基础上提出三点改进:首先提出基于两种空间索引模型进行线段求交计算,保证算法在理论上具有较低的时间复杂度；其次,在射线法和网格索引基础上提出局部射线法,使得判断每个交点出入属性的时间复杂度为O(1)～O(√n),与参考文献中的算法相比,此方法的优点是避免判断多边形上顶点的方向；最后,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.
針對大規模矢量線與大量裁剪窗口同時齣現的線裁剪算法存在的三箇主要問題,減少線段求交次數、簡化交點齣入屬性計算以及無交點矢量線的取捨,本文提齣瞭一種基于雙空間索引的大規模線圖任意多邊形裁剪算法.算法根據裁剪多邊形的邊分彆建立R-樹索引和均勻Cell索引,應用兩種索引各自的優點大幅減少被裁剪線段與裁剪多邊形上線段的求交次數.在此基礎上,基于均勻網格索引,提齣跼部射線法,簡化交點齣入屬性計算和無交點矢量線的取捨.本文在傳統算法基礎上提齣三點改進:首先提齣基于兩種空間索引模型進行線段求交計算,保證算法在理論上具有較低的時間複雜度；其次,在射線法和網格索引基礎上提齣跼部射線法,使得判斷每箇交點齣入屬性的時間複雜度為O(1)～O(√n),與參攷文獻中的算法相比,此方法的優點是避免判斷多邊形上頂點的方嚮；最後,算法中裁剪多邊形可以是包含任意多箇洞的任意簡單多邊形,剋服傳統算法中對裁剪多邊形的特定約束條件.
침대대규모시량선여대량재전창구동시출현적선재전산법존재적삼개주요문제,감소선단구교차수、간화교점출입속성계산이급무교점시량선적취사,본문제출료일충기우쌍공간색인적대규모선도임의다변형재전산법.산법근거재전다변형적변분별건립R-수색인화균균Cell색인,응용량충색인각자적우점대폭감소피재전선단여재전다변형상선단적구교차수.재차기출상,기우균균망격색인,제출국부사선법,간화교점출입속성계산화무교점시량선적취사.본문재전통산법기출상제출삼점개진:수선제출기우량충공간색인모형진행선단구교계산,보증산법재이론상구유교저적시간복잡도；기차,재사선법화망격색인기출상제출국부사선법,사득판단매개교점출입속성적시간복잡도위O(1)～O(√n),여삼고문헌중적산법상비,차방법적우점시피면판단다변형상정점적방향；최후,산법중재전다변형가이시포함임의다개동적임의간단다변형,극복전통산법중대재전다변형적특정약속조건.
