基于Voronoi图的空间区域划分算法

Study on region of space partition algorithm based on Voronoi diagrams

考虑到空间划分的复杂性,将有限维分布不均匀的空间划分为均匀的空间是一个很复杂的过程.针对Voronoi图诸多性质中的最近邻特性,提出利用Voronoi图划分空间区域,定义了一个单位覆盖空间,运用点替换规则和迭代法划分空间,并将分块区域内的点集标记颜色,位于同一分块内的点有相同的特性,从而把平面或维空间划分为有周期性或准周期性的分块.利用Voronoi图划分空间的算法可应用到计算机制图,把凹凸不平的物体表面细分,还可应用在三维空间来构造分子,在计算化学中得有广泛的应用.

Considering the complexity of the space division,limited dimension of non-uniform distribution of space into uniform space is a very complicated process.According to nearest neighbor of the properties of various Voronoi diagram,used the Voronoi diagram partition space area,this paper defined an unit,used some covered space to replace rules and iterative method,and would be partitioned into space inside area of point set in the same block mark color,thus the cells of a fractal partition have self-similarity property and could be used as a set of tiles that can tile space periodically or quasi-periodically with non-uniform tiling density.Used the space Voronoi graph partition algorithm could also be applied to computer graphics and the uneven surface subdivision,also could be used in 3D space constructed in computational chemistry in molecular,have extensive application.