Delaunay三角网之逐点插入算法 Matlab 实现

Delaunay三角网之逐点插入算法 Matlab 实现

Delaunay 三角网是一种无需人为干预的自动生成网格的技术，它能够在任意多边形的边界上生成具有优良性质的三角网。逐点插入法是一种实现 Delaunay 三角网的基本方法，它通过不断地加入新的点来构建 Delaunay 三角网。

在本文中，我们将介绍如何使用 Matlab 实现逐点插入算法并构建 Delaunay 三角网。首先，我们需要了解 Delaunay 三角网具有的一些优良性质：

1. 最小化了所有三角形的最小角度。
2. 保证每个三角形的外接圆内部不包含其它节点。
3. 不会产生悬挂点和自交三角形。

具有这些优良性质的 Delaunay 三角网在许多应用中都具有重要的作用。下面我们将介绍如何使用逐点插入算法构建 Delaunay 三角网。

逐点插入算法的基本思想是不断地加入新的点，并更新已有的三角形，使其仍然满足 Delaunay 条件。具体而言，插入新点时，首先找到所有包含该点的三角形，然后删除这些三角形，并连接该点与这些三角形的顶点构成的新三角形。最后，将新生成的三角形进行优化，使得其满足 Delaunay 条件。

下面是逐点插入算法的 Matlab 实现代码：

function tri = delaunay_triangulation(points)
    % 初始化
    tri = [];
    n = si