8.2 三维Delaunay三角剖分 (Delaunay_triangulation_3) §

上一节: 7.2 二维Delaunay三角化 | 8.1 三维三角剖分基础 下一节: 9.1 Mesh_3三维网格生成概述

0. 直观理解：泡沫结构与晶体生长 §

0.1 生活类比：肥皂泡沫与气泡结构 §

想象你正在观察一杯碳酸饮料中的气泡，或者肥皂泡沫的结构。这些气泡的排列方式，就是三维Delaunay三角剖分的完美类比。

三维Delaunay三角剖分就像是：

• 点：气泡的中心
• 四面体：由四个气泡中心形成的立体结构
• Delaunay性质：气泡壁尽可能以120度相遇（最小化表面积）

二维类比（平面气泡）：          三维（立体气泡）：
    〇-----〇                      〇
   / \   / \                     /|\
  /   \ /   \                   / | \
 〇-----〇-----〇               〇--〇--〇
                                \ | /
                                 \|/
                                  〇

0.2 为什么需要3D Delaunay？ §

场景1：晶体结构分析

• 模拟原子在晶体中的排列
• 计算原子间的空隙（可能藏有其他分子）
• 分析材料的力学性质

场景2：医学成像

• 从CT/MRI扫描重建三维器官模型
• 计算器官体积和表面积
• 规划手术路径

场景3：计算流体力学（CFD）

• 生成飞机机翼周围的流体网格
• 模拟空气流动和湍流
• 优化机翼设计

0.3 3D翻转操作的可视化 §

在三维Delaunay三角剖分中，当插入新点或删除点时，需要使用翻转（Flip）操作来恢复Delaunay性质。

2-3翻转（2个四面体变成3个） §

翻转前（2个四面体）：              翻转后（3个四面体）：
        
        D                              D
       /|\                            /|\
      / | \                          / | \
     /  |  \                        /  |  \
    /   |   \                      /   |   \
   A----|----B                    A----+----B
    \   |   /                      \   |   /
     \  |  /                        \  |  /
      \ | /                          \ | /
       \|/                            \|/
        C                              C
        
共享面：ABC                        共享边：CD
四面体：ABCD, ABCD                 四面体：ACDE, BCDE, ABDE
（从AB看，C和D在两侧）            （从CD看，A,B,E在三侧）

3-2翻转（3个四面体变成2个） §

这是2-3翻转的逆操作：

翻转前（3个四面体共享边AB）：      翻转后（2个四面体共享面ABC）：

        C                              C
       /|\                            /|\
      / | \                          / | \
     /  |  \                        /  |  \
    D---|---E                      D---|---E
     \  |  /                        \  |  /
      \ | /                          \ | /
       \|/                            \|/
        A-----B                        A-----B
        
共享边：AB                         共享面：CDE

4-4翻转（4个四面体重新排列） §

翻转前：                          翻转后：

        A                              A
       /|\                            /|\
      / | \                          / | \
     B--|--C                        B--|--C
     |\ | /|                        |\ | /|
     | \|/ |                        | \|/ |
     D--|--E                        D--|--E
                                   
围绕边BC的4个四面体重排           围绕边DE的4个四面体

8.2.1 数学理论基础 §

Delaunay三角剖分的定义 §

三维Delaunay三角剖分是满足**空球性质（Empty Sphere Property）**的三角剖分：

对于三角剖分中的每个四面体，其外接球内部不包含任何其他输入点。

形式化定义：设 $P$ 是 ${\mathbb{R}}^3$ 中的点集，三角剖分 $DT(P)$ 是Delaunay的，当且仅当对于 $DT(P)$ 中的每个四面体 $t=(p_i,p_j,p_k,p_l)$，满足：

$\forall p\in P\setminus \{p_i,p_j,p_k,p_l\},p\notin \text{interior}(\text{circumsphere}(t))$

空球性质可视化：

四面体ABCD的外接球：

       A
      /|\
     / | \
    /  |  \
   B---|---C
    \  |  /
     \ | /
      \|/
       D

外接球（虚线表示）：
       •
      / \
     /   \
    A-----\
   /|\     \
  / | \     \
 /  |  \     \
B---|---C-----•
 \  |  /     /
  \ | /     /
   \|/     /
    D-----•

球内无其他点！

Delaunay三角剖分的存在性与唯一性 §

存在性定理：对于任意有限点集 $P\subset {\mathbb{R}}^3$，Delaunay三角剖分存在。

