小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2011年
10期
2068-2073
,共6页
局部拓扑%裁剪%线段求交
跼部拓撲%裁剪%線段求交
국부탁복%재전%선단구교
针对大规模等值线图裁剪算法面临的两个主要问题,如何减少线段求交次数和判别保留部分的起止点,提出一种针对大规模等值线图的任意多边形裁剪算法.该算法首先使用等网格分割方法,在等值线线段与裁剪多边形边之间建立网格索引,减少线段求交次数；同时,在网格数据结构基础上,采用局部射线法,很好地解决了判断交点在裁剪多边形内外时间复杂度过大的问题,使得算法可以快速判断出需要保留(剔除)的等值线部分.本文算法的优点是能够在求出交点的基础上快速获得需要保留(剔除)部分的起止点；同时,算法中裁剪多边形可以是包含任意多个洞的任意简单多边形,克服传统算法中对裁剪多边形的特定约束条件.本文算法易于实现且高效.
針對大規模等值線圖裁剪算法麵臨的兩箇主要問題,如何減少線段求交次數和判彆保留部分的起止點,提齣一種針對大規模等值線圖的任意多邊形裁剪算法.該算法首先使用等網格分割方法,在等值線線段與裁剪多邊形邊之間建立網格索引,減少線段求交次數；同時,在網格數據結構基礎上,採用跼部射線法,很好地解決瞭判斷交點在裁剪多邊形內外時間複雜度過大的問題,使得算法可以快速判斷齣需要保留(剔除)的等值線部分.本文算法的優點是能夠在求齣交點的基礎上快速穫得需要保留(剔除)部分的起止點；同時,算法中裁剪多邊形可以是包含任意多箇洞的任意簡單多邊形,剋服傳統算法中對裁剪多邊形的特定約束條件.本文算法易于實現且高效.
침대대규모등치선도재전산법면림적량개주요문제,여하감소선단구교차수화판별보류부분적기지점,제출일충침대대규모등치선도적임의다변형재전산법.해산법수선사용등망격분할방법,재등치선선단여재전다변형변지간건립망격색인,감소선단구교차수；동시,재망격수거결구기출상,채용국부사선법,흔호지해결료판단교점재재전다변형내외시간복잡도과대적문제,사득산법가이쾌속판단출수요보류(척제)적등치선부분.본문산법적우점시능구재구출교점적기출상쾌속획득수요보류(척제)부분적기지점；동시,산법중재전다변형가이시포함임의다개동적임의간단다변형,극복전통산법중대재전다변형적특정약속조건.본문산법역우실현차고효.
