The world of Voronoi diagrams (2021)
10 months ago
- #mathematics
- #data-science
- #geometry
- 沃罗诺伊图（Voronoi diagram），又称狄利克雷镶嵌（Dirichlet tessellation）或泰森多边形（Thiessen polygons），是制图学、生物学、建筑学等多领域常见的自然空间分割模式。
- 该图将平面划分为围绕种子点的单元区域，每个单元包含离该种子点最近的所有空间点。
- 这种高效的空间分配方式在自然界中广泛存在，如洋葱表皮、菠萝蜜外壳和长颈鹿斑纹等结构，均呈现均匀生长的沃罗诺伊特征。
- 人工建筑中也应用该原理，如北京奥运场馆'水立方'的膜结构设计，以及宋代瓷器开片釉的裂纹形态。
- 在平面艺术领域，沃罗诺伊图案常用于创作抽象纹理与背景效果。
- 该模型可推广至n维空间，并支持欧氏距离、曼哈顿距离等多种度量标准。
- 其数学本质与k近邻算法、德劳内三角剖分密切相关，后者在三维建模中具有重要价值。
- 劳埃德算法（Lloyd's algorithm）通过迭代优化种子点位置实现单元均匀化，这也是k均值聚类的理论基础。
- 扫描线算法和基于德劳内三角剖分的构建方法，是当前最高效的沃罗诺伊图生成技术。
- 应用场景涵盖森林建模、机器人路径规划、游戏程序化地图生成等跨学科领域。