唯一性定理：如果点集处于一般位置（general position），即不存在5个点共球面，则Delaunay三角剖分唯一。

对于非一般位置的点集（存在共球点），Delaunay三角剖分不唯一，但Delaunay图（Delaunay graph）唯一。

对偶关系：Voronoi图 §

Delaunay三角剖分与Voronoi图互为对偶：

• Voronoi细胞：对于点 $p_i\in P$，其Voronoi细胞为 $V(p_i)=\{x\in {\mathbb{R}}^3:\Vert x-p_i\Vert \le \Vert x-p_j\Vert ,\forall p_j\in P\}$

• 对偶关系：

  • Delaunay顶点 $\leftrightarrow$ Voronoi细胞
  • Delaunay边 $\leftrightarrow$ Voronoi面
  • Delaunay三角形面 $\leftrightarrow$ Voronoi边
  • Delaunay四面体 $\leftrightarrow$ Voronoi顶点

对偶关系可视化：

Delaunay四面体：                  Voronoi对偶：

    P1                               
   /|\                              V1（Voronoi顶点）
  / | \                             |
 /  |  \                         Voronoi边
P2--|--P3                          |
 \  |  /                         V2（Voronoi顶点）
  \ | /
   \|/
    P4

四面体的外接球中心 = Voronoi顶点

最优性质 §

Delaunay三角剖分具有多个最优性质：

1. 最大化最小角：在二维中，Delaunay三角剖分最大化最小角。三维中没有直接对应，但相关。

2. 最近邻图：Delaunay三角剖分包含欧几里得最小生成树（EMST）作为子图。

3. 空球性质：保证局部最优性，避免”扁平”四面体。

四面体质量指标 §

在三维网格生成中，四面体质量至关重要。常用质量指标：

1. 半径-边比（Radius-Edge Ratio） §

$\rho =\frac{R}{L_{min}}$

其中 $R$ 是外接球半径，$L_{min}$ 是最短边长。

质量可视化：

优质四面体：              劣质四面体（扁平）：
    
    A                      A
   /|\                    /|
  / | \                  / |
 /  |  \                /  |
B---|---C              B---|---C
 \  |  /                \  |  /
  \ | /                  \ | /
   \|/                    \|/
    D                      D
    
ρ ≈ 1.0                  ρ >> 1.0
（接近正四面体）          （接近共面）

2. 纵横比（Aspect Ratio） §

$\alpha =\frac{R}{r_{in}}$

其中 $r_{in}$ 是内切球半径。

3. 二面角（Dihedral Angle） §

四面体两个面之间的夹角，范围 $(0,\pi )$。过小的二面角会导致数值不稳定。

二面角示意：

面ABC和面ABD之间的二面角：

       C
      /
     /
    / 二面角θ
   A--------B
    \       /
     \     /
      \   /
       \ /
        D
        
优质四面体：最小二面角 > 15°
劣质四面体：最小二面角 < 1°（接近0的"刀片"四面体）

退化情况处理 §

当点集不满足一般位置假设时：

• 共球点（Cospherical points）：多个点位于同一球面上
• 共面点（Coplanar points）：多个点位于同一平面上

CGAL使用**符号扰动（Symbolic Perturbation）**技术处理退化情况，确保结果的一致性和唯一性。

8.2.2 架构分析 §

类继承层次 §

Triangulation_3<GT, Tds>
└── Delaunay_triangulation_3<GT, Tds>
    ├── Regular_triangulation_3（加权点推广）
    └── Periodic_3_Delaunay_triangulation_3（周期性）

模板参数 §

template <class GT, class Tds = Default>
class Delaunay_triangulation_3 : public Triangulation_3<GT, Tds>

• GT（Geometric Traits）：几何特征类，必须提供Delaunay所需的谓词
  • Side_of_oriented_sphere_3：判断点与有向球面的关系
  • Compare_distance_3：距离比较
• Tds（Triangulation Data Structure）：数据结构，默认使用 Triangulation_data_structure_3

核心谓词：Side_of_oriented_sphere §

这是Delaunay三角剖分的关键谓词：

// 判断点 t 相对于 (p, q, r, s) 的有向外接球的位置
Oriented_side side_of_oriented_sphere(p, q, r, s, t);
 
// 返回值：
// ON_POSITIVE_SIDE: t 在球外（满足Delaunay性质）
// ON_NEGATIVE_SIDE: t 在球内（违反Delaunay性质）
// ON_ORIENTED_BOUNDARY: t 在球面上（退化情况）

该谓词通过计算5×5行列式实现：

