Delaunay Triangulation
"Delaunay Triangulation" Delaunay Triangulation 是一种特殊的三角剖分方法,广泛应用于计算机图形学、计算机视觉、地理信息系统、科学计算等领域。该方法的定义、特性、算法等方面的知识点将在以下进行详细的阐述。 定义 三角剖分是指将一个散点集合剖分成不均匀的三角形网格,Delaunay Triangulation 是三角剖分的一种特殊方法。它的定义为:假设 V 是二维实数域上的有限点集,边 e 是由点集中的点作为端点构成的封闭线段,E 为 e 的集合。那么该点集 V 的一个三角剖分 T=(V,E) 是一个平面图 G,该平面图满足条件:除了端点,平面图中的边不包含点集中的任何点;没有相交边;平面图中所有的面都是三角面,且所有三角面的合集是散点集 V 的凸包。 Delaunay Triangulation 的定义 Delaunay Triangulation 是一种特殊的三角剖分,它的定义为:如果点集 V 的一个三角剖分 T 只包含 Delaunay 边,那么该三角剖分称为 Delaunay Triangulation。Delaunay 边是指满足空圆特性的边,即存在一个圆经过两个端点,圆内不含点集 V 中任何其他的点。 Delaunay Triangulation 的特性 Delaunay Triangulation 具有以下特性: 1. 最接近:以最近临的三点形成三角形,且各线段(三角形的边)皆不相交。 2. 唯一性:不论从区域何处开始构建,最终都将得到一致的结果。 3. 最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。 4. 最规则:如果将三角网中的每个三角形的最小角进行升序排列,则 Delaunay Triangulation 的排列得到的数值最大。 5. 区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。 6. 具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。 算法 Delaunay Triangulation 的算法有多种,常见的有 Lawson 算法和 Bowyer-Watson 算法。 Lawson 算法是逐点插入的算法,思路简单,易于编程实现。基本原理为:首先建立一个大的三角形或多边形,把所有数据点包围起来,向其中插入一点,该点与包含它的三角形三个顶点相连,形成三个新的三角形,然后逐个对它们进行空外接圆检测,同时用 Lawson 设计的局部优化过程 LOP 进行优化。 Bowyer-Watson 算法是另一种常见的算法,它的基本步骤是:构造一个超级三角形,包围所有数据点,然后逐点插入该超级三角形中,形成新的三角形同时进行空外接圆检测和局部优化过程。 应用 Delaunay Triangulation 广泛应用于计算机图形学、计算机视觉、地理信息系统、科学计算等领域。它可以用于构建三维模型、计算机辅助设计、地理信息系统、科学计算等领域。