C++ Delaunay 三角剖分

引言

Delaunay 三角剖分 是计算几何中的一项基本概念。它广泛应用于计算机图形学、网格生成、地形建模等方面。该概念由 **Boris Delaunay** 于 1934 年首次提出，因其高效性和从点集中生成高质量三角形的能力而备受赞誉。

在本文中，我们将深入探讨 Delaunay 三角剖分，并学习如何在 C++ 中实现它。我们将讨论 Delaunay 三角剖分的意义、该技术定义的问题，以及一个关于使用 C++ 编程语言构建 Delaunay 三角形的教学教程。

问题陈述

目标是创建点之间的连线网络，使得没有任何点位于这些连线定义的任何三角形内部。这种配置应该能够最大化最小角度，从而产生最优的、条件良好的网格。

主要挑战在于尽可能有效地构建此三角剖分，同时牢记其最优性。它还必须考虑多种边缘情况（例如，共线性、退化），以确保在实际场景中具有足够的鲁棒性。

为了直接解决这个问题，我们将使用 Delaunay 三角剖分，它能确保三角剖分的某些良好特性，如最大化最小角度和最小化外接圆半径。通过构建 Delaunay 三角剖分，我们的目标是提出一个网格，该网格能够有效地进行计算，而不会在不同应用中出现任何几何变形。

程序

让我们以一个例子来说明 C++ 中的 Delaunay 三角剖分。

输出

Triangle: (-2, -1), (2, -1), (0, 0)
Triangle: (0, 0), (1, 2), (1, 0)
Triangle: (2, -1), (1, 2), (0, 1)
Triangle: (1, 2), (0, 0), (0, 1)
Triangle: (-2, -1), (0, 0), (0, 1)
Triangle: (1, 0), (-2, -1), (0, 1)
Triangle: (1, 2), (-2, -1), (1, 1)
Triangle: (1, 0), (1, 2), (1, 1)
Triangle: (0, 0), (2, -1), (0.5, 0.5)
Triangle: (2, -1), (0, 1), (0.5, 0.5)
Triangle: (0, 1), (0, 0), (0.5, 0.5)
Triangle: (0, 0), (1, 0), (0.5, 0.5)
Triangle: (1, 0), (0, 1), (0.5, 0.5)
Triangle: (0, 1), (0, 0), (0.5, 0.5)
Triangle: (-2, -1), (1, 0), (0.5, 0.5)
Triangle: (1, 0), (1, 1), (0.5, 0.5)
Triangle: (1, 1), (-2, -1), (0.5, 0.5)

说明

1. 结构定义

• 在这个例子中，我们使用两个结构，即 Point 和 Triangle。
• 这个结构用 x 和 y 对表示 2D 空间 中的点。
• 这是一个描述由三个点组成的三角形的结构。

2. 距离计算函数

• 此代码提供了计算两点之间 欧几里得距离 的函数。它以后可以用来计算三角形的外接圆半径。

3. 内圆测试

• 另一种方法是执行内圆测试。此测试使用行列式来检查一个点是否位于三角形外接圆的内部或外部。
• 在三角剖分过程中，内圆测试有助于我们识别 “坏三角形”。

4. 三角剖分函数

• 该程序遵循 Bowyer-Watson 算法 进行 Delaunay 三角剖分。
• 首先，它创建一个覆盖所有输入点的“超级三角形”。通常，这个超级三角形是一个超越输入点凸包的大三角形。
• 然后，它遍历输入集中的每个点。
• 最后，它使用上述移除的“坏三角形”的顶点来创建新三角形。
• 该算法会移除任何包含超级三角形顶点的三角形，因为它们不被包含在最终的 Delaunay 三角剖分中。
• 因此，这些三角形构成了输入点的 Delaunay 三角剖分。

5. Main 函数

• 有了这些知识，主函数创建一个点集，并调用三角剖分函数来生成 Delaunay 三角剖分。
• 之后，可以通过将这些三角形打印到屏幕上来可视化它们。

复杂度分析

时间复杂度

• 通常，Bowyer-Watson 算法的时间复杂度为 O(n^2)，其中 n 是输入点的数量。
• 实际上，点的插入被认为是实践中最昂贵的操作。对于每个点，查找和删除 “坏三角形” 平均可能需要 O(n) 时间，从而导致总体时间复杂度为 O(n^2)。
• 然而，由于某些优化和数据结构有助于在点插入期间快速检索附近三角形，因此实际上它通常比最坏情况表现得更好。

