沃罗诺伊图(Voronoi):迷人的世界【1/2】

2023-10-15 06:20

本文主要是介绍沃罗诺伊图(Voronoi):迷人的世界【1/2】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、说明

Voronoi图(也称为狄利克雷镶嵌泰森多边形)在自然界中无处不在。你已经遇到过他们数千次了,但也许没有这样称呼它。Voronoi图很简单,但它们具有令人难以置信的特性,在制图,生物学,计算机科学,统计学,考古学,一直到建筑和艺术等领域都有应用。

二、什么是沃罗诺伊图?

        假设您有 n 个点分散在一个平面上,这些点的 Voronoi 图将平面细分为正好 n 个单元格,这些单元格包围了最接近每个点的平面部分。这将产生完全覆盖平面的镶嵌。作为说明,在图 1 中,我绘制了 100 个随机点及其相应的 Voronoi 图。如您所见,每个点都包含在一个像元中,该像元的边界在两个或多个点之间正好等距。换句话说,单元格中包含的所有区域都最靠近单元格中的点,而不是任何其他点。

图1:沃罗诺伊图
 

三、沃罗诺伊模式无处不在

3.1 自然界中的沃罗诺伊模式

        由Voronoi图创建的模式在自然界中是常见的。在图 2 中,我制作了一些自然发生的类似 Voronoi 的图案的小拼贴画。从洋葱皮中的微观细胞,到菠萝蜜的壳和长颈鹿的皮毛。这些模式无处不在!

        它们无处不在的第一个原因是它们形成了有效的形状。正如我们前面提到的,Voronoi 图完全细分了平面:因此,所有空间都被使用。如果您想在有限的空间内尽可能多地挤压,例如在肌肉纤维或蜂箱中,这将非常方便。其次,Voronoi图是一种自发模式,每当某物从不同的点以均匀的增长率增长时(见图3)。例如,这就解释了为什么长颈鹿表现出这种模式。长颈鹿胚胎具有分散分布的黑色素分泌细胞,这是长颈鹿斑点深色色素沉着的原因。在妊娠过程中,这些细胞释放黑色素 - 因此斑点向外辐射。有兴趣的读者可以参考这篇论文,其中作者使用Voronoi图对动物外套上的斑点进行计算机渲染建模。

