delaunay三角网 c++

Delaunay三角网是一种用于数值计算和计算几何中常用的数据结构。它可以将给定的二维点集按照一定的规则连接成三角形，使得任意两个点之间的直线不会穿过其他三角形的内部或边界。

Delaunay三角网的构建过程主要分为以下几个步骤：首先，选择一个超级三角形，将所有的点都包含在内，并将超级三角形加入到Delaunay三角网中。然后，依次将每个点插入到已有的三角形中，形成新的三角形，并更新使得新形成的网为空心的三角形的边界。最终，将超级三角形及其相关的三角形删除，得到最终的Delaunay三角网。

Delaunay三角网具有很多优点。首先，它保持了点集的凸壳性质，即保证了任意两个点之间的最短路径在Delaunay三角网中。其次，它能够高效地计算包括Voronoi图等其他几何结构。此外，Delaunay三角网还可以用于计算三角网内部的点的一些属性，比如最大最小角度、周围点的平均距离等。因此，Delaunay三角网在计算几何、计算机图形学等领域得到了广泛的应用。

总而言之，Delaunay三角网是一种用于连接二维点集的数据结构，具有许多优点和应用。它能够高效地计算最短路径和其他几何结构，并可用于计算点的属性。通过构建Delaunay三角网，我们可以更好地理解和分析二维空间中的数据。