目录

一，三角剖分

二，Delaunay三角剖分

1，Delaunay边

2，Delaunay三角剖分

3，点集的条件

4，Delaunay三角剖分的特点

三，泰森多边形

1，泰森多边形

2，泰森多边形的特点

一，三角剖分

        三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：
        1.除了端点，平面图中的边不包含点集中的任何点。
        2.没有相交边。
        3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

二，Delaunay三角剖分

1，Delaunay边

假设对于E中的一条边e（两个端点为a,b），存在一个圆经过a,b两点，圆内不含点集V中任何其他的点，圆上最多三个点，则e称为Delaunay边。

ps：这样的不含其他点的圆称为空圆。

2，Delaunay三角剖分

如果点集V的一个三角剖分T只包含Delaunay边，那么T称为Delaunay三角剖分。

3，点集的条件

点集具有Delaunay三角剖分的充要条件是，不存在一个空圆上有四个点。

4，Delaunay三角剖分的特点

（1）如果一个点集不存在一个空圆上有四个点，那么就有唯一的Delaunay三角剖分。

（2）最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大。

（3）区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。

三，泰森多边形

1，泰森多边形

泰森多边形（剖分）是基于Delaunay三角剖分的，基于这个剖分结果，把所有边的垂直平分线画出来，就构成泰森多边形。

2，泰森多边形的特点

（1）每个多边形内有且仅有一个点（样点）

（2）多边形内的任何位置离该多边形的样点的距离最近，距离其他多边形的样点较远。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/124361736