Delaunay三角剖分(Delaunay Triangulation)

Delaunay三角剖分(Delaunay Triangulation)
1.Delaunay边: 假设E中的一条边e(两个端点为a,b)，e若满足下列条件，则称之为Delaunay边: 存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。
2.Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。
3.假设T为V的任一三角剖分，则T是V的一个Delaunay三角剖分，当且仅当T中的每个三角形的外接圆(circumcircle)的内部不包含V中任何的点。

https://mathworld.wolfram.com/DelaunayTriangulation.html

Delaunay三角剖分所具备的优异特性：
1) 最接近：以最近临的三点形成三角形，且各线段(三角形的边)皆不相交。
2) 唯一性：不论从区域何处开始构建，最终都将得到一致的结果。
3) 最优性：任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话，那么两个三角形六个内角中最小的角度不会变大。
4) 最规则：如果将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大。
5) 区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。
6) 具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。

Voronoi diagram(泰森多边形又叫冯洛诺伊图)，得名于Georgy Voronoi，是一组由连接两邻点线段的垂直平分线组成的连续多边形组成。
一个泰森多边形内的任一点到构成该多边形的控制点的距离小于到其他多边形控制点的距离。
Voronoi Diagram
The partitioning of a plane with n points into convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. The cells are called Dirichlet regions, Thiessen polytopes, or Voronoi polygons.
Voronoi diagrams were considered as early at 1644 by René Descartes and were used by Dirichlet (1850) in the investigation of positive quadratic forms. They were also studied by Voronoi (1907), who extended the investigation of Voronoi diagrams to higher dimensions. They find widespread applications in areas such as computer graphics, epidemiology, geophysics, and meteorology. A particularly notable use of a Voronoi diagram was the analysis of the 1854 cholera epidemic in London, in which physician John Snow determined a strong correlation of deaths with proximity to a particular (and infected) water pump on Broad Street.