7.5 特殊三角化

上一节: 7.1 二维三角化基础 | 7.2 二维Delaunay三角化 | 7.3 约束三角化 | 7.4 正则三角化

1. 周期性三角化 (Periodic Triangulation)

1.1 数学理论基础

周期性三角化处理定义在平坦环面 (Flat Torus) 上的点集。平坦环面是通过将平面在某个方向上周期性等同而得到的拓扑空间。

1.1.1 平坦环面定义

对于周期 $L_{x}, L_{y}$ ，平坦环面 $T^{2}$ 定义为：

$T^{2} = R^{2} /Λ$

其中 $Λ = {(k L_{x}, l L_{y}) ∣ k, l \in Z}$ 是格点。

等价关系： $(x, y) \sim (x + k L_{x}, y + l L_{y}), \forall k, l \in Z$

1.1.2 周期性Delaunay三角化

在平坦环面上，Delaunay三角化的定义需要调整：

周期副本：每个点有9个副本（3×3网格），用于处理跨越周期边界的三角形
空外接圆性质：测试时需要考虑所有副本
唯一性：在一般位置下唯一

1.1.3 覆盖空间方法

CGAL使用覆盖空间 (Covering Space) 方法：

原始域: [0, Lx) × [0, Ly)
9个副本: 3×3网格，中心为原始域
        [-Lx, 0)  [0, Lx)  [Lx, 2Lx)
        ┌─────────┬─────────┬─────────┐
[Ly,2Ly)│ 副本7   │ 副本8   │ 副本9   │
        ├─────────┼─────────┼─────────┤
[0, Ly) │ 副本4   │ 原始域  │ 副本6   │
        ├─────────┼─────────┼─────────┤
[-Ly, 0)│ 副本1   │ 副本2   │ 副本3   │
        └─────────┴─────────┴─────────┘

1.2 类架构

#include <CGAL/Periodic_2_Delaunay_triangulation_2.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_traits_2.h>
 
// 定义周期性内核
template <class K>
class Periodic_2_Delaunay_triangulation_traits_2 : public K {
public:
    typedef Periodic_2_offset_2 Offset;  // 周期偏移
    typedef std::pair<Point_2, Offset> Point;  // 带点+偏移
    
    // 将点归一化到原始域
    Point_2 construct_point(const Point_2& p, const Offset& o);
};
 
// 周期性Delaunay三角化
template <class Traits, class Tds = Default>
class Periodic_2_Delaunay_triangulation_2 {
public:
    // 设置周期域
    void set_domain(const Iso_rectangle_2& domain);
    
    // 插入点（自动归一化到原始域）
    Vertex_handle insert(const Point_2& p);
    
    // 获取周期副本信息
    Offset periodic_offset(Vertex_handle v);
    
    // 转换为非周期三角化
    void convert_to_1_sheeted_triangulation();
    void convert_to_9_sheeted_triangulation();
};

1.3 实现细节

// 周期性点定位
Face_handle locate(const Point_2& p) {
    // 1. 将点归一化到原始域
    Point_2 normalized = normalize(p);
    Offset offset = compute_offset(p);
    
    // 2. 在原始域中定位
    Face_handle f = Base::locate(normalized);
    
    // 3. 处理跨越周期边界的情况
    if (crosses_boundary(f)) {
        // 使用副本进行测试
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                Offset test_offset(dx, dy);
                // 测试副本
            }
        }
    }
    
    return f;
}
 
// 空外接圆测试（周期性版本）
bool is_delaunay(Face_handle f) {
    // 获取三角形的三个顶点（考虑偏移）
    Point_2 p0 = get_point(f->vertex(0));
    Offset o0 = periodic_offset(f->vertex(0));
    
    // 对于每个其他顶点，检查所有9个副本
    for (Vertex_handle v : all_vertices) {
        for (int dx = -1; dx <= 1; ++dx) {
            for (int dy = -1; dy <= 1; ++dy) {
                Offset test_offset(dx, dy);
                Point_2 test_point = get_point(v) + test_offset * domain_size;
                
                if (in_circumcircle(f, test_point)) {
                    return false;
                }
            }
        }
    }
    return true;
}

1.4 代码示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_2.h>
#include <CGAL/Periodic_2_Delaunay_triangulation_traits_2.h>
#include <iostream>
#include <vector>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using PK = CGAL::Periodic_2_Delaunay_triangulation_traits_2<K>;
using PDT = CGAL::Periodic_2_Delaunay_triangulation_2<PK>;
 
