沃罗诺伊、德劳内、中轴介绍

本文主要讲解一下计算几何中的Voronoi相关的知识。首先给出题目中的三个英文单词相关的数学定义:

Voroni region：given a set of points in the 2D,for each point p, its Voronoi region is a set of points V(p):

V(p) = {x: |p-x| <= |q-x|} q is any point in the set which is nonequal p; 也就是说一个点的Voronoi区域是到这个点的距离比到点集中其他所有点的距离小的那些点。

these Voronoi regions form the Voronoi diagram.

关于Voronoi图的算法，主要包括incremental construction，divide and conquer算法，和Fortune’s algorithm。重点讲解一下最后一种方法。

这篇文章介绍和改进了上述的算法 Primitives for the manipulation of general subdivisions and the computation of Voronoi 。

主要的核心思想是对于每个点而言，在每个点上构建起一个圆锥，这个圆锥和平面是交45°的，于是对于相邻的两个圆锥而言，会在上面相交，将他们相交的部分投影到平面上，可以看到中间是一条直线，就是Voronoi图的边。现在使用一个和平面同样是交45°的平面进行扫描，它和圆锥的交线是一条抛物线，相邻的圆锥的抛物线在平面上的投影的交点形成了Voronoi图的边。具体的算法，请看上面的paper。

Delaunay triangulations：这部分内容可以看：http://www.cnblogs.com/RenLiQQ/archive/2008/02/06/1065399.html，这篇文章较详细的介绍了Delaunay三角化的知识。

这里对于Delaunay triangulation和hull的关系。2D点的Delaunay三角剖分，可以使用3D的hull来求解。首先将2D点投影到3D空间，其实就是为每个点添加了一个Z分量，z = x*x+y*y，然后将上述3D中的点进行求解凸包。然后将这个凸包直接投影到平面上，就可以得到Delaunay三角剖分了。如果想要证明，可以从凸包上三角形投影到平面上时，它的外接圆没有任何其他内点来证明。

medial axis：a set of points inside polygon that have more than one closest points among the points of boundary of polygon.其实就是一个在多边形内部的圆，它和多边形有多于一个相切点，这些圆的圆心组成的点集就是medial axis。

现在有个问题需要考虑一下，就是Voronoi vertices和medial axis有什么关系？