深入浅出泰森多边形Voronoi算法

概述

    Voronoi图，又称泰森多边形或狄利克雷镶嵌，是一种基于离散点集的空间划分方法。每个区域内的点到其对应控制点的距离比到其他控制点更近，边界由相邻控制点连线的垂直平分线构成。Voronoi图广泛应用于地理信息系统（如服务区划分）、计算机图形学（如自然纹理生成）、机器人路径规划、生物学（如细胞结构模拟）等领域。其核心优势在于高效的空间分割能力和对偶性（与Delaunay三角剖分互为对偶）。通过加权、高阶或三维扩展，Voronoi图可适应复杂场景需求，是连接数学理论与实际应用的重要工具。

 

数学定义

    在数学上，Voronoi图有非常严谨的定义。给定一个度量空间(M,d)和其中的一个离散点集S⊂M，Voronoi图将该空间分割为多个区域，每个区域对应集合S中的一个特定点。具体来说，设S={s₁, s₁,..., s_n​}是度量空间M中的有限点集，对于任意一点s_i∈S，其对应的Voronoi区域V(s_i)定义为：

    这里， d(x,y)表示两点x和y之间的距离函数。

通俗解释

    举个例子来说，假设在一个城市里有几家咖啡店，Voronoi图可以帮助你找到每个地方最近的咖啡店。在这个图中，每个咖啡店都有自己的“势力范围”，在这个范围内居住的人到这家咖啡店的距离是最近的。这样，通过Voronoi图，我们可以直观地看到各个服务设施（如咖啡店、医院、学校等）的服务范围。

应用领域

    Voronoi 图因其高效的空间划分能力，广泛应用于以下场景：

    地理与城市规划：划分服务覆盖范围。

    计算机图形学：生成自然纹理（如蜻蜓翅膀纹理）、地形建模。

    路径规划：构建避障最短路径。

    生物学与材料科学：模拟细胞结构、晶体生长。

    无线通信：基站信号覆盖优化。

算法说明

    创建Voronoi图通常需要先构建Delaunay三角网，这是因为Voronoi图与Delaunay三角网是对偶结构，即它们之间存在一一对应关系。以下是建立Voronoi图的一般算法：

    1、首先布置Voronoi的控制点，并基于控制点构建Delaunay三角网。

    2、画出所有三角网边的垂直平分线，垂直平分线构成Voronoi的边，垂直平分线的交点即为Voronoi的顶点。

Voronoi软件

    如果需要快速生成Voronoi泰森多边形二维或三维模型，可采用成熟的软件来进行。

    1、AF_Voronoi V2.0版本

    可随机生成彩色Voronoi晶格图片或对现有的图片进行晶格化处理。

    2、CAD Voronoi V2.5版本

    可在AutoCAD内快速生成二维的Voronoi模型，并具备区块编码、面积计算等功能，方便科研使用。

    3、CAD Voronoi 3D V1.0.1版本

    具备在AutoCAD内建立三维多种形状的Voronoi晶格三维实体模型。

    4、CAD泰森多边形框架3D V1.0.0版本

    在AutoCAD内建立三维Voronoi边线构成的框架结构模型。