using Point = K::Point_2;
using Iso_rectangle = K::Iso_rectangle_2;
 
int main() {
    // 定义周期域
    Iso_rectangle domain(0, 0, 1, 1);  // [0,1] × [0,1]
    
    PDT pdt(domain);
    
    std::cout << "=== 周期性Delaunay三角化 ===" << std::endl;
    
    // 插入点
    std::vector<Point> points = {
        Point(0.1, 0.1), Point(0.9, 0.1), Point(0.5, 0.9),
        Point(0.5, 0.5), Point(0.2, 0.7), Point(0.8, 0.6)
    };
    
    pdt.insert(points.begin(), points.end());
    
    std::cout << "顶点数: " << pdt.number_of_vertices() << std::endl;
    std::cout << "面数: " << pdt.number_of_faces() << std::endl;
    
    // 检查三角化是否有效（1-sheeted）
    std::cout << "是否为1-sheeted: " 
              << (pdt.is_triangulation_in_1_sheet() ? "是" : "否") << std::endl;
    
    // 如果不是，转换为9-sheeted
    if (!pdt.is_triangulation_in_1_sheet()) {
        pdt.convert_to_9_sheeted_triangulation();
        std::cout << "转换为9-sheeted后顶点数: " 
                  << pdt.number_of_vertices() << std::endl;
    }
    
    // 遍历三角形
    std::cout << "\n=== 三角形列表 ===" << std::endl;
    for (auto fit = pdt.finite_faces_begin(); 
         fit != pdt.finite_faces_end(); ++fit) {
        std::cout << "三角形: ";
        for (int i = 0; i < 3; ++i) {
            Point p = fit->vertex(i)->point();
            std::cout << "(" << p.x() << ", " << p.y() << ") ";
        }
        std::cout << std::endl;
    }
    
    // 点定位（跨越周期边界）
    Point query(0.95, 0.95);  // 靠近右上角
    auto loc = pdt.locate(query);
    
    std::cout << "\n查询点 (0.95, 0.95) 定位结果:" << std::endl;
    if (!pdt.is_infinite(loc)) {
        for (int i = 0; i < 3; ++i) {
            Point p = loc->vertex(i)->point();
            std::cout << "  顶点 " << i << ": (" 
                      << p.x() << ", " << p.y() << ")" << std::endl;
        }
    }
    
    return 0;
}

1.5 复杂度分析

操作	复杂度	说明
insert(p)	O(log n)	周期点插入
locate(p)	O(log n)	考虑9个副本
空外接圆测试	O(1)	常数时间（9个副本）
空间	O(n)	存储偏移信息

2. 双曲三角化 (Hyperbolic Triangulation)

2.1 数学理论基础

双曲三角化在庞加莱圆盘模型 (Poincaré Disk Model) 或上半平面模型 (Upper Half-Plane Model) 中进行。

2.1.1 庞加莱圆盘模型

整个双曲平面映射到单位圆盘内部
双曲直线是垂直于边界的圆弧或直径
距离公式： $d (z_{1}, z_{2}) = arccosh (1 + \frac{2∣ z _{1} - z _{2} ∣ ^{2}}{( 1 - ∣ z _{1} ∣ ^{2} ) ( 1 - ∣ z _{2} ∣ ^{2} )})$

2.1.2 双曲Delaunay三角化

双曲Delaunay三角化满足空外接圆性质，但”圆”是双曲圆（欧氏圆，但圆心不在几何中心）。

关键性质：

双曲Delaunay三角化与欧氏Delaunay三角化在圆盘内部一致
边界需要特殊处理（理想点）

2.2 类架构

#include <CGAL/Hyperbolic_Delaunay_triangulation_2.h>
#include <CGAL/Hyperbolic_triangulation_face_base_2.h>
 
template <class Gt, class Fb = Default>
class Hyperbolic_Delaunay_triangulation_2 {
public:
    // 插入点（必须在单位圆盘内）
    Vertex_handle insert(const Point_2& p);
    
    // 双曲几何查询
    Hyperbolic_distance hyperbolic_distance(Vertex_handle v1, Vertex_handle v2);
    
    // 判断是否为理想三角化（顶点在边界上）
    bool is_ideal() const;
};

2.3 实现细节

// 双曲空外接圆测试
bool is_hyperbolic_delaunay(Face_handle f) {
    // 计算双曲外接圆（不同于欧氏外接圆）
    Circle_2 hyp_circle = hyperbolic_circumcircle(f);
    
    // 检查其他点是否在双曲圆内
    for (Vertex_handle v : all_vertices) {
        if (hyperbolic_in_circle(v->point(), hyp_circle)) {
            return false;
        }
    }
    return true;
}
 
