基于GPU的加权Voronoi图计算  

GPU-based Weighted Voronoi Diagram Computing

作　　者：徐振华[1] 孔德慧[1] 肖小芳[1] 

机构地区：[1]北京工业大学计算机学院多媒体与智能软件技术北京市重点实验室,北京100124

出　　处：《系统仿真学报》2008年第S1期29-32,共4页Journal of System Simulation

基　　金：北京市自然科学基金(4061001);国家科技攻关项目(2005BA904B09);北京市教育委员会科技发展计划面上项目(KM200710005017;KM200710005023);北京市属市管高等学校人才强教计划资助项目

摘　　要：Voronoi图描述了一种对空间按照欧式距离进行的划分,是关于空间邻近关系的一种基础数据结构,在图像处理、城市规划以及地理信息系统等应用中有着重要的地位。顶点加权Voronoi图是Voronoi图的一种扩展,有着更为广泛的应用,但由于其实现的复杂性,相关算法一直比较少。为此,提出了一种基于GPU的加速算法。该算法利用GPU的高效计算特性,能够实时地生成离散的加权Voronoi图。与现有的算法相比,该方法易于实现,同时实验显示算法具有更好的计算性能。The Voronoi diagram is a way of partitioning the space according to the Euclidean metric.It is a basic data structure based on the adjacent relation of space,which is valuable in a number of applications including image processing, city layout and GIS.Vertex weighted Voronoi diagram is a useful generalization of Voronoi diagram.However,few related algorithms have been raised because of the complexity of realization.So,a novel GPU-based algorithm is presented to generate the discrete Voronoi diagram in real time.The experiment result shows that this method is easier to implement and faster than other methods.

关 键 词：欧式距离 VORONOI图 GPU 顶点加权 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]