摘要
提出一种基于结点空间逼近、精确提取以及面向拓扑关系生成的2维平面点集的构建方法。主要给出了搜索矩形域及其剖分概念、Voronoi图的基本性质、矩形域与Voronoi图结点关系的定理及其证明、基于链队的矩形域剖分和结点逼近机制及结点提取策略、基于条带有序表的最近邻近发生元快速检索算法、矢量Voronoi图的拓扑关系建立算法等。经过算法分析和程序试验验证本文算法的时间复杂度为O(nlog2n),本方法可以扩展到平面任意发生元Voronoi图的构建,具有简洁、高精度、鲁棒性、高效、适合于海量数据等特点,并且具有较好的实用价值和应用前景。
A topology-oriented algorithm for constructing Voronoi diagram of point set in the two-dimensional Euclidean space based on approximating and extracting Voronoi vertices are proposed in this paper. The concepts of searching rectangle area and its dissection, the basic properties of Voronoi diagram, the theorems involved in the relation of rectangle and Voronoi vertices, the mechanism of dissecting rectangle and approximating vertices based on chained queue, the strategy of extracting the vertices, the algorithm of searching the closest generator based on ordered table of strip, and the method of constructing topology relation are given. The algorithm analysis and computational experiments verifiesthat the algorithm achieves time complexity of 0 （ n log2 n）, high precision, robustness and flexibility for mass data, the algorithm can be expanded to construct the Voronoi diagram of planar arbitrary generators and also has practical value and application prospect.
出处
《测绘学报》
EI
CSCD
北大核心
2007年第4期436-442,共7页
Acta Geodaetica et Cartographica Sinica
基金
国家自然科学基金项目(40401046)
关键词
VORONOI图
结点提取
四叉剖分
拓扑关系
搜索矩形域
Voronoi diagram
extracting vertices
quartering dissection
searching rectangle
topology relation
