中国图象图形学报A
中國圖象圖形學報A
중국도상도형학보A
JOURNAL OF IMAGE AND GRAPHICS
2010年
6期
978-984
,共7页
孟雷%张俊伟%王筱婷%杨承磊
孟雷%張俊偉%王篠婷%楊承磊
맹뢰%장준위%왕소정%양승뢰
Voronoi图%Delaunay三角化%增量法%扫描线法%右凸链
Voronoi圖%Delaunay三角化%增量法%掃描線法%右凸鏈
Voronoi도%Delaunay삼각화%증량법%소묘선법%우철련
Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用.增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长.扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlog n),但需要构造比较复杂的数据结构.为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右凸链的结构来定位新插入的点,实现了Voronoi图的逐步构造.和扫描线算法类似,其时间复杂度为O(nlog n),但算法更简洁,且便于理解和编程实现.
Voronoi圖是計算幾何中的一種重要幾何結構,也是計算幾何的重要研究內容之一,如今已經在圖形學、地理信息繫統、機械工程、機器人等領域得到廣汎應用.增量法是最常用的構造Voronoi圖的方法,但一般實現方法中點的定位時間比較長.掃描線算法可以視為一種特殊的增量法,時間複雜度為O(nlog n),但需要構造比較複雜的數據結構.為瞭更有效地構建Voronoi圖,提齣瞭一種改進的Voronoi圖增量構造算法,該算法是通過對已有的生成Voronoi圖的增量法進行分析,併結閤它們的優點,採用掃描線的方式,通過右凸鏈的結構來定位新插入的點,實現瞭Voronoi圖的逐步構造.和掃描線算法類似,其時間複雜度為O(nlog n),但算法更簡潔,且便于理解和編程實現.
Voronoi도시계산궤하중적일충중요궤하결구,야시계산궤하적중요연구내용지일,여금이경재도형학、지리신식계통、궤계공정、궤기인등영역득도엄범응용.증량법시최상용적구조Voronoi도적방법,단일반실현방법중점적정위시간비교장.소묘선산법가이시위일충특수적증량법,시간복잡도위O(nlog n),단수요구조비교복잡적수거결구.위료경유효지구건Voronoi도,제출료일충개진적Voronoi도증량구조산법,해산법시통과대이유적생성Voronoi도적증량법진행분석,병결합타문적우점,채용소묘선적방식,통과우철련적결구래정위신삽입적점,실현료Voronoi도적축보구조.화소묘선산법유사,기시간복잡도위O(nlog n),단산법경간길,차편우리해화편정실현.
