APP下载

面向雷利法则的加权Voronoi图生成方法

2018-04-08瞿珊珊

测绘通报 2018年3期
关键词:生长方法

康 顺,瞿珊珊

(1. 中国矿业大学(北京)地球科学与测绘工程学院,北京 100083; 2. 中南大学地球科学与信息物理学院,湖南 长沙 410083)

Voronoi雏形可见于笛卡尔的《哲学原理》,文中描述了在可视宇宙中太阳系是由许多漩涡(Vortices)组成的这一理念[1]。在涡旋空间被抽取为凸域集合概念之后,这一概念在不同学科中被赋予了种种名称:生物学的中轴变换(medial axis transform);化学、物理学的维格那-塞茨原胞(Wigner-Seitz zones);晶体学的作用域(domains of action);气象学、几何学的泰森多边形(Thiessen polygons)等。最后,由数学家Dirichlet和Voronoi将这一概念正式命名为狄利克雷镶嵌(Dirichlet tessellation)或沃洛诺伊图(Voronoi diagram)[2]。作为计算几何的重要内容,Voronoi图是解决骨架线提取、凸包计算、Delaunay三角化,以及数据可视化等问题的有力工具[3]。因此,研究Voronoi图的高效生成算法具有重要的现实意义。

在一般Voronoi图与广义Voronoi图的生成方法上已有诸多学者进行了相关研究,主要分为矢量生成方式和栅格生成方式两种。基于矢量的Voronoi图生成方法主要有增量法、分治法、间接法,由于矢量数据的存储量大、存储结构比较复杂,对点线面复合目标构成的空间实体进行Voronoi计算时,多要求生长元是点或半线,对线或面要素则往往分解为点要素来构建Voronoi图,该方式破坏了图形的完整性,并增加了计算的复杂度[4-6]。由于矢量方法的局限性,基于栅格的Voronoi图生成方法得到研究与发展。栅格Voronoi图的生成方式一是依据传统距离变换的栅格Voronoi生成[7-10],在基于空间生长目标图像转变为距离图像的栅格Voronoi图生成方法中定义栅格距离是关键,已有的主要距离形式有欧氏距离、曼哈顿距离(或L1距离)、切比雪夫距离(或L∞距离)及其加权形式;……

登录APP查看全文

猜你喜欢

生长方法
碗莲生长记
生长在哪里的启示
生长
用对方法才能瘦
四大方法 教你不再“坐以待病”!
捕鱼