一种构建任意发生元Voronoi图的实用算法  

A Practical Algorithm for Constructing Voronoi Diagrams of General Figures

作　　者：张辉[1] 胡玮[1] 蒲英霞[1] 王结臣[1] 

机构地区：[1]南京大学地理信息科学系,江苏南京210093

出　　处：《地理与地理信息科学》2011年第4期41-44,F0003,共5页Geography and Geo-Information Science

基　　金：国家基础科学人才培养基金能力提高项目(J0830518);江苏高校优势学科建设工程资助项目

摘　　要：针对GIS中线状、面状等复杂形态地理要素,提出一种构建任意发生元Voronoi图的实用算法。主要步骤包括:将复杂发生元离散为点集;对点集采用扫描线算法构建Voronoi图,构建过程中对所生成的Voronoi多边形以其发生点所在要素的序号赋属性值;根据拟定的规则进行Voronoi多边形的合并,得到面向复杂发生元的广义Voronoi多边形,每个复杂发生元有且仅有一个Voronoi多边形与之对应。论述了算法实现的关键过程,并结合实例验证了该方法的可行性,算法的执行效率相对较高。Considering the complexity of geographical elements in GIS,a practical algorithm for constructing Voronoi diagrams of general figures is put forward in this paper.Firstly,the general figures were scattered into point-set by using the interpolation method.Secondly,Voronoi diagrams of the point-set were constructed with sweep-line algorithm.In order to distinguish the different types of the Voronoi edges,the existing data structure of sweep-line algorithm was amended.Lastly,Voronoi polygons were merged according to the proposed rules if they belonged to the same figure.In addition,how to deal with the complex figures in this algorithm was also discussed.Case study indicated that the proposed method has a general advantage in the time and computational precision.

关 键 词：VORONOI图 算法 地理信息系统 

分 类 号：P208[天文地球—地图制图学与地理信息工程]