空间复杂度

• 正如我们从这种算法中预期的那样，在最坏的情况下，Bowyer-Watson 的空间复杂度也为 O(n^2)。
• 这是因为，连接一组点数量不断增加的三角形数量可能大致与这些点的数量成正比。如果大多数或所有点都共线性，我们将有大约 O(n^2) 个三角形。
• 此外，该算法还需要空间来存储输入点和输出三角形，这增加了其空间复杂度。

Delaunay 三角剖分的优点

C++ 中的 Delaunay 三角剖分 有几个优点。Delaunay 三角剖分的一些主要优点如下。

1. 最优三角剖分： Delaunay 三角剖分 最大化最小角度，最小化所有三角形的最大外接圆半径，并生成条件良好的三角形。这一特性使其能够生成用于数值计算、网格生成和有限元分析的 Delaunay 三角剖分。
2. 几何鲁棒性： Delaunay 三角剖分能够处理各种几何配置，例如非均匀点分布、凹壳、复杂形状等。它是将点集划分为三角形同时保持几何完整性的一种鲁棒方法。
3. 一致性和规律性： Delaunay 三角剖分算法生成一致且规则的网格，使其适用于需要三角剖分表面具有均匀性和可预测性的应用。三角形的质量和边长等几何特性在整个域中得到保持，以确保这种一致性。
4. 高效的计算特性： 尽管存在理论上的复杂性，但存在高效的算法来计算 Delaunay 三角剖分，例如 Bowyer-Watson 算法和分治法。因此，通过这些算法，可以获得合理的 O(nlogn) 时间复杂度或 O(n) 空间复杂度。因此，Delaunay 三角剖分可用于大型数据集或实时应用。
5. 表面建模和数据插值： Delaunay 三角剖分广泛用于插值和表面重建。Delaunay 三角剖分允许估算点集凸包内任意位置的值，从而实现表面建模和数据插值。
6. 空间索引和最近邻查询： 通过应用 Delaunay 三角剖分可以实现高效的空间索引和最近邻查询。它有助于快速检索相邻点及其空间关系，从而支持不同的空间分析和查询操作。

Delaunay 三角剖分的缺点

C++ 中的 Delaunay 三角剖分 有几个缺点。Delaunay 三角剖分的一些主要缺点如下。

1. 计算复杂度： 对于大型数据集，Delaunay 三角剖分例程可能耗时较长。更糟糕的是，现有的算法，如 Bowyer-Watson 或分治法，其最坏情况时间复杂度为 O(n^2)，其中 n 是输入点的数量。因此，这种复杂度可能会使 Delaunay 在非常大的数据集或实时应用中不可行。
2. 内存消耗： 大多数 Delaunay 三角剖分算法通常涉及大量三角形和其他数据结构需要存储，这使得它们消耗大量内存，尤其是在处理密集点分布或复杂几何形状时。如果运行资源受限的设备不达预期或可用内存有限，这可能是一个缺点。
3. 边界处理： 大多数 Delaunay 三角剖分算法都假定点集具有凸包或定义明确的边界。在这些情况下，可能需要进行额外的预处理或后处理，以考虑点位于凸包表面区域（或其外部）的情况，从而使算法复杂化并影响其性能。
4. 非均匀点分布： 对于 非均匀分布 的点，Delaunay 三角剖分可能会生成形状不均匀的三角形，并且网格中的密度会发生变化。因此，某些区域的网格质量可能较低，需要进行后处理步骤或进一步的细化技术才能获得高质量的整体网格。
5. 对更高维度的支持有限： 尽管如此，在更高维度上将 Delaunay 三角剖分扩展到 2D 和 3D 之外是困难的。随着维度的增加，它们变得不那么有效且更复杂，这限制了它们在大型数据集和高维应用中的使用。

结论

Delaunay 三角剖分 是计算几何中的一个重要概念。它是平面上某些点的最优且良好的三角剖分，因为它提供了许多优点，包括最优性、鲁棒性、几何一致性、效率、适应性和多功能性，这使其在计算机图形学、GIS（地理信息系统）、有限元分析、网格生成、插值和表面重建等领域不可或缺。

有几种计算 Delaunay 三角剖分的算法，每种算法都有其优点和缺点。这些算法包括 Bowyer-Watson 算法、分治算法、增量算法、扫描线算法 等。然而，选择特定算法取决于输入大小或数据集大小，以及可用的计算资源、所需的计算精度和特定的应用需求。