图2:Voronoi模式在自然界中无处不在。
(从左上到右下:肌肉的横截面,长颈鹿的毛纹,蜻蜓的翅膀,大蒜鳞茎,玉米,挂在树上的菠萝蜜。
来源:维基百科,Nirav Shah,Karolina Grabowska,StarGlade,Mali Maeder,Abi Jacob

图 3:从分散点
向外不断增长获得 Voronoi 图 来源:维基百科

3.2 建筑和艺术中的沃罗诺伊模式

        也许是因为它们自发的“自然”外观,或者仅仅是因为它们令人着迷的随机性,Voronoi模式被有意地在人造结构中实现。一个建筑例子是2008年北京奥运会期间为容纳水上运动而建造的“水立方”。它的天花板和立面上有Voronoi图(图4)。选择Voronoi图是因为它们回忆起气泡1。这个类比在晚上非常明显,当整个立面被蓝色照亮并活跃起来时。

图4:北京
 

        但中国人对沃罗诺伊图案的欣赏肯定比这座建筑更古老。宋代的关、葛皿有独特的噼啪作响的釉。陶瓷在冷却过程中很容易破裂,但是关和葛瓷的裂纹是不同的——它们是故意的。它们因其美学品质而受到追捧。由于表面的Voronoi图案,每件作品都是独一无二的。迄今为止,这是最常被模仿的瓷器风格之一(图5)。

图5:关和葛炳
 

        Voronoi图在图形艺术中也很常见,用于创建“抽象”图案。我认为它们可以制作出色的背景图像。例如,我通过生成随机点并构建Voronoi图来创建这篇文章的缩略图。然后,我根据每个单元格的点与框中随机选择的点的距离对每个单元格进行着色(图 6)。无穷无尽的“抽象”背景图像可以通过这种方式生成。

图6:彩色沃罗诺伊图
 

四、数学定义和一些有趣的属性

        到目前为止,我们已经提出了一个简单的二维Voronoi图。然而,相同类型的结构可以推广到 n 维空间。假设 P={p1,p2,...,pm} 是我们 n 维空间中的一组 m 个点。然后,可以将空间划分为 m Voronoi 单元 Vi,其中包含 Rn 中比任何其他点更接近 pi 的所有点。

        其中函数 d(x,y) 给出其两个参数之间的距离 (a)。通常,使用欧几里得距离(l2 距离):

        但是,可以使用其他距离函数设计Voronoi图。例如,图 7 显示了使用曼哈顿或城市街区距离(l1 距离)获得的 Voronoi 图。Manahattan 距离是两点之间的距离,如果您必须遵循常规网格(例如曼哈顿的城市街区)。结果是一个更“四四方方”的Voronoi图。

图7:欧几里得距离
 

图 8:同一组点
使用欧几里得(左)和曼哈顿(右)距离的 Voronoi 图比较 来源:维基百科

        欧几里得距离是Voronoi图科学应用中最常见的距离度量。它还具有生成面Voronoi细胞的优点。也就是说,如果您在单元格内取任意两个点,则连接这两个点的线将完全位于单元格内。

        最后,还应该注意的是,Voronoi 图与 k 最近邻算法 (k-NN) 紧密相连,该算法是分类、回归和聚类问题中非常流行的算法。该算法使用训练数据集中最接近的 k 个示例进行值预测。由于 Voronoi 图在包含每个种子最近的点的多边形中划分空间,因此 Voronoi 像元的边与简单的 1-最近邻问题的决策边界完全对应。

五、德劳奈三角测量

        如果您从 Voronoi 图中获取每个点并将其与其相邻单元格中的点链接,您将获得一个名为 Delaunay 三角测量的图形。用数学术语来说,德劳奈三角测量是沃罗诺伊图的对偶图。在下图中,从一组点绘制了Voronoi图(黑色)和Delaunay三角测量(灰色)。

图9:带有德劳奈三角测量的Voronoi图
来源:作者图片

        德劳奈三角测量与沃罗诺伊图一样令人惊叹。顾名思义,它会产生一组连接我们点的三角形。这些三角形是这样的,如果要在这些三角形的顶点上画一个圆,圆内就不会有其他点(见图 10)。此外,德劳奈三角测量还具有最大化三角三角形中最小角度的特性。因此,德劳奈三角测量倾向于避免具有锐角的三角形。

图 10:Delaunay 三角形的构造使得没有点落在环绕每个三角形的圆内
来源:维基百科

        这些属性使其在从一组点对表面和对象进行建模时非常有用。例如,Delaunay 三角测量用于为有限元方法生成网格,为计算机动画构建 3D 模型以及在 GIS 分析中对地形进行建模。

六、劳埃德松弛算法

        Llyod算法是一种与Voronoi图相关的有用算法。该算法包括在构建Voronoi图和查找每个单元的质心(即质心)之间反复交替(见图11)。在每次迭代中,该算法将点分开并产生更均匀的Voronoi单元。

图 11:劳埃德松弛算法
中的步骤 来源:作者图片

        经过几次迭代后,单元格将已经具有“更圆”的方面,并且点将更均匀地分布。下图对此进行了说明,其中我绘制了一组随机点的劳埃德算法的前 30 次迭代。对于每个点,我还记录它们的起始位置(灰色空心圆圈),以更好地跟踪每个单元格的运动。对于大量迭代,该图倾向于收敛到稳定的Voronoi图,其中每个种子也是细胞的质心 - 也称为质心Voronoi图。有趣的是,在2D中,Voronoi单元往往会变成六边形,因为它们提供了在平面中包装形状的最有效方式。正如任何建造蜂巢的蜜蜂都可以证明的那样,六边形细胞具有两大优势:1)它们确保细胞之间没有空白空间(即镶嵌平面),以及2)六边形提供细胞表面和周长之间的最高比例。这个所谓的蜂窝猜想,花了数学家两千年的时间才证明。

