一、Voronoi Noise

沃罗诺伊图（Voronoi Diagram，也称作Dirichlet tessellation，狄利克雷镶嵌）是由俄国数学家Georgy Fedoseevich Voronoi建立的空间分割算法，其空间划分思想来源于笛卡尔用凸域分割空间理论，也就是说，Voronoi图实际是一种空间划分方法，这种划分方法解决了这样一个问题：如何根据已知点划分空间，使得晶胞与点一一对应，并使晶胞内任取一点都与最近的已知点围在一起，或者换一种说法就是沃罗诺伊图基于一组特征点将空间分割成不同区域，而每一区域又仅包含唯一的特征点，并且该区域内任意位置到该特征点的距离比到其它的特征点都要更近。所以Voronoi图有以下特性（以二维平面为例）：
（1）每个V多边形内有一个特征点；
（2）每个V多边形内点到该特征点距离短于到其它特征点的距离；
（3）多边形边界上的点到生成此边界的特征点距离相等；
（4）邻接图形的Voronoi多边形界线以原邻接界线作为子集。

Voronoi图作一种空间划分算法，由于其特性，在很多领域都有应用，例如用来规划电信信号塔选址以达到更好的覆盖和经济性；用来规划航线达到充分利用空间但又防范避免空中撞击风险；用来规划路线达到避开障碍物的目的。另外其在地理学、气象学、结晶学、航天、核物理学、机器人等领域具有广泛的应用。
Voronoi Noise

对图形学来讲，Voronoi图的空间划分特性可以用来模拟物体破碎效果：
Voronoi Noise

　　
Voronoi图能形成独特的图案纹理，也常用在程序纹理生成中。

二、Delaunay Triangulation

Voronoi图定义简单，我们甚至可以使用手工做铅垂线的方式来作出给定特征点的Voronoi图，但理论上解决这个问题却比较难，直到Voronoi图提出来后25年，Delaunay才提出了解决该剖分完整而实用的方法，这就是著名的德劳内三角剖分（Delaunay Triangulation）。

Delaunay三角剖分具有以下特性：

1、在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在并与其通视，即空圆特性；
2、在构网时，总是选择最邻近的点形成三角形并且不与约束线段相交；
3、形成的三角形网总是具有最优的形状特征，任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形6个内角中最小的角度不会变大；
4、不论从区域何处开始构网，最终都将得到一致的结果，即构网具有唯一性。

Delaunay三角剖分也有很多算法，网上相关资料很多，不再详述，本文参考文献部分也列出了部分Delaunay三角剖分方面的文章。
Delaunay三角剖分是Voronoi图的对偶图，因此得到Delaunay三角剖分后就可以得到Voronoi图。