// 双曲距离计算
double hyperbolic_distance(const Point_2& p1, const Point_2& p2) {
    double x1 = p1.x(), y1 = p1.y();
    double x2 = p2.x(), y2 = p2.y();
    
    double num = 2 * ((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    double den = (1 - x1*x1 - y1*y1) * (1 - x2*x2 - y2*y2);
    
    return std::acosh(1 + num / den);
}

2.4 代码示例

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Hyperbolic_Delaunay_triangulation_2.h>
#include <iostream>
#include <vector>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
using HDT = CGAL::Hyperbolic_Delaunay_triangulation_2<K>;
 
using Point = K::Point_2;
 
int main() {
    HDT hdt;
    
    std::cout << "=== 双曲Delaunay三角化 ===" << std::endl;
    
    // 在单位圆盘内插入点
    std::vector<Point> points = {
        Point(0.0, 0.0),      // 中心
        Point(0.5, 0.0),      // 右侧
        Point(-0.5, 0.0),     // 左侧
        Point(0.0, 0.5),      // 上侧
        Point(0.0, -0.5),     // 下侧
        Point(0.3, 0.3),      // 右上
        Point(-0.3, -0.3)     // 左下
    };
    
    for (const auto& p : points) {
        // 验证点在单位圆盘内
        if (p.x()*p.x() + p.y()*p.y() < 1.0) {
            hdt.insert(p);
        }
    }
    
    std::cout << "顶点数: " << hdt.number_of_vertices() << std::endl;
    std::cout << "面数: " << hdt.number_of_faces() << std::endl;
    
    // 遍历三角形
    std::cout << "\n=== 双曲三角形 ===" << std::endl;
    for (auto fit = hdt.finite_faces_begin(); 
         fit != hdt.finite_faces_end(); ++fit) {
        std::cout << "三角形: ";
        for (int i = 0; i < 3; ++i) {
            Point p = fit->vertex(i)->point();
            std::cout << "(" << p.x() << ", " << p.y() << ") ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

3. 阿基米德三角化 (Apollonius Graph)

3.1 数学理论基础

阿基米德图是加性加权Voronoi图 (Additively Weighted Voronoi Diagram) 的对偶图，也称为Apollonius Diagram。

3.1.1 加性加权距离

$d_{A W} (p_{i}, x) = ∥ x - p_{i} ∥ - w_{i}$

与幂距离（乘性加权）不同，加性加权使用减法。

3.1.2 Apollonius圆

给定三个加权点，存在唯一的Apollonius圆与三个圆都相切。

3.2 类架构

#include <CGAL/Apollonius_graph_2.h>
#include <CGAL/Apollonius_graph_traits_2.h>
 
template <class Gt, class Agds = Default>
class Apollonius_graph_2 {
public:
    typedef Gt::Site_2 Site;  // 加权点 (位置 + 权重)
    
    // 插入站点
    Vertex_handle insert(const Site_2& s);
    
    // 获取Apollonius边
    Segment apollonius_edge(Edge e);
    
    // 判断两个圆是否相交
    bool do_intersect(const Site_2& s1, const Site_2& s2);
};

3.3 与正则三角化的区别

特性	Regular Triangulation	Apollonius Graph
距离	幂距离	加性加权距离
对偶	幂图	Apollonius图
隐藏点	有	有（不同条件）
应用	分子表面	圆填充、网络规划

4. 比较与选择指南

4.1 各种三角化对比

三角化类型	输入	对偶图	主要应用	CGAL包
Delaunay	普通点	Voronoi	网格生成、插值	Triangulation_2
Regular	加权点	幂图	分子表面、球填充	Triangulation_2
Constrained	点+约束边	-	多边形剖分	Triangulation_2
Periodic	周期点	周期Voronoi	材料模拟	Periodic_2_triangulation_2
Hyperbolic	双曲点	双曲Voronoi	双曲几何	Hyperbolic_triangulation_2
Apollonius	加权圆	Apollonius图	圆填充	Apollonius_graph_2

4.2 选择决策树

需要处理周期边界？
├── 是 → Periodic_2_Delaunay_triangulation_2
└── 否 → 点是否有权重？
    ├── 是 → 权重类型？
    │   ├── 乘性（半径平方）→ Regular_triangulation_2
    │   └── 加性（半径）→ Apollonius_graph_2
    └── 否 → 需要约束边？
        ├── 是 → Constrained_Delaunay_triangulation_2
        └── 否 → 在双曲空间？
            ├── 是 → Hyperbolic_Delaunay_triangulation_2
            └── 否 → Delaunay_triangulation_2

5. 高级主题

5.1 动态三角化

// 支持插入和删除的完全动态三角化
template <class Triangulation>
class Dynamic_triangulation {
    // 使用历史DAG支持删除
    // 维护所有版本的三角化
};

5.2 层次三角化

// 多级分辨率三角化
class Hierarchical_triangulation {
    std::vector<Triangulation*> levels;
    // 粗到细的网格层次
};

5.3 并行三角化

// 使用TBB/OpenMP并行构建
void parallel_insert(Triangulation& tri, Iterator first, Iterator last) {
    // 分治策略
    // 局部三角化 + 合并
}

6. 总结

CGAL的二维三角化框架提供了丰富的特殊三角化类型：

周期性三角化：处理周期边界条件，适用于材料模拟和晶体结构
双曲三角化：支持非欧几何计算
阿基米德图：加性加权Voronoi图的对偶

这些特殊三角化共享统一的设计理念和接口，使得用户可以在不同几何背景下使用熟悉的API。理解这些特殊三角化的数学基础和适用场景，有助于在实际问题中选择合适的工具。

Chunibyo

Explorer

7.5 特殊三角化

7.5 特殊三角化

1. 周期性三角化 (Periodic Triangulation)

1.1 数学理论基础

1.1.1 平坦环面定义

1.1.2 周期性Delaunay三角化

1.1.3 覆盖空间方法

1.2 类架构

1.3 实现细节

1.4 代码示例

1.5 复杂度分析

2. 双曲三角化 (Hyperbolic Triangulation)

2.1 数学理论基础

2.1.1 庞加莱圆盘模型

2.1.2 双曲Delaunay三角化

2.2 类架构

2.3 实现细节

2.4 代码示例

3. 阿基米德三角化 (Apollonius Graph)

3.1 数学理论基础

3.1.1 加性加权距离

3.1.2 Apollonius圆

3.2 类架构

3.3 与正则三角化的区别

4. 比较与选择指南

4.1 各种三角化对比

4.2 选择决策树

5. 高级主题

5.1 动态三角化

5.2 层次三角化

5.3 并行三角化

6. 总结

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

7.5 特殊三角化

7.5 特殊三角化 §

1. 周期性三角化 (Periodic Triangulation) §

1.1 数学理论基础 §

1.1.1 平坦环面定义 §

1.1.2 周期性Delaunay三角化 §

1.1.3 覆盖空间方法 §

1.2 类架构 §

1.3 实现细节 §

1.4 代码示例 §

1.5 复杂度分析 §

2. 双曲三角化 (Hyperbolic Triangulation) §

2.1 数学理论基础 §

2.1.1 庞加莱圆盘模型 §

2.1.2 双曲Delaunay三角化 §

2.2 类架构 §

2.3 实现细节 §

2.4 代码示例 §

3. 阿基米德三角化 (Apollonius Graph) §

3.1 数学理论基础 §

3.1.1 加性加权距离 §

3.1.2 Apollonius圆 §

3.2 类架构 §

3.3 与正则三角化的区别 §

4. 比较与选择指南 §

4.1 各种三角化对比 §

4.2 选择决策树 §

5. 高级主题 §

5.1 动态三角化 §

5.2 层次三角化 §

5.3 并行三角化 §

6. 总结 §

Graph View

Table of Contents

Backlinks

7.5 特殊三角化

1. 周期性三角化 (Periodic Triangulation)

1.1 数学理论基础

1.1.1 平坦环面定义

1.1.2 周期性Delaunay三角化

1.1.3 覆盖空间方法

1.2 类架构

1.3 实现细节

1.4 代码示例

1.5 复杂度分析

2. 双曲三角化 (Hyperbolic Triangulation)

2.1 数学理论基础

2.1.1 庞加莱圆盘模型

2.1.2 双曲Delaunay三角化

2.2 类架构

2.3 实现细节

2.4 代码示例

3. 阿基米德三角化 (Apollonius Graph)

3.1 数学理论基础

3.1.1 加性加权距离

3.1.2 Apollonius圆

3.2 类架构

3.3 与正则三角化的区别

4. 比较与选择指南

4.1 各种三角化对比

4.2 选择决策树

5. 高级主题

5.1 动态三角化

5.2 层次三角化

5.3 并行三角化

6. 总结