关于Delaunay三角剖分

创作时间:

作者:

@小白创作中心

关于Delaunay三角剖分

引用

CSDN

https://m.blog.csdn.net/ttod/article/details/144441182

Delaunay三角剖分是一种将平面上的点集连接成三角形网格的方法，其关键特性是每个三角形的外接圆内不包含点集中的其他点。这种方法在计算机图形学、地理信息系统和有限元分析等领域有着广泛的应用。

定义

Delaunay三角剖分（Delaunay Triangulation），也称为狄洛尼三角剖分，是一种将平面上的点集连接成三角形网格的方法。其实就是每个三角形的外接圆内不包含点集中的其他点。

特性

空外接圆特性

这是Delaunay三角剖分最关键的特性。例如，假设有点集A、B、C、D，如果三角形是Delaunay三角剖分中的一个三角形，那么D点不在三角形ABC的外接圆内部。这个特性保证了三角剖分的最优性，在很多应用中可以避免狭长三角形的出现，使得三角形形状比较“规则”。

最大最小角特性

在所有可能的三角剖分中，Delaunay三角剖分所形成的三角形的最小角是最大的。这意味着它产生的三角形相对比较“胖”，而不是很“瘦”。这种特性在有限元分析等数值计算领域非常重要，因为狭长的三角形可能会导致数值计算的不稳定。

构建方法

增量法

从一个初始的三角形开始（当点集只有三个点时，就是这三个点构成的三角形），然后逐个添加点。每次添加一个点时，检查该点位于哪些三角形的外接圆内。如果一个点在某个三角形的外接圆内，就对这个三角形进行翻转操作。例如，假设有三角形，新加入的点在其外接圆内，那么就删除三角形，连接、和，形成三个新的三角形、和。

分治法

先将点集划分为两个较小的子集，分别对这两个子集进行Delaunay三角剖分。然后将这两个子三角剖分合并。在合并过程中，需要检查并修正边界附近的三角形，以满足Delaunay三角剖分的空外接圆特性。

应用领域

计算机图形学

在三维建模中，Delaunay三角剖分用于将三维模型的表面进行三角网格化。比如，在地形建模中，将地形上的采样点进行Delaunay三角剖分，能够很好地重建地形的表面形状，为后续的渲染等操作提供基础。在曲面重建方面，对于扫描得到的点云数据（例如通过三维扫描仪获取的物体表面点的集合），Delaunay三角剖分可以将这些点连接成曲面，从而还原物体的形状。

地理信息系统（GIS）

用于地图绘制中的地形表面建模。例如，将地理区域内的高程采样点进行三角剖分，能够生成数字高程模型（DEM），直观地表示地形的起伏。在空间分析方面，Delaunay三角剖分可以帮助确定地理要素之间的邻近关系，比如分析城市中不同功能区之间的相邻情况等。

有限元分析

在有限元分析中，将求解区域划分为三角形单元（通过Delaunay三角剖分实现），可以对物理问题（如结构力学中的应力分析、热传导问题等）进行数值求解。由于Delaunay三角剖分的良好特性，使得有限元分析的计算精度和稳定性得到提高。

关于德劳内

鲍里斯・尼古拉耶维奇・德劳内（Boris Nikolayevich Delaunay，俄语：Бори́с Никола́евич Делоне́，1890年3月15日-1980年7月17日）是一位苏联/俄罗斯的杰出数学家、登山家，也是物理学家尼古拉・鲍里索维奇・德劳内的父亲。以下是对他的具体介绍：

生平经历

鲍里斯出生于俄罗斯帝国的圣彼得堡，其姓氏源于他的祖先——在1812年拿破仑入侵俄国时被俘的法国军官德劳内，这位军官是巴士底狱总督德劳内侯爵的侄子，后来他与图哈切夫斯基贵族家族的一位女子结婚并留在了俄国。小时候，鲍里斯的家人常去阿尔卑斯山度夏，在那里他学会了登山，并于1913年成为俄罗斯顶尖的三位登山家之一。俄国革命后，他在高加索和阿尔泰山区登山，位于别卢哈附近的一座4300米高的山峰以他的名字命名。20世纪30年代，他首批获得苏联登山运动大师资格。

数学成就

Delaunay三角剖分

1934年，鲍里斯・尼古拉耶维奇・德劳内提出了著名的“德劳内三角化”。其内容是对于平面上给定的点集P，存在一种剖分DT(P)，使得在P中没有点严格处于DT(P)中任意一个三角形外接圆的内部。这一理论几乎是后世所有mesh算法的基础，如Lawson算法、Bowyer-Watson算法等都是对德劳内三角化的继承和发展1。