三维散乱点集Voronoi图快速生成算法研究  

An Algorithm for Generating Voronoi Diagram of 3D Scattered Point-set

作　　者：孙殿柱[1] 刘健[1] 李延瑞[1] 李心成[1] 

机构地区：[1]山东理工大学机械工程学院,淄博市张店区张周路12号255091

出　　处：《武汉大学学报（信息科学版）》2010年第8期909-912,共4页Geomatics and Information Science of Wuhan University

基　　金：国家863计划资助项目(2006AA04Z105)

摘　　要：提出了一种高效的三维散乱点集Voronoi图的生成算法。该算法采用点-面-体数据结构存储Voronoi单元,初始化首点Voronoi单元,通过单元分裂与单元重组快速生成新增点的Voronoi单元,并完成其相邻单元的维护。实验证明,该算法可快速准确地生成任意三维散乱点集的Voronoi图。基于该算法可有效地解决逆向工程中三维散乱数据点拓扑近邻的快速准确查询问题,对产品模型的曲面重建具有重要意义。An efficient algorithm for generating Voronoi diagram of 3D scattered point-set is proposed,which takes the data structure named ＂point-face-polyhedron＂ to store Voronoi cell,initializes the Voronoi cell of the first point,and the Voronoi cell of the new inserted point was generated after whose adjacent cells were changed accordingly through fission and reconstitution of cells.The experimental results show that this method can generate Voronoi diagram of 3D scattered point-set veraciously and efficiently.The topological neighbors inquiring for 3D scattered point-set can be realized efficiently based on this algorithm.

关 键 词：三维散乱点集 Voronoi单元 单元分裂 单元重组 

分 类 号：P208[天文地球—地图制图学与地理信息工程]