写在前面：

博主本人大学期间参加数学建模竞赛十多余次，获奖等级均在二等奖以上。为了让更多学生在数学建模这条路上少走弯路，故将数学建模常用数学模型算法汇聚于此专栏，希望能够对要参加数学建模比赛的同学们有所帮助。

1.Voronoi图介绍

Voronoi 图的又叫泰森多边形或Dirichlet 图，它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。

Voronoi图将相邻两个生成元相连接，并且做出连接线段的垂直平分线，这些垂直平分线之间的交线就形成一些多边形,这样就把整个平面剖分成一些分区域，一个分区域只含有一个生成元，分区域内生成元的属性可以代替此分区域的属性，而且可以根据分区域的面积作为权重推测出该区域中生成元的平均水平。

若两个生成元 的Voronoi 区域有公共边，就连接这两个点，以此类推遍历这n个生成元，可以得到一个连接点集S的唯一确定的网络，称为Delaunay 三角网格。

2. Voronoi图性质

（1）Voronoi图与Delaunay三角网格图对偶;

（2） Voronoi图具有局域动态性，即增加和删除一个生成元只影响相邻生成元的Voronoi区域；

（3）如果点 P在区域中,则P到各生成元的距离中,到生成元的距离最小；

（4）两个相邻Voronoi区域的公共边上任意一点到这两个区域的生成元距离相等;

（5）Voronoi 区域的顶点到邻近的生成元的距离相等，即与这个顶点有关的Voronoi区域的生成元共圆，称这个圆为最大空圆；

3.案例分析

例1 根据表中10个点的数据画出对应的Voronoi图及其对偶Delaunay三角网格图。

使用Matlab画图的结果如下：

画图的Matlab程序如下：

clc,clear
x=[0.9523 0.7621 0.6068 0.4567 0.2312 0.8866 0.7621 0.0185 0.4455 0.3369];
y=[0.9566 0.7041 0.6789 0.5674 0.8422 0.4432 0.2034 0.3421 0.8368 0.6666];
subplot(1,2,1);voronoi(x,y,'-k');%直接画voronoi图
axis([0,1,0,1]);title('Voronoi图');
subplot(1,2,2);plot(x,y,'.'),hold on
tri=delaunay(x,y) %生成delaunay三角剖分，每行是一个三角形的顶点索引
triplot(tri,x,y,'k-');%画delaunay三角形
axis([0,1,0,1]);title('Delaunay三角形');
hold off
figure;
[vx,vy]=voronoi(x,y);%生成voronoi图顶点的横坐标和纵坐标
plot(x,y,'kp',vx,vy,'k-');
axis([0,1,0,1]);hold on
triplot(tri,x,y,'b-');
title('对比图');