p_x & p_y & p_z & p_x^2+p_y^2+p_z^2 & 1 \\ q_x & q_y & q_z & q_x^2+q_y^2+q_z^2 & 1 \\ r_x & r_y & r_z & r_x^2+r_y^2+r_z^2 & 1 \\ s_x & s_y & s_z & s_x^2+s_y^2+s_z^2 & 1 \\ t_x & t_y & t_z & t_x^2+t_y^2+t_z^2 & 1 \end{pmatrix}$$ ## 8.2.3 实现细节 ### 增量插入算法 CGAL采用**增量算法（Incremental Algorithm）**构建Delaunay三角剖分： ```cpp // 伪代码：插入点p void insert(Point p) { // 1. 定位包含p的胞腔 Cell_handle c = locate(p); // 2. 找到冲突区域（外接球包含p的所有胞腔） std::vector<Cell_handle> conflict_cells; find_conflict_zone(p, c, conflict_cells); // 3. 提取冲突区域的边界（星形多面体） std::vector<Facet> boundary_facets; extract_boundary(conflict_cells, boundary_facets); // 4. 删除冲突胞腔 for (Cell_handle cell : conflict_cells) { delete_cell(cell); } // 5. 将p与边界连接，创建新胞腔 Vertex_handle v = create_vertex(p); for (Facet f : boundary_facets) { create_cell(v, f.first->vertex((f.second+1)%4), f.first->vertex((f.second+2)%4), f.first->vertex((f.second+3)%4)); } } ``` **冲突区域可视化**： ``` 插入点P前的三角剖分： 识别冲突区域： A A /|\ /|\ / | \ / | \ / | \ / | \ B---|---C B---P---C \ | / \ | / \ | / \ | / \|/ \|/ D D 冲突区域：外接球包含P的所有四面体 边界：星形多面体表面 ``` ### 翻转（Flip）操作详解 当插入或删除点导致Delaunay性质被破坏时，使用翻转恢复： #### 2-3翻转 将两个相邻四面体的共享面翻转，生成三个四面体： ``` 翻转前（2个四面体）： 翻转后（3个四面体）： D D /|\ /|\ / | \ / | \ / | \ / | \ / | \ / | \ A----|----B A----+----B \ | / \ | / \ | / \ | / \ | / \ | / \|/ \|/ C C 共享面：ABC 共享边：CD 四面体：ABCD, ABCD 四面体：ACDE, BCDE, ABDE （从AB看，C和D在两侧） （从CD看，A,B,E在三侧） ``` **2-3翻转条件**： - 两个四面体共享一个面 - 四个顶点不共面 - 翻转后满足Delaunay性质 #### 3-2翻转 三个四面体围绕一条边，翻转后变为两个四面体（2-3的逆操作）。 ``` 翻转前（3个四面体共享边AB）： 翻转后（2个四面体共享面ABC）： C C /|\ /|\ / | \ / | \ / | \ / | \ D---|---E D---|---E \ | / \ | / \ | / \ | / \|/ \|/ A-----B A-----B 共享边：AB 共享面：CDE ``` #### 4-4翻转 四个四面体围绕一条边，翻转后重新排列。 ``` 翻转前： 翻转后： A A /|\ /|\ / | \ / | \ B--|--C B--|--C |\ | /| |\ | /| | \|/ | | \|/ | D--|--E D--|--E 围绕边BC的4个四面体重排 围绕边DE的4个四面体 ``` ### 冲突区域检测 ```cpp // BFS搜索冲突区域 void find_conflict_zone(Point p, Cell_handle start, std::vector<Cell_handle>& conflict_cells) { std::queue<Cell_handle> queue; std::set<Cell_handle> visited; queue.push(start); visited.insert(start); while (\!queue.empty()) { Cell_handle c = queue.front(); queue.pop(); // 检查外接球是否包含p if (side_of_oriented_sphere(c, p) == ON_NEGATIVE_SIDE) { conflict_cells.push_back(c); // 检查邻居 for (int i = 0; i < 4; i++) { Cell_handle neighbor = c->neighbor(i); if (visited.find(neighbor) == visited.end()) { visited.insert(neighbor); queue.push(neighbor); } } } } } ``` ### 顶点删除 顶点删除比插入更复杂： 1. 删除与顶点关联的所有胞腔，形成星形空腔 2. 对空腔边界进行重新三角剖分 3. 确保新三角剖分满足Delaunay性质 CGAL使用**多面体三角剖分算法**处理空腔重新填充。 ``` 顶点删除过程： 步骤1: 删除顶点V及其关联四面体 A A /|\ /| / | \ / | / V \ / | B---|---C B---|---C \ | / \ | / \ | / \ | / \|/ \|/ D D 步骤2: 形成星形空腔（凸包） A / \ / \ / \ B-------C \ / \ / \ / D 步骤3: 重新三角剖分空腔 A /|\ / | \ / | \ B---|---C \ | / \ | / \|/ D ``` ## 8.2.4 代码示例 ### 基本Delaunay三角剖分 ```cpp #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_3.h> #include <CGAL/point_generators_3.h> #include <vector> #include <iostream> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Delaunay_triangulation_3<K> Delaunay; typedef K::Point_3 Point; typedef Delaunay::Vertex_handle Vertex_handle; typedef Delaunay::Cell_handle Cell_handle; typedef Delaunay::Facet Facet; typedef Delaunay::Edge Edge; int main() { Delaunay dt; // 生成随机点 CGAL::Random_points_in_cube_3<Point> generator(1.0); std::vector<Point> points; for (int i = 0; i < 1000; i++) { points.push_back(*generator++); } // 构建Delaunay三角剖分 dt.insert(points.begin(), points.end()); std::cout << "顶点数: " << dt.number_of_vertices() << std::endl; std::cout << "胞腔数: " << dt.number_of_finite_cells() << std::endl; // 验证Delaunay性质 bool is_valid = dt.is_valid(); std::cout << "三角剖分有效: " << (is_valid ? "是" : "否") << std::endl; return 0; } ``` ### 四面体质量分析 ```cpp #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_3.h> #include <iostream> #include <vector> #include <algorithm> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Delaunay_triangulation_3<K> Delaunay; typedef K::Point_3 Point; typedef K::FT FT; // 计算四面体的外接球半径 FT circumradius(const Point& a, const Point& b, const Point& c, const Point& d) { // 使用CGAL的函数计算外接球 K::Tetrahedron_3 tet(a, b, c, d); return tet.circumcenter().second; // 返回半径 } // 计算四面体的最短边 FT min_edge_length(const Point& a, const Point& b, const Point& c, const Point& d) { std::vector<FT> lengths; lengths.push_back(CGAL::squared_distance(a, b)); lengths.push_back(CGAL::squared_distance(a, c)); lengths.push_back(CGAL::squared_distance(a, d)); lengths.push_back(CGAL::squared_distance(b, c)); lengths.push_back(CGAL::squared_distance(b, d)); lengths.push_back(CGAL::squared_distance(c, d)); return std::sqrt(*std::min_element(lengths.begin(), lengths.end())); } // 计算半径-边比 FT radius_edge_ratio(const Point& a, const Point& b, const Point& c, const Point& d) { FT R = circumradius(a, b, c, d); FT L = min_edge_length(a, b, c, d); return R / L; } int main() { Delaunay dt; // 生成随机点 CGAL::Random_points_in_sphere_3<Point> generator(1.0); std::vector<Point> points; for (int i = 0; i < 500; i++) { points.push_back(*generator++); } dt.insert(points.begin(), points.end()); // 分析四面体质量 std::vector<FT> ratios; for (auto cit = dt.finite_cells_begin(); cit \!= dt.finite_cells_end(); ++cit) { Point a = cit->vertex(0)->point(); Point b = cit->vertex(1)->point(); Point c = cit->vertex(2)->point(); Point d = cit->vertex(3)->point(); FT ratio = radius_edge_ratio(a, b, c, d); ratios.push_back(ratio); } // 统计质量分布 std::sort(ratios.begin(), ratios.end()); std::cout << "=== 四面体质量分析 ===" << std::endl; std::cout << "四面体总数: " << ratios.size() << std::endl; std::cout << "最小半径-边比: " << ratios.front() << std::endl; std::cout << "最大半径-边比: " << ratios.back() << std::endl; std::cout << "中位数半径-边比: " << ratios[ratios.size()/2] << std::endl; // 统计优质四面体（半径-边比 < 2.0） int good_count = std::count_if(ratios.begin(), ratios.end(), [](FT r) { return r < 2.0; }); std::cout << "优质四面体比例: " << (100.0 * good_count / ratios.size()) << "%" << std::endl; return 0; } ``` ### 最近邻查询 ```cpp #include <CGAL/Search_traits_3.h> #include <CGAL/Orthogonal_k_neighbor_search.h> void nearest_neighbor_query(Delaunay& dt, const Point& query) { // 使用Delaunay进行最近邻查询 Vertex_handle v = dt.nearest_vertex(query); std::cout << "最近邻点: (" << v->point().x() << ", " << v->point().y() << ", " << v->point().z() << ")" << std::endl; // 计算距离 double dist = CGAL::squared_distance(query, v->point()); std::cout << "平方距离: " << dist << std::endl; } ``` ### 范围查询 ```cpp #include <CGAL/bounding_box.h> void range_query(Delaunay& dt, const Point& center, double radius) { // 使用包围盒进行粗略过滤 K::Sphere_3 sphere(center, radius * radius); std::vector<Vertex_handle> results; // 遍历所有顶点进行精确测试 for (auto vit = dt.finite_vertices_begin(); vit \!= dt.finite_vertices_end(); ++vit) { if (sphere.has_on_bounded_side(vit->point())) { results.push_back(vit); } } std::cout << "范围内点数: " << results.size() << std::endl; } ``` ### Voronoi图计算 ```cpp void compute_voronoi_cell(Delaunay& dt, Vertex_handle v) { // 遍历顶点的入射胞腔 std::vector<Point> voronoi_vertices; Delaunay::Cell_circulator cc = dt.incident_cells(v); Delaunay::Cell_circulator done(cc); do { if (\!dt.is_infinite(cc)) { // 计算外接球中心（Voronoi顶点） Point circumcenter = dt.dual(cc); voronoi_vertices.push_back(circumcenter); } ++cc; } while (cc \!= done); std::cout << "Voronoi细胞顶点数: " << voronoi_vertices.size() << std::endl; } // 获取对偶边（Voronoi边） void voronoi_edges(Delaunay& dt) { for (auto eit = dt.finite_edges_begin(); eit \!= dt.finite_edges_end(); ++eit) { // 边的对偶是Voronoi面 CGAL::Object dual = dt.dual(eit); // dual可能是射线、线段或点 K::Ray_3 ray; K::Segment_3 segment; Point point; if (CGAL::assign(ray, dual)) { // 无限Voronoi边 } else if (CGAL::assign(segment, dual)) { // 有限Voronoi边 } } } ``` ### 带约束的Delaunay三角剖分 ```cpp #include <CGAL/Delaunay_triangulation_cell_base_3.h> #include <CGAL/Triangulation_vertex_base_with_info_3.h> // 定义带信息的类型 typedef CGAL::Triangulation_vertex_base_with_info_3<int, K> Vb; typedef CGAL::Delaunay_triangulation_cell_base_3<K> Cb; typedef CGAL::Triangulation_data_structure_3<Vb, Cb> Tds; typedef CGAL::Delaunay_triangulation_3<K, Tds> Delaunay_with_info; void constrained_example() { Delaunay_with_info dt; // 插入带ID的点 auto v0 = dt.insert(Point(0, 0, 0)); v0->info() = 0; auto v1 = dt.insert(Point(1, 0, 0)); v1->info() = 1; // 遍历并访问信息 for (auto vit = dt.finite_vertices_begin(); vit \!= dt.finite_vertices_end(); ++vit) { std::cout << "顶点 " << vit->info() << ": (" << vit->point().x() << ", " << vit->point().y() << ", " << vit->point().z() << ")" << std::endl; } } ``` ### 实际应用：点云表面重建 ```cpp #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Delaunay_triangulation_3.h> #include <CGAL/point_generators_3.h> #include <iostream> #include <fstream> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Delaunay_triangulation_3<K> Delaunay; typedef K::Point_3 Point; // 从点云重建表面（简化版Alpha Shape） void surface_reconstruction(const std::vector<Point>& points) { Delaunay dt; dt.insert(points.begin(), points.end()); std::cout << "Delaunay三角剖分完成:" << std::endl; std::cout << "顶点数: " << dt.number_of_vertices() << std::endl; std::cout << "四面体数: " << dt.number_of_finite_cells() << std::endl; // 提取表面三角形（无邻接四面体的面） int surface_triangles = 0; for (auto fit = dt.finite_facets_begin(); fit \!= dt.finite_facets_end(); ++fit) { // 检查是否为表面面片（一侧为无限胞腔） if (dt.is_infinite(fit->first->neighbor(fit->second))) { ++surface_triangles; } } std::cout << "表面三角形数: " << surface_triangles << std::endl; // 导出到PLY格式 std::ofstream ply_file("surface.ply"); ply_file << "ply\n"; ply_file << "format ascii 1.0\n"; ply_file << "element vertex " << dt.number_of_vertices() << "\n"; ply_file << "property float x\n"; ply_file << "property float y\n"; ply_file << "property float z\n"; ply_file << "element face " << surface_triangles << "\n"; ply_file << "property list uchar int vertex_indices\n"; ply_file << "end_header\n"; // 写入顶点 std::map<Delaunay::Vertex_handle, int> vertex_indices; int idx = 0; for (auto vit = dt.finite_vertices_begin(); vit \!= dt.finite_vertices_end(); ++vit) { Point p = vit->point(); ply_file << p.x() << " " << p.y() << " " << p.z() << "\n"; vertex_indices[vit] = idx++; } // 写入表面面片 for (auto fit = dt.finite_facets_begin(); fit \!= dt.finite_facets_end(); ++fit) { if (dt.is_infinite(fit->first->neighbor(fit->second))) { ply_file << "3 "; for (int i = 0; i < 3; ++i) { ply_file << vertex_indices[fit->first->vertex((fit->second+i+1)%4)] << " "; } ply_file << "\n"; } } ply_file.close(); std::cout << "表面模型已保存到 surface.ply" << std::endl; } int main() { // 生成球面上的点 std::vector<Point> points; CGAL::Random_points_on_sphere_3<Point> generator(1.0); for (int i = 0; i < 1000; ++i) { points.push_back(*generator++); } surface_reconstruction(points); return 0; } ``` ## 8.2.5 复杂度分析 ### 时间复杂度 | 操作 | 平均复杂度 | 最坏复杂度 | 说明 | |------|-----------|-----------|------| | 构造（n个点） | $O(n \log n)$ | $O(n^2)$ | 随机化增量算法 | | 插入单个点 | $O(\log n)$ | $O(n)$ | 期望复杂度 | | 删除顶点 | $O(d \log d)$ | $O(n)$ | d为顶点度数 | | 最近邻查询 | $O(\log n)$ | $O(n)$ | 利用Delaunay性质 | | 点定位 | $O(\log n)$ | $O(n)$ | 分层结构 | | Voronoi顶点计算 | $O(1)$ | $O(1)$ | 外接球中心 | ### 空间复杂度 - **顶点存储**：$O(n)$ - **胞腔存储**：$O(m)$，其中 $m$ 为四面体数 对于三维点集，Delaunay三角剖分的胞腔数满足： $$m \leq 2n - 4 - k$$ 其中 $k$ 为凸包上的顶点数。因此空间复杂度为 $O(n)$。 ### 组合复杂度 三维Delaunay三角剖分的组合复杂度： - 边数：$O(n)$ - 面数：$O(n)$ - 胞腔数：$O(n)$ 这与二维情况不同，二维Delaunay三角剖分有 $O(n)$ 个三角形。 ## 8.2.6 应用 ### 1. 网格生成 Delaunay三角剖分是**Delaunay细化（Delaunay Refinement）**算法的基础，用于生成高质量的四面体网格。 **应用场景**： - 有限元分析（FEM） - 计算流体力学（CFD） - 生物医学建模 ### 2. 表面重建 通过Delaunay三角剖分和 $\alpha$-形状（Alpha Shapes）可以从点云重建表面。 **应用场景**： - 三维扫描数据处理 - 医学图像可视化 - 文物保护数字化 ### 3. 最近邻搜索 Delaunay三角剖分支持高效的最近邻和范围查询。 **应用场景**： - 分子动力学模拟 - 粒子系统模拟 - 机器学习中的k近邻算法 ### 4. 有限元分析 高质量的Delaunay网格是有限元模拟的基础。 **关键要求**： - 避免扁平四面体 - 控制半径-边比 - 优化二面角分布 ### 5. 分子建模 Voronoi图用于计算分子表面积和体积。 **应用场景**： - 药物分子设计 - 蛋白质结构分析 - 材料科学模拟 ## 8.2.7 与其他组件的关系 ``` Delaunay_triangulation_3 ├── 继承自 │ └── Triangulation_3 │ ├── 特化为 │ ├── Regular_triangulation_3（加权Delaunay） │ └── Periodic_3_Delaunay_triangulation_3（周期性） │ ├── 用于 │ ├── Mesh_3（网格生成） │ ├── Alpha_shapes_3（Alpha形状） │ └── Apollonius_graph_2（阿波罗尼斯图） │ └── 相关算法 ├── Voronoi图（对偶） └── Natural_neighbor_coordinates（自然邻坐标） ```