简介Voronoi图Voronoi Diagrams

这是计算机的经典算法。

问题引入

倘若一张大白纸上有很多三角点，掉进去一个五星点，问，哪个三角离着五星最近？简单，算距离呗，这个五星到其他所有三角点的距离，找到最小的那个就行。

若掉进去1亿次，每次掉进去的位置都不一样，每次问相同的问题，怎样能用最快的速度得出答案？你这总不能算一亿次吧！

通俗解释

Voronoi Diagrams的作用：用已知的点划分空间。这种划分，使得当自己在随机选择的一个点时，能立刻找到当前空间内所有点中最近的那个点。

哎，有了voronoi，掉到哪里，就找那个领地的主，离五星最近的三角就是它！

怎么获得voronoi图划分呢？

见这个pdf的3.2构造方法，和2001年这个学生的本科课程设计的“求解 Voronoi 图的各种算法”。

还能解决什么问题？

除了解决开始的问题，voronoi更多的是用在延展问题上。
当然2001年这个学生的本科课程设计其实已经列举了不少了。

 人类学和考古学：考察由不同的部落、首领、堡垒等所确定的势力范围或影响范围。
 天文学：识别星群和星系群，比如由太阳和其它恒星所确定的星系。
 生物学、生态学和林学：不同植物间生存竞争关系的研究与模型。
 几何学：多面体的“好的”三角化方案。
 气象学：根据几个点的降雨量测量来估计一个地区的平均降雨量。
 模式识别：从二维形状提取出一位信息，从而找到形状的简单描述，比如“中轴”
和“骨架”。
 生理学：通过肌肉组织截面的毛细管分布情况的分析来计算氧传输。
 机器人技术：在有障碍物情况下的路径规划。
 统计学：分析统计聚类。
 动物学：动物疆域的分析。

比如求不规则多边形的中心（medial axis算法），或者说 “图像获得skeleton”。（当然现在的骨架提取很多都是深度学习的天下了），更具体的，可以看看2015年清华的学生的课程报告

机器人技术，在有障碍物情况下的路径规划（Voronoi planner）和路径平滑，可以查看这个知乎等。

还可以制作字符表情包。