这是计算机的经典算法。
问题引入
倘若一张大白纸上有很多三角点,掉进去一个五星点,问,哪个三角离着五星最近?简单,算距离呗,这个五星到其他所有三角点的距离,找到最小的那个就行。
若掉进去1亿次,每次掉进去的位置都不一样,每次问相同的问题,怎样能用最快的速度得出答案?你这总不能算一亿次吧!
通俗解释
Voronoi Diagrams的作用:用已知的点划分空间。这种划分,使得当自己在随机选择的一个点时,能立刻找到当前空间内所有点中最近的那个点。
哎,有了voronoi,掉到哪里,就找那个领地的主,离五星最近的三角就是它!
怎么获得voronoi图划分呢?
见这个pdf的3.2构造方法,和2001年这个学生的本科课程设计的“求解 Voronoi 图的各种算法”。
还能解决什么问题?
除了解决开始的问题,voronoi更多的是用在延展问题上。
当然2001年这个学生的本科课程设计其实已经列举了不少了。
人类学和考古学:考察由不同的部落、首领、堡垒等所确定的势力范围或影响范围。
天文学:识别星群和星系群,比如由太阳和其它恒星所确定的星系。
生物学、生态学和林学:不同植物间生存竞争关系的研究与模型。
几何学:多面体的“好的”三角化方案。
气象学:根据几个点的降雨量测量来估计一个地区的平均降雨量。
模式识别:从二维形状提取出一位信息,从而找到形状的简单描述,比如“中轴”
和“骨架”。
生理学:通过肌肉组织截面的毛细管分布情况的分析来计算氧传输。
机器人技术:在有障碍物情况下的路径规划。
统计学:分析统计聚类。
动物学:动物疆域的分析。
比如求不规则多边形的中心(medial axis算法),或者说 “图像获得skeleton”。(当然现在的骨架提取很多都是深度学习的天下了),更具体的,可以看看2015年清华的学生的课程报告
机器人技术,在有障碍物情况下的路径规划(Voronoi planner)和路径平滑,可以查看这个知乎等。
还可以制作字符表情包。