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

Study on region of space partition algorithm based on Voronoi diagrams

作　　者：董雪[1] 刘润涛[1] 

机构地区：[1]哈尔滨理工大学应用科学学院,哈尔滨150080

出　　处：《哈尔滨商业大学学报（自然科学版）》2011年第6期867-869,880,共4页Journal of Harbin University of Commerce：Natural Sciences Edition

基　　金：黑龙江省自然科学基金项目(F200601);黑龙江省教育厅项目(11511027);哈尔滨理工大学教学研究课题(No.p20100054)

摘　　要：考虑到空间划分的复杂性,将有限维分布不均匀的空间划分为均匀的空间是一个很复杂的过程.针对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.

关 键 词：区域划分 VORONOI划分 迭代法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]