基于结点逼近提取的平面点集Voronoi图构建算法

提出一种基于结点空间逼近、精确提取以及面向拓扑关系生成的2维平面点集的构建方法。主要给出了搜索矩形域及其剖分概念、Voronoi图的基本性质、矩形域与Voronoi图结点关系的定理及其证明、基于链队的矩形域剖分和结点逼近机制及结点提取策略、基于条带有序表的最近邻近发生元快速检索算法、矢量Voronoi图的拓扑关系建立算法等。经过算法分析和程序试验验证本文算法的时间复杂度为0（n log2 n），本方法可以扩展到平面任意发生元Voronoi图的构建，具有简洁、高精度、鲁棒性、高效、适合于海量数据等特点，并且具有较好的实用价值和应用前景。

Algorithm for Constructing Voronoi Diagram of Planar Points Based on Approximating and Extracting Vertices

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 O(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.