摘要
提出了基于“O QTM”(OctahedralQuaternaryTriangularMesh)剖分的球面Voronoi图的格网生成算法 :首先介绍了球面的QTM格网剖分和编码方法 ,并根据地址码进行邻近球面三角形的搜索 ;然后 ,参照数学形态学原理 ,重新定义了球面三角网的膨胀操作和膨胀算子 ,利用球面实体的递归膨胀来生成球面Voronoi图。应用VC++语言在OpenGL 3维平台上开发了相应的实验程序 ,实验结果表明 :利用此算法可生成球面上任意实体的Voronoi图 ,且生成点、弧和曲面Voronoi图的时间复杂度是一样的 ;而其误差受球面距离的影响较小 ,主要与球面实体的位置有关。最后给出了本文研究的结论及进一步的工作。
In order to store, pick up and analyse the spatial data efficiently in global scale, the digital expression of the Earth data in data model must be global, continuous and conjugate, i.e., the spherical dynamic data model is needed. It has been realized that Voronoi data structure is the only possible solution (which is currently available) to dynamic GIS. But the complex of the Voronoi algorithm of line sets and area sets in vector limits its application in GIS. There are few Voronoi algorithms in spherical data except spherical points sets, and can not satisfy the requirement of dynamic operation of spherical data in arc sets and curve face sets. To overcome this serious deficiency, this paper presents an algorithm for generating of spherical Voronoi diagram based on O-QTM (Octahedral Quaternary Triangle Mesh). Firstly, the methods of spherical surface triangular partition and triangular coding are reviewed. With the codes of triangle, the direct and non-direct neighbor triangle can be searched and the dilation operator and dilation-structuring element of spherical triangular are redefined according to the principle of mathematical morphology. So the spherical Voronoi diagram is generated by recursive dilation of spherical objects expressed by codes of triangles. We developed the experimental system using VC ++ in OpenGL platform and analysed the complex degree of algorithm and features of errors. The results demonstrate: Voronoi diagram for any spherical objects based on QTM can be generated easily, and the complex degree of algorithm with point sets, arc sets and curved surface sets are equal, and proportional to levels of the spherical surface partition; The error of dilations is related little to spherical distance, not as the raster dilation in planar, and is mainly related to the locations of the objects. In the end, the conclusions and future works are presented.
出处
《测绘学报》
EI
CSCD
北大核心
2002年第2期157-163,共7页
Acta Geodaetica et Cartographica Sinica
基金
国家自然科学基金资助项目 ( 6 98330 10 )