图 12:劳埃德算法
的 30 次迭代 来源:作者图片

        在数据科学中,劳埃德算法是k均值聚类的基础,k-means聚类是最流行的聚类算法之一。k 均值聚类通常是通过在空间中获取 k 个随机“质心”来启动的。然后,通过交替将数据点分组为 k 个簇:1) 将数据点分配给最接近的“质心”(这相当于为质心构建 Voronoi 图并检查哪个点在单元内)和 2) 通过计算每个单元内点的平均值来更新质心(参见图 14)。

图 14:k 均值聚类
 

        除了数据科学,劳埃德的算法还用于各种应用。例如,它在量化和有损数据压缩算法(例如劳埃德-马克斯算法)中很常见。每当人们想要间隔良好的随机点时,它也非常有用。例如,它可用于从 Delaunay 三角测量生成平滑网格,用于抖动图像,或作为视频游戏中程序地图生成的基础。

七、如何构建沃罗诺伊图?

        人们可以通过逐个构建每个单元格来构建Voronoi图。如果扩展连接每个点组合的段的平分线,则可以获得Voronoi单元的轮廓(图15)。但是,这种技术效率很低。考虑到有0.5*(n-1)n个点的组合,这种算法的复杂性会随着点数的增加呈二次增加。

图15:Voronoi细胞
的构建 来源:作者图片

        已经提出了更有效的替代办法。例如,扫描线算法通过使用二叉搜索树和优先级队列操作按顺序逐步构建 Voronoi 单元(图 16)。可以在此处找到此算法的良好描述。构建Voronoi图的另一种方法是首先构建Delaunay三角测量。获得三角测量后,延伸三角形边的平分线通向Voronoi图。无需考虑每对点即可获得德劳内三角测量。例如,一种有效的技术是在更高维度上投影抛物面上的点。将凸包重新投影回原始空间,使德劳内三角测量。

图 16:扫描线算法
来源:维基百科

        有关计算Voronoi图的不同算法及其复杂性的讨论,请参见此处,此处和此处。不断提出新的算法来提高不同情况下的计算效率(例如Yan et al. 2011, Qin et al. 2017)。 还有一些技术需要恒定时间来生成近似的Voronoi图(例如跳跃洪水算法)。

八、其他材料的链接

  • 本文讲述了约翰·斯诺(John Snow)如何使用Voronoi图来显示1854年伦敦爆发期间水泵与霍乱传播之间的联系的故事。
  • Amit Patel有一个关于游戏开发的非凡博客。我强烈推荐他关于使用 Voronoi 图生成程序地图的文章。
  • David Austin的这篇文章很好地解释了用于计算Voronoi图的扫描线算法。
  • 这张由杰森·戴维斯(Jason Davies)绘制的精美地图是基于世界各地机场位置的Voronoi图。
  • 空间镶嵌:Voronoi图的概念和应用是一本关于Voronoi图的圣经。如果您对Voronoi图有任何疑问,您一定会在这里找到答案。
  • Vincent Legat 的这些幻灯片包括一些针对不同构造算法的精美图纸。
  • Voronoi图通常用于对森林中的树木进行建模(例如Abellanas等人,2016年,Bohler等人,2018年)。
  • Voronoi图也可用于确定机器人的路径。检查这些文章:文章 1、文章 2。
  • Voronoi图有数千种应用程序。从在森林中建模树木到规划机器人路径。在这篇文章中,我几乎没有触及表面。这些链接包含有趣的应用程序列表:链接 1、链接 2、链接 3、链接 4、链接 5。
  • 本文参考资料  弗朗切斯科·贝莱利

这篇关于沃罗诺伊图(Voronoi):迷人的世界【1/2】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/215903

相关文章

揭秘世界上那些同时横跨两大洲的国家

我们在《世界人口过亿的一级行政区分布》盘点全球是那些人口过亿的一级行政区。 现在我们介绍五个横跨两州的国家,并整理七大洲和这些国家的KML矢量数据分析分享给大家,如果你需要这些数据,请在文末查看领取方式。 世界上横跨两大洲的国家 地球被分为七个大洲分别是亚洲、欧洲、北美洲、南美洲、非洲、大洋洲和南极洲。 七大洲示意图 其中,南极洲是无人居住的大陆,而其他六个大洲则孕育了众多国家和

简单的Q-learning|小明的一维世界(3)

