沃罗诺伊图
定义
沃罗诺伊图是按距离对空间作最近邻划分的结果。设平面上有一个离散点集,每个点对应一个区域,区域内任意位置到该点的距离都不大于到点集中其他点的距离,这样的区域称为沃罗诺伊区域或沃罗诺伊单元,全部单元拼合成沃罗诺伊图[1][5]。点集中的点通常称为生成点、母点或站点,划分出的单元在二维情形下是多边形,在三维情形下是多面体[6]。
用集合与距离的形式可写作 $V(p_i)=\{x \mid d(x,p_i) \le d(x,p_j),\ \forall j \neq i\}$,其中 $d$ 为距离函数[2]。由于每个单元都是若干半平面的交集,单元必然是凸的,其边由相邻生成点连线的垂直平分线构成,顶点则到 3 个或更多生成点等距[5][7]。位于元胞边界上的点,到两侧生成点的距离相等[4]。
该结构在文献中还有多个名称。二维情形常称泰森多边形(Thiessen Polygon),德国数学家狄利克雷早期研究中的同类构造则称狄利克雷镶嵌(Dirichlet Tessellation)[2][6]。
原理
沃罗诺伊图的核心是对偶关系。把生成点作为顶点,当且仅当两个生成点的沃罗诺伊单元存在公共边时在它们之间连边,得到的是德劳内三角剖分(Delaunay Triangulation);两者的单元、边和顶点一一对应,互为几何对偶,可以由其中一方推出另一方[1][7]。德劳内三角剖分满足空圆性质,即每个三角形的外接圆内部不含点集中的其他点[8]。
这一对偶性给出了实用的构造路径。先建立点集的德劳内三角网,再求每个三角形的外接圆圆心,最后把相邻三角形的外心依次连接,即得到以原始点为生成点的多边形网;位于点集凸包上的生成点,其单元无界,边延伸至无穷远[1][9]。常用算法包括分治法、扫描线算法与基于德劳内三角剖分的增量算法,其中扫描线算法的复杂度为 $O(n \log n)$[2]。
除了标准的欧氏距离,还可以更换距离度量或给生成点赋权,得到曼哈顿沃罗诺伊图、加权沃罗诺伊图、高阶沃罗诺伊图等变体;在道路网络等非均匀空间中,距离由网络上的最短路径决定,相应推广称为网络沃罗诺伊图[2][10]。
发展历程
用凸区域分割空间的想法可以上溯到 1644 年笛卡尔的著作,当时只是作为解释自然现象的图示,尚未形成一般理论[6][11]。1850 年,德国数学家狄利克雷在研究二次型时使用了二维与三维的同类划分[11][12]。
1908 年,俄国数学家格奥尔吉·沃罗诺伊定义并研究了一般 $n$ 维情形,该结构因此以他的名字命名[6][11]。1911 年前后,泰森把这一方法用于气象台站的辖区划分,以由站点雨量估算区域平均降水,泰森多边形的名称由此在气象与地理学界流传[2][4]。
1934 年,德劳内提出德劳内三角网,并确立其与沃罗诺伊图的对偶关系,使后者的构造可以借助三角剖分完成[2]。20 世纪 70 年代以后,随着计算几何成为独立学科,沃罗诺伊图的构造算法与复杂度分析逐步完善,并被引入地理信息系统、计算机图形学、机器人导航等应用领域[2][3]。
应用
在气象与水文统计中,泰森多边形被用作面积权重法的空间单元。把相邻气象站连成三角形并作各边垂直平分线,围成的多边形内只用该站观测值代表全区降水强度,由此估算流域面雨量[4][13]。这一方法也用于把一组样本测量值概化到其周边区域,例如为零售门店快速划定服务范围[14]。
地理信息与公共设施规划中,沃罗诺伊图可确定最近的设施位置。以医院、消防站或接种门诊为生成点划分辖区,可评估各点负责的范围与服务人口,用于优化资源分配[15][2]。1854 年伦敦霍乱疫情期间,斯诺以水泵位置划分地图区域并统计各区死亡病例,识别出百老汇街水泵为感染集中地,这一分析常被视作该图思想的前身[6][11]。
在工程与科学计算中,沃罗诺伊图用于有限体积法的控制体积生成、有限元网格划分、多晶体材料的晶粒建模与裂纹形态模拟[7]。机器人领域用它把环境骨架化为节点图以规划路径和分割未知地图,通信领域则用于基站覆盖区域的划分与邻区判断[16][11]。在计算机图形与建筑设计中,该结构被用于图像分割、网格生成与空间布局,建筑表皮与构筑物的分格亦常采用类似图形[15][11]。
局限
高维与大数据情形下的计算代价是主要制约。沃罗诺伊图所需的存储量随维数呈指数增长,对高于六维的中大型数据集,直接计算并不现实,因此实际应用多集中在二维与三维空间[1]。即使固定维数,基于栅格的实现也存在精度与速度的取舍:网格越细结果越精确,但耗时随之增加[17]。
由该图直接做最近邻查询并不方便,它给出的是空间的划分形式,而不是索引结构,故常需借助其他几何结构完成查询[1]。在数值应用上,以泰森多边形为单元的面积权重法假定各站点数值在其单元内均匀不变,单元边界处会出现数值突变,难以表现连续渐变,因此更适合离散或分级数据的面上摊派[5]。
标准沃罗诺伊图以欧氏距离为基础,当空间被道路、障碍或地形分割时,直线距离与实际通行成本不一致,需要改用网络距离或加权形式,模型也随之复杂化[10]。此外,点集处于特殊情况(如三点共线或四点共圆)时,对偶关系不再唯一对应,构造时须特殊处理[18]。
参见
参考资料
- 沃罗诺伊图 - MATLAB & Simulink [引用日期2026-10-29]
- 沃罗诺伊图 [引用日期2026-10-29]
- wiley.com 上的网页 [引用日期2026-10-29]
- 泰森多边形分析 [引用日期2026-10-29]
- Voronoi-Diagramm – Wikipedia [引用日期2026-10-29]
- bristol.ac.uk 上的网页 [引用日期2026-10-29]
- 三二解说 [引用日期2026-10-29]
- 沃罗诺伊图与德劳内三角剖分 | Bohrium [引用日期2026-10-29]
- 维诺图分析与实现 [引用日期2026-10-29]
- システム制御情報学会論文誌，Vol [引用日期2026-10-29]
- Diagramme de Voronoï — Wikipédia [引用日期2026-10-29]
- ボロノイ図 [引用日期2026-10-29]
- SuperMap iClient for OpenLayers - 泰森多边形是荷兰气候学家 A [引用日期2026-10-29]
- 泰森多边形构建原理 [引用日期2026-10-29]
- 大自然的优化算法：优雅的沃罗诺伊图 [引用日期2026-10-29]
- 对G(m)中的每一对节点(p,q),如果它们在地图中是邻近点时,我们就在G(m)上为p和q间增加一条边 [引用日期2026-10-29]
- Automated Thiessen polygon generation - Technical Note [引用日期2026-10-29]
- 數學思維與解題期末報告 [引用日期2026-10-29]