简单的Q-learning|小明的一维世界(1) 简单的Q-learning|小明的一维世界(2) 一维的加速度世界 这个世界,小明只能控制自己的加速度,并且只能对加速度进行如下三种操作:增加1、减少1、或者不变。所以行动空间为: { u 1 = − 1 , u 2 = 0 , u 3 = 1 } \{u_1=-1, u_2=0, u_3=1\} {u1​=−1,u2​=0,u3​=1}

简单的Q-learning|小明的一维世界(2)

上篇介绍了小明的一维世界模型 、Q-learning的状态空间、行动空间、奖励函数、Q-table、Q table更新公式、以及从Q值导出策略的公式等。最后给出最简单的一维位置世界的Q-learning例子,从给出其状态空间、行动空间、以及稠密与稀疏两种奖励函数的设置方式。下面将继续深入,GO! 一维的速度世界 这个世界,小明只能控制自己的速度,并且只能对速度进行如下三种操作:增加1、减

【Linux】萌新看过来!一篇文章带你走进Linux世界

🚀个人主页:奋斗的小羊 🚀所属专栏:Linux 很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~ 目录 前言💥1、初识Linux💥1.1 什么是操作系统?💥1.2 各种操作系统对比💥1.3 现代Linux应用💥1.4 Linux常用版本 💥2、Linux 和 Windows 目录结构对比💥2.1 文件系统组织方式💥2.2

Elasticsearch:无状态世界中的数据安全

作者:来自 Elastic Henning Andersen 在最近的博客文章中,我们宣布了支持 Elastic Cloud Serverless 产品的无状态架构。通过将持久性保证和复制卸载到对象存储(例如 Amazon S3),我们获得了许多优势和简化。 从历史上看,Elasticsearch 依靠本地磁盘持久性来确保数据安全并处理陈旧或孤立的节点。在本博客中,我们将讨论无状态的数据持

【AI大模型应用开发】2.1 Function Calling连接外部世界 - 入门与实战(1)

Function Calling是大模型连接外部世界的通道,目前出现的插件(Plugins )、OpenAI的Actions、各个大模型平台中出现的tools工具集,其实都是Function Calling的范畴。时下大火的OpenAI的GPTs,原理就是使用了Function Calling,例如联网检索、code interpreter。 本文带大家了解下Function calling,看

005:VTK世界坐标系中的相机和物体

VTK医学图像处理---世界坐标系中的相机和物体 左侧是成像结果                                                    右侧是世界坐标系中的相机与被观察物体 目录 VTK医学图像处理---世界坐标系中的相机和物体 简介 1 在三维空间中添加坐标系 2 世界坐标系中的相机 3 世界坐标系中vtkImageData的参数 总结:

深入RabbitMQ世界:探索3种队列、4种交换机、7大工作模式及常见概念

文章目录 文章导图RabbitMQ架构及相关概念四大核心概念名词解读 七大工作模式及四大交换机类型0、前置了解-默认交换机DirectExchange1、简单模式(Simple Queue)-默认DirectExchange2、 工作队列模式(Work Queues)-默认DirectExchange3、发布/订阅模式(Publish/Subscribe)-FanoutExchange4、路

攻防世界 unseping

unseping 攻防世界web新手练习 -unseping_攻防世界web新手题unseping-CSDN博客 这道题对我来说还是有点难,什么oct绕过命令执行第一次遇到捏,所以基本是跟着别人的wp写的,一点点记录吧 先对源码进行分析 <?phphighlight_file(__FILE__);//定义了一个ease类class ease{private $method;privat

世界公认十大护眼灯数据出炉!一文看懂孩子用的台灯哪个牌子好

近年来,随着科技的迅猛发展,诸如智能手机、电脑等电子设备在工作、学习及娱乐中的应用日益广泛,人们对这些设备的依赖程度也随之加深。然而,长时间面对屏幕不可避免地给眼睛带来伤害,如眼疲劳、干燥甚至近视等问题。因此,市场对能够缓解眼疲劳的照明产品的需求日益增长。这类护眼照明产品通常采用无频闪、无紫外线辐射等技术,旨在减少对眼睛的潜在危害,有效保护视力健康,并降低眼疾的发生率。随着护眼台灯的不断创新进步,