3.5 组合地图（Combinatorial Map）

从半边数据结构到组合地图

如果你已经理解了HalfedgeDS，学习组合地图会更容易。

类比：从具体到抽象

HalfedgeDS 就像具体的建筑图纸（专门针对2D表面）
Combinatorial Map 就像通用的拓扑语言（可以描述任何维度）

对照表

HalfedgeDS	Combinatorial Map	几何意义
Halfedge	Dart	有向边元素
next()	β₁	绕面的下一条
opposite()	β₂	对边
vertex()	β₀	顶点关联

理解了HalfedgeDS的半边遍历，你就已经掌握了组合地图的70%！

为什么需要组合地图？

想象你正在处理一个3D打印模型：

2D表面网格只需要知道面和边（HalfedgeDS足够）
3D体网格需要知道体积单元内部的结构（需要Combinatorial Map）
高维数据（如4D时空网格）则需要更通用的表示

组合地图提供了一个统一的框架，用同一套语言描述任意维度的拓扑结构。

2D组合地图可视化

简单三角形示例

想象一个三角形ABC，它的边是如何表示的？

        A (顶点)
        /\
       /  \
  dart0↓    ↓dart2
       /      \
      /________\
    B    dart1    C

Beta关系：
- β₀(dart0) = dart at same vertex, different edge
- β₁(dart0) = dart1 (next around face)
- β₂(dart0) = dart on opposite side of edge AB

可视化遍历

假设你从dart0开始，沿着三角形的边走：

步骤1：dart0 (边AB，从A到B)

β₁(dart0) = dart1 （绕面移动到边BC）
β₂(dart0) = dart0_opp （跳到边AB的另一侧，外部面）

步骤2：dart1 (边BC，从B到C)

β₁(dart1) = dart2 （绕面移动到边CA）
β₂(dart1) = dart1_opp （跳到边BC的另一侧）

步骤3：dart2 (边CA，从C到A)

β₁(dart2) = dart0 （绕面回到边AB）
β₂(dart2) = dart2_opp （跳到边CA的另一侧）

这样，β₁操作让你绕着面转一圈，β₂操作让你跳到相邻的面。

更复杂的例子：两个三角形共享一条边

        A
        /\
       /  \
      / F1 \
     /______\
    B \      / C
       \ F2 /
        \/
        D

在这个结构中：

面F1：三角形ABC
面F2：三角形BCD
共享边：BC

Dart分配：

F1有3个darts：d0(AB), d1(BC), d2(CA)
F2有3个darts：d3(BC), d4(CD), d5(DB)

关键连接：

β₂(d1) = d3 （边BC的两侧通过β₂连接）
β₂(d3) = d1 （对合性质）

这样，当你从F1遍历到边BC时，通过β₂就能跳到F2。

渐进维度学习

2D：多边形网格（最直观）

在2D中，组合地图有3个beta函数：β₀, β₁, β₂。

几何解释：

β₀：在同一个顶点的不同边之间切换
β₁：绕着面的下一条边
β₂：跳到共享边的另一侧（对边）

示例代码：创建四边形

#include <CGAL/Combinatorial_map.h>
#include <iostream>
 
typedef CGAL::Combinatorial_map<2> CMap_2;
typedef CMap_2::Dart_descriptor Dart_descriptor;
 
int main() {
    CMap_2 cmap;
    
    // 创建四边形的8个darts（4个内部 + 4个外部）
    Dart_descriptor d[8];
    for (int i = 0; i < 8; ++i) {
        d[i] = cmap.create_dart();
    }
    
    // 设置β₁：内部面的循环 0→1→2→3→0
    cmap.link_beta(d[0], d[1], 1);
    cmap.link_beta(d[1], d[2], 1);
    cmap.link_beta(d[2], d[3], 1);
    cmap.link_beta(d[3], d[0], 1);
    
    // 设置β₂：内部和外部连接
    for (int i = 0; i < 4; ++i) {
        cmap.link_beta(d[i], d[i+4], 2);  // d[i]和d[i+4]是对边
    }
    
    // 设置β₁：外部面的循环 4→7→6→5→4（注意顺序相反）
    cmap.link_beta(d[4], d[7], 1);
    cmap.link_beta(d[7], d[6], 1);
    cmap.link_beta(d[6], d[5], 1);
    cmap.link_beta(d[5], d[4], 1);
    
    std::cout << "四边形创建完成，dart数量：" 
              << cmap.number_of_darts() << std::endl;
    
    return 0;
}

3D：多面体（扩展到体积）

在3D中，我们添加β₃来连接体积单元。

        顶点A
        /|\
       / | \
      /  |  \
     /___|___\
    顶点B  顶点C
    \    |    /
     \   |   /
      \  |  /
       \ | /
        \|/
        顶点D

四面体的结构：

4个三角形面
6条边
4个顶点
每个面有3个darts，共12个darts

3D中的Beta函数：

β₀, β₁, β₂：同2D，但在每个面内工作
β₃：跳到相邻的体积单元（通过共享面）

代码示例：遍历3D体的一个面

#include <CGAL/Combinatorial_map.h>
#include <iostream>
 
typedef CGAL::Combinatorial_map<3> CMap_3;
typedef CMap_3::Dart_descriptor Dart_descriptor;
 
void traverse_face_in_3d(const CMap_3& cmap, Dart_descriptor start) {
    std::cout << "遍历3D体中的面：" << std::endl;
    
    Dart_descriptor current = start;
    int count = 0;
    
    do {
        std::cout << "  Dart " << count++ << std::endl;
        
        // 在3D中，β₃可能指向另一个体积单元
        if (\!cmap.is_free(current, 3)) {
            std::cout << "    → 通过β₃连接到相邻体" << std::endl;
        }
        
        // β₁绕面遍历
        current = cmap.beta(current, 1);
    } while (current \!= start && count < 10);
}

nD：一般复形（抽象但强大）

推广到n维，概念已经很自然：

n维组合地图的Beta函数：

β₀：顶点关联（置换）
β₁：边方向（对合）
β₂：面对边（对合）
…
βₙ：n维单元邻接（对合）

维度对应关系：

维度	单元类型	Beta函数	轨道含义
0D	顶点	<β₀>	顶点关联的边
1D	边	<β₀,β₁>	边的两个方向
2D	面	<β₀,β₁,β₂> excluding β₂	面的边界
3D	体	<β₀,β₁,β₂,β₃> excluding β₃	体的表面
nD	n-单元	<β₀,…,βₙ> excluding βₙ	n-单元的边界

Combinatorial Map for Surface Mesh Users

快速转换指南

如果你熟悉Surface_mesh，这里是Combinatorial Map的对应概念：

Surface_mesh	Combinatorial Map	代码示例
vertex_descriptor	Dart of 0-cell orbit	`cmap.dart_descriptor(0)`
halfedge_descriptor	Dart	`cmap.dart_descriptor(i)`
face_descriptor	Dart of 2-cell orbit	`cmap.dart_descriptor(2)`
next(h)	beta(d, 1)	`cmap.beta(d, 1)`
prev(h)	beta(d, 0) then beta(d, 1)	`cmap.beta(cmap.beta(d,0),1)`
opposite(h)	beta(d, 2)	`cmap.beta(d, 2)`
target(h)	attribute<0>(beta(d,0))	`cmap.attribute<0>(cmap.beta(d,0))`

代码对比示例

Surface_mesh版本：

#include <CGAL/Surface_mesh.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
 
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Mesh>::halfedge_descriptor halfedge_descriptor;
 
void print_face_vertices(const Mesh& mesh, halfedge_descriptor h) {
    halfedge_descriptor start = h;
    do {
        vertex_descriptor v = target(h, mesh);
        std::cout << mesh.point(v) << std::endl;
        h = next(h, mesh);
    } while (h \!= start);
}

Combinatorial Map等效版本：

#include <CGAL/Combinatorial_map.h>
#include <iostream>
 
typedef CGAL::Combinatorial_map<2> CMap;
typedef CMap::Dart_descriptor Dart_descriptor;
 
void print_face_darts(const CMap& cmap, Dart_descriptor d) {
    Dart_descriptor start = d;
    do {
        // 获取顶点属性（假设有Point_3属性）
        auto vertex_attr = cmap.attribute<0>(cmap.beta(d, 0));
        std::cout << "Vertex at dart " << d << std::endl;
        
        d = cmap.beta(d, 1);  // 等同next()
    } while (d \!= start);
}

何时选择哪个？

需求	推荐选择	理由
只用2D表面网格	Surface_mesh	更快、内存效率更高
需要3D体网格	Combinatorial_map<3>	支持体积单元
需要非流形结构	Combinatorial_map	支持任意拓扑
需要动态拓扑修改	两者都可以	都支持动态操作
需要高维网格 (>3D)	Combinatorial_map	唯一选择
需要丰富的算法库	Surface_mesh	更多算法支持

性能对比

操作	Surface_mesh	Combinatorial_map<2>	备注
创建顶点	O(1)	O(1)	相同
创建面	O(1)	O(k) k=面边数	CM需要创建多个darts
遍历面	O(k)	O(k)	相同
内存占用	低	中	CM更通用但开销大
访问速度	快	中	CM有间接层

交互式学习：Dart遍历

练习1：手动跟踪遍历

给定以下组合地图，手动跟踪β₁β₂β₁路径：

        V0
       /  \
  d0  /    \ d2
     /  F0  \
    /________\
   V1    d1   V2
    \        /
 d3  \  F1  /  d5
      \    /
       \  /
        \/
        V3
          d4

问题1：从d0开始，应用β₁β₂β₁，最终到达哪个dart？

解答：

β₁(d0) = d1 （绕面F0移动）
β₂(d1) = d4 （跳到共享边V1-V2的另一侧，面F1）
β₁(d4) = d3 （绕面F1移动）

答案：d3

问题2：在面F1中，从d3开始遍历所有darts。

解答：

d3 (β₁)
β₁(d3) = d4
β₁(d4) = d5
β₁(d5) = d3 （回到起点）

路径：d3 → d4 → d5 → d3

练习2：编写遍历代码

实现一个函数，打印所有构成2-cell的darts：

#include <CGAL/Combinatorial_map.h>
#include <iostream>
#include <vector>
 
typedef CGAL::Combinatorial_map<2> CMap;
typedef CMap::Dart_descriptor Dart_descriptor;
 
// 练习：实现面遍历
void print_face_darts(const CMap& cmap, Dart_descriptor start) {
    std::cout << "面中的darts：" << std::endl;
    
    Dart_descriptor current = start;
    int count = 0;
    
    do {
        std::cout << "  Dart " << count++ << ": " << current << std::endl;
        
        // TODO: 移动到下一个dart
        current = cmap.beta(current, 1);  // 提示：使用β₁
        
    } while (current \!= start && count < 100);  // 安全限制
}
 
// 练习：实现顶点one-ring遍历
void print_vertex_one_ring(const CMap& cmap, Dart_descriptor start) {
    std::cout << "顶点的one-ring面：" << std::endl;
    
    Dart_descriptor current = start;
    int count = 0;
    
    do {
        std::cout << "  面 " << count++ << std::endl;
        
        // TODO: 绕顶点移动到相邻面
        // 提示：使用β₂∘β₁
        current = cmap.beta(cmap.beta(current, 1), 2);
        
    } while (current \!= start && count < 100);
}
 
int main() {
    CMap cmap;
    
    // 创建简单三角形
    Dart_descriptor d[6];
    for (int i = 0; i < 6; ++i) {
        d[i] = cmap.create_dart();
    }
    
    // 内部面
    cmap.link_beta(d[0], d[1], 1);
    cmap.link_beta(d[1], d[2], 1);
    cmap.link_beta(d[2], d[0], 1);
    
    // 外部面
    cmap.link_beta(d[3], d[5], 1);
    cmap.link_beta(d[5], d[4], 1);
    cmap.link_beta(d[4], d[3], 1);
    
    // 对边连接
    for (int i = 0; i < 3; ++i) {
        cmap.link_beta(d[i], d[i+3], 2);
    }
    
    // 测试遍历
    print_face_darts(cmap, d[0]);
    print_vertex_one_ring(cmap, d[0]);
    
    return 0;
}

练习3：可视化工具

使用以下工具可视化组合地图：

1. CGAL的Qt可视化器

#ifdef CGAL_USE_QT5
#include <CGAL/Combinatorial_map.h>
#include <CGAL/Qt/Basic_viewer_qt.h>
#include <QApplication>
 
typedef CGAL::Combinatorial_map<2> CMap;
 
class CombinatorialMapViewer : public CGAL::Basic_viewer_qt {
    const CMap& cmap;
    
public:
    CombinatorialMapViewer(QWidget* parent, const CMap& cm)
        : Basic_viewer_qt(parent, "Combinatorial Map Viewer"), cmap(cm) {}
    
    void draw() {
        // 绘制所有darts作为有向边
        // 为不同2-cell使用不同颜色
    }
};
 
int main(int argc, char** argv) {
    QApplication app(argc, argv);
    
    CMap cmap;
    // ... 创建组合地图 ...
    
    CombinatorialMapViewer viewer(nullptr, cmap);
    viewer.show();
    return app.exec();
}
#endif

2. 导出到Graphviz

#include <CGAL/Combinatorial_map.h>
#include <fstream>
#include <map>
 
typedef CGAL::Combinatorial_map<2> CMap;
typedef CMap::Dart_descriptor Dart_descriptor;
 
void export_to_graphviz(const CMap& cmap, const char* filename) {
    std::ofstream out(filename);
    out << "digraph CombinatorialMap {" << std::endl;
    out << "  rankdir=LR;" << std::endl;
    out << "  node [shape=box];" << std::endl;
    
    // 为每个dart创建节点
    std::map<Dart_descriptor, int> dart_ids;
    int id = 0;
    
    for (auto it = cmap.darts().begin(); it \!= cmap.darts().end(); ++it) {
        Dart_descriptor d = it;
        dart_ids[d] = id;
        out << "  dart" << id << " [label=\"Dart " << id << "\"];" << std::endl;
        id++;
    }
    
    // β₁边（红色）
    out << "  edge [color=red, label=\"β₁\"];" << std::endl;
    for (auto it = cmap.darts().begin(); it \!= cmap.darts().end(); ++it) {
        Dart_descriptor d = it;
        Dart_descriptor next = cmap.beta(d, 1);
        if (dart_ids.count(next)) {
            out << "  dart" << dart_ids[d] << " -> dart" << dart_ids[next] << ";" << std::endl;
        }
    }
    
    // β₂边（蓝色，虚线）
    out << "  edge [color=blue, style=dashed, label=\"β₂\"];" << std::endl;
    for (auto it = cmap.darts().begin(); it \!= cmap.darts().end(); ++it) {
        Dart_descriptor d = it;
        if (\!cmap.is_free(d, 2)) {
            Dart_descriptor opp = cmap.beta(d, 2);
            if (dart_ids.count(opp) && d < opp) {  // 避免重复边
                out << "  dart" << dart_ids[d] << " -> dart" << dart_ids[opp] << ";" << std::endl;
            }
        }
    }
    
    out << "}" << std::endl;
}

3. 使用Python的NetworkX

# export_cm_to_networkx.py
import networkx as nx
import matplotlib.pyplot as plt
 
def load_combinatorial_map(filename):
    """从C++导出的文件读取组合地图"""
    G = nx.DiGraph()
    
    with open(filename, 'r') as f:
        lines = f.readlines()
    
    # 解析dart和连接关系
    darts = []
    beta1_edges = []
    beta2_edges = []
    
    for line in lines:
        line = line.strip()
        if line.startswith('DART'):
            dart_id = int(line.split()[1])
            darts.append(dart_id)
            G.add_node(dart_id, type='dart')
        elif line.startswith('BETA1'):
            parts = line.split()
            beta1_edges.append((int(parts[1]), int(parts[2])))
            G.add_edge(int(parts[1]), int(parts[2]), type='beta1', color='red')
        elif line.startswith('BETA2'):
            parts = line.split()
            beta2_edges.append((int(parts[1]), int(parts[2])))
            G.add_edge(int(parts[1]), int(parts[2]), type='beta2', color='blue')
    
    return G, darts, beta1_edges, beta2_edges
 
def visualize_combinatorial_map(G, darts, beta1_edges, beta2_edges):
    """可视化组合地图"""
    pos = nx.spring_layout(G, k=2, iterations=50)
    
    plt.figure(figsize=(12, 8))
    
    # 绘制节点
    nx.draw_networkx_nodes(G, pos, nodelist=darts, 
                          node_color='lightblue', node_size=500)
    
    # 绘制β₁边（红色）
    nx.draw_networkx_edges(G, pos, edgelist=beta1_edges, 
                          edge_color='red', width=2, 
                          connectionstyle='arc3,rad=0.1',
                          arrows=True, arrowsize=20)
    
    # 绘制β₂边（蓝色，虚线）
    nx.draw_networkx_edges(G, pos, edgelist=beta2_edges, 
                          edge_color='blue', width=2, style='dashed',
                          connectionstyle='arc3,rad=-0.1',
                          arrows=True, arrowsize=20)
    
    # 标签
    labels = {d: f'Dart {d}' for d in darts}
    nx.draw_networkx_labels(G, pos, labels, font_size=10)
    
    # 图例
    from matplotlib.lines import Line2D
    legend_elements = [
        Line2D([0], [0], color='red', lw=2, label='β₁ (next)'),
        Line2D([0], [0], color='blue', lw=2, linestyle='--', label='β₂ (opposite)')
    ]
    plt.legend(handles=legend_elements, loc='upper left')
    
    plt.title('Combinatorial Map Visualization')
    plt.axis('off')
    plt.tight_layout()
    plt.savefig('combinatorial_map.png', dpi=150)
    plt.show()
 
# 主程序
if __name__ == '__main__':
    G, darts, beta1, beta2 = load_combinatorial_map('cm_export.txt')
    visualize_combinatorial_map(G, darts, beta1, beta2)

1. 理论基础

1.1 组合地图的数学定义

组合地图（Combinatorial Map）是拓扑结构的通用表示方法，通过darts和beta函数来定义n维拓扑结构。它是半边数据结构的推广，可以表示任意维度的复形。

定义 1.1（Dart）：Dart是带方向的边，类似于半边。在n维组合地图中，每个dart代表一个n维单形的一个面。

定义 1.2（Beta函数）：对于n维组合地图，定义n+1个beta函数 $β_{0}, β_{1}, \dots, β_{n}$ ，其中：

$β_{i} (d)$ 表示与dart $d$ 在第 $i$ 维相邻的dart
$β_{i}$ 是对合（involution）： $β_{i} (β_{i} (d)) = d$ ，对于 $i > 0$
$β_{0}$ 是置换（permutation）

定义 1.3（n维组合地图）：n维组合地图是一个元组 $(D, β_{0}, β_{1}, \dots, β_{n})$ ，其中：

$D$ 是dart的集合
$β_{i} : D \to D$ 满足上述约束

1.2 约束条件

组合地图必须满足以下数学约束：

约束1（对合性）：对于 $i > 0$ $β_{i} \circ β_{i} = id$

约束2（置换性）： $β_{0}$ 是一个置换 $\forall d \in D, \exists d^{'} \in D : β_{0} (d^{'}) = d$

约束3（交换性）：对于 $∣ i - j ∣ > 1$ $β_{i} \circ β_{j} = β_{j} \circ β_{i}$

约束4（维度约束）：对于2维组合地图（类似半边结构） $β_{1} \circ β_{2} \circ β_{1} = β_{2} \circ β_{1} \circ β_{2}$

1.3 维度特化

维度	表示对象	Beta函数	对应概念
0D	点	$β_{0}$	顶点
1D	线段	$β_{0}, β_{1}$	边的两个方向
2D	多边形	$β_{0}, β_{1}, β_{2}$	面、边、顶点
3D	多面体	$β_{0}, β_{1}, β_{2}, β_{3}$	体、面、边、顶点
nD	n维复形	$β_{0}, \dots, β_{n}$	n维单形

2D组合地图与半边数据结构的对应：

Dart = 半边
$β_{1}$ = next（绕面）
$β_{2}$ = opposite（对边）
$β_{0}$ = 顶点关联

2. 架构分析

2.1 Combinatorial_map类层次结构

Combinatorial_map体系
├── Combinatorial_map_base<d, Refs, Items, Alloc, Storage>
│   ├── Dart（通过Storage定义）
│   ├── beta操作
│   ├── 属性管理
│   └── 标记系统
│
├── 存储策略（Storage）
│   ├── Combinatorial_map_storage_1<d, Refs, Items, Alloc>
│   └── Combinatorial_map_storage_with_index<d, Refs, Items, Alloc>
│
├── Items（可定制项）
│   ├── Generic_map_min_items
│   └── 自定义Items
│
└── 迭代器
    ├── Dart_const_iterators
    └── Cell_const_iterators

2.2 核心类定义

namespace CGAL {
 
// 组合地图基础类
template<unsigned int d_, class Refs_, class Items_, class Alloc_, class Storage_>
class Combinatorial_map_base : public Storage_ {
public:
    static const unsigned int dimension = d_;
    static const unsigned int NB_MARKS = ...;  // 标记数量
    
    typedef Storage_ Storage;
    typedef typename Storage::Dart Dart;
    typedef typename Storage::Dart_descriptor Dart_descriptor;
    typedef typename Storage::Dart_const_descriptor Dart_const_descriptor;
    typedef typename Storage::size_type size_type;
    
    // 属性类型
    template<int i>
    struct Attribute_type : public Storage::template Attribute_type<i> {};
    
    template<int i>
    struct Attribute_descriptor : public Storage::template Attribute_descriptor<i> {};
    
    // Beta函数
    Dart_descriptor beta(Dart_descriptor dh, int i) const;
    Dart_descriptor beta(Dart_descriptor dh, std::initializer_list<int> indices) const;
    
    template<int i>
    Dart_descriptor beta(Dart_descriptor dh) const;
    
    // 检查dart是否在第i维自由
    bool is_free(Dart_descriptor dh, int i) const;
    template<int i> bool is_free(Dart_descriptor dh) const;
    
    // 链接和取消链接
    void link_beta(Dart_descriptor dh1, Dart_descriptor dh2, int i);
    void unlink_beta(Dart_descriptor dh, int i);
    
    // 创建和删除dart
    Dart_descriptor create_dart();
    void erase_dart(Dart_descriptor dh);
    
    // 标记操作
    size_type get_new_mark();
    void free_mark(size_type m);
    bool is_marked(Dart_descriptor dh, size_type m) const;
    void mark(Dart_descriptor dh, size_type m);
    void unmark(Dart_descriptor dh, size_type m);
    
    // 属性操作
    template<unsigned int i>
    Attribute_descriptor<i> create_attribute();
    
    template<unsigned int i>
    void erase_attribute(Attribute_descriptor<i> ah);
    
    // 轨道遍历
    template<unsigned int i, typename Functor>
    void foreach_dart_of_orbit(Dart_descriptor dh, Functor&& f);
    
    template<unsigned int... Beta, typename Functor>
    void foreach_dart_of_orbit(Dart_descriptor dh, Functor&& f);
};
 
// 组合地图主类
template<unsigned int d_, class Items_, class Alloc_>
class Combinatorial_map 
    : public Combinatorial_map_base<d_, 
                                     Combinatorial_map<d_, Items_, Alloc_>,
                                     Items_, Alloc_,
                                     Combinatorial_map_storage_1<d_, 
                                         Combinatorial_map<d_, Items_, Alloc_>,
                                         Items_, Alloc_>>> {
public:
    static const unsigned int dimension = d_;
    typedef Combinatorial_map<d_, Items_, Alloc_> Self;
    typedef Combinatorial_map_base<...> Base;
    
    using Base::beta;
    using Base::is_free;
    using Base::link_beta;
    using Base::unlink_beta;
    using Base::create_dart;
    using Base::erase_dart;
};
 
} // namespace CGAL

2.3 Dart结构

// Dart的内部表示
template<unsigned int d>
struct Dart {
    std::array<Dart_handle, d + 1> beta_links;  // beta链接
    Attribute_handle<0> attribute_0;  // 0维属性（顶点）
    Attribute_handle<1> attribute_1;  // 1维属性（边）
    // ... 更多属性
    
    // 标记位
    std::bitset<NB_MARKS> marks;
    
    template<int i>
    Dart_handle beta() const { return beta_links[i]; }
    
    template<int i>
    void set_beta(Dart_handle dh) { beta_links[i] = dh; }
};

3. 实现细节

3.1 Beta函数实现

// 文件: CGAL/Combinatorial_map_basic_operations.h
 
namespace CGAL {
 
// beta函数组合
template<unsigned int... Beta>
struct Beta_combination {
    template<typename CMap>
    static typename CMap::Dart_descriptor 
    run(const CMap& cmap, typename CMap::Dart_descriptor dh) {
        return cmap.template beta<Beta...>(dh);
    }
};
 
// 轨道遍历
template<unsigned int... Beta, typename CMap, typename Functor>
void foreach_dart_of_orbit(const CMap& cmap, 
                           typename CMap::Dart_descriptor dh,
                           Functor&& f) {
    // 使用BFS遍历轨道
    std::set<typename CMap::Dart_descriptor> visited;
    std::queue<typename CMap::Dart_descriptor> queue;
    queue.push(dh);
    
    while (\!queue.empty()) {
        auto current = queue.front();
        queue.pop();
        
        if (visited.count(current)) continue;
        visited.insert(current);
        
        f(current);
        
        // 沿所有beta方向遍历（除了指定的）
        // 使用模板参数包Beta...来确定遍历方向
        (void)std::initializer_list<int>{
            (foreach_dart_of_orbit_beta<Beta>(cmap, current, visited, queue), 0)...
        };
    }
}
 
// 检查dart是否自由
template<unsigned int i, typename CMap>
bool is_free(const CMap& cmap, typename CMap::Dart_descriptor dh) {
    return cmap.template beta<i>(dh) == CMap::null_dart_handle;
}
 
// 链接两个dart
template<unsigned int i, typename CMap>
void link_beta(CMap& cmap, 
               typename CMap::Dart_descriptor dh1,
               typename CMap::Dart_descriptor dh2) {
    cmap.template set_beta<i>(dh1, dh2);
    if (i > 0) {
        cmap.template set_beta<i>(dh2, dh1);
    }
}
 
} // namespace CGAL

3.2 轨道（Orbit）遍历算法

// 文件: CGAL/Combinatorial_map_operations.h
 
namespace CGAL {
 
// i-cell轨道：遍历定义i维单元的所有dart
// 例如，在2D中：0-cell=顶点, 1-cell=边, 2-cell=面
template<unsigned int i, typename CMap, typename Functor>
void foreach_dart_of_cell(const CMap& cmap,
                          typename CMap::Dart_descriptor dh,
                          Functor&& f) {
    // i-cell的轨道是除beta_i外的所有beta函数
    // 使用编译时生成的遍历序列
    foreach_dart_of_orbit_except<i>(cmap, dh, f);
}
 
// 遍历i-cell的所有属性
template<unsigned int i, typename CMap, typename Functor>
void foreach_attribute_of_cell(const CMap& cmap,
                               typename CMap::Dart_descriptor dh,
                               Functor&& f) {
    foreach_dart_of_cell<i>(cmap, dh, [&](typename CMap::Dart_descriptor d) {
        auto attr = cmap.template attribute<i>(d);
        if (attr \!= CMap::null_attribute_handle) {
            f(attr);
        }
    });
}
 
// 2D组合地图的专用遍历
template<typename CMap, typename Functor>
void foreach_dart_of_face(const CMap& cmap,
                          typename CMap::Dart_descriptor dh,
                          Functor&& f) {
    // 在2D中，面是2-cell
    // 轨道：除beta_2外的所有beta
    auto current = dh;
    do {
        f(current);
        current = cmap.template beta<1>(current);  // next
    } while (current \!= dh);
}
 
template<typename CMap, typename Functor>
void foreach_dart_of_vertex(const CMap& cmap,
                            typename CMap::Dart_descriptor dh,
                            Functor&& f) {
    // 在2D中，顶点是0-cell
    // 轨道：除beta_0外的所有beta
    auto current = dh;
    do {
        f(current);
        // vertex的one-ring: beta_2 o beta_1
        current = cmap.template beta<2>(cmap.template beta<1>(current));
    } while (current \!= dh);
}
 
template<typename CMap, typename Functor>
void foreach_dart_of_edge(const CMap& cmap,
                          typename CMap::Dart_descriptor dh,
                          Functor&& f) {
    // 在2D中，边是1-cell
    // 轨道：除beta_1外的所有beta
    f(dh);
    f(cmap.template beta<0>(dh));
    f(cmap.template beta<2>(dh));
    f(cmap.template beta<0>(cmap.template beta<2>(dh)));
}
 
} // namespace CGAL

3.3 属性系统实现

// 文件: CGAL/Combinatorial_map_storages.h
 
namespace CGAL {
 
// 组合地图存储基类
template<unsigned int d, class Refs, class Items, class Alloc>
class Combinatorial_map_storage_1 {
public:
    static const unsigned int dimension = d;
    static const unsigned int NB_MARKS = ...;
    
    typedef ... Dart;
    typedef Dart* Dart_handle;
    typedef const Dart* Dart_const_handle;
    
    // 属性容器
    template<int i>
    using Attribute_type = typename Items::template Attribute_wrapper<i, Refs>::Attribute;
    
    template<int i>
    using Attribute_handle = Attribute_type<i>*;
    
    // 属性数组
    std::tuple<std::vector<Attribute_handle<0>>,
               std::vector<Attribute_handle<1>>,
               ...> attribute_containers;
    
    // 获取属性
template<unsigned int i>
    Attribute_handle<i> attribute(Dart_handle dh) const {
        return dh->template attribute<i>();
    }
    
    // 设置属性
template<unsigned int i>
    void set_attribute(Dart_handle dh, Attribute_handle<i> ah) {
        dh->template set_attribute<i>(ah);
    }
    
    // 创建属性
template<unsigned int i>
    Attribute_handle<i> create_attribute() {
        auto ah = new Attribute_type<i>();
        std::get<i>(attribute_containers).push_back(ah);
        return ah;
    }
    
    // 删除属性
template<unsigned int i>
    void erase_attribute(Attribute_handle<i> ah) {
        delete ah;
        // 从容器中移除
    }
};
 
} // namespace CGAL

4. 使用示例

4.1 示例1：2D组合地图（三角形）

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <iostream>
 
// 2D组合地图
typedef CGAL::Combinatorial_map<2> CMap_2;
typedef CMap_2::Dart_descriptor Dart_descriptor;
 
int main() {
    CMap_2 cmap;
    
    // 创建一个三角形面
    // 需要3个darts，beta_1形成循环，beta_2指向外部
    
    // 创建3个darts
    Dart_descriptor d1 = cmap.create_dart();
    Dart_descriptor d2 = cmap.create_dart();
    Dart_descriptor d3 = cmap.create_dart();
    
    // 设置beta_1（绕面next）
    cmap.link_beta(d1, d2, 1);
    cmap.link_beta(d2, d3, 1);
    cmap.link_beta(d3, d1, 1);
    
    // 创建对边（边界darts）
    Dart_descriptor d1_opp = cmap.create_dart();
    Dart_descriptor d2_opp = cmap.create_dart();
    Dart_descriptor d3_opp = cmap.create_dart();
    
    // 设置beta_2（对边）
    cmap.link_beta(d1, d1_opp, 2);
    cmap.link_beta(d2, d2_opp, 2);
    cmap.link_beta(d3, d3_opp, 2);
    
    // 边界darts的beta_1形成另一个循环（外部面）
    cmap.link_beta(d1_opp, d3_opp, 1);
    cmap.link_beta(d3_opp, d2_opp, 1);
    cmap.link_beta(d2_opp, d1_opp, 1);
    
    std::cout << "Created 2D combinatorial map with triangle" << std::endl;
    std::cout << "Number of darts: " << cmap.number_of_darts() << std::endl;
    
    // 遍历三角形的darts（面遍历）
    std::cout << "\nDarts of the triangle face:" << std::endl;
    Dart_descriptor current = d1;
    int count = 0;
    do {
        std::cout << "  Dart " << count++ << std::endl;
        current = cmap.beta(current, 1);  // next
    } while (current \!= d1);
    
    // 验证beta_2是对合
    std::cout << "\nVerifying beta_2 is an involution:" << std::endl;
    Dart_descriptor test = cmap.beta(d1, 2);
    Dart_descriptor back = cmap.beta(test, 2);
    std::cout << "  beta_2(beta_2(d1)) == d1: " << (back == d1 ? "yes" : "no") << std::endl;
    
    return 0;
}

4.2 示例2：3D组合地图（四面体）

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <iostream>
 
// 3D组合地图
typedef CGAL::Combinatorial_map<3> CMap_3;
typedef CMap_3::Dart_descriptor Dart_descriptor;
 
int main() {
    CMap_3 cmap;
    
    // 创建一个四面体
    // 四面体有4个面，每个面是三角形
    // 每个三角形需要3个darts
    // 总共需要 4 * 3 = 12个darts（不考虑共享）
    // 实际上每个内部边被2个面共享，所以需要更少的darts
    
    // 简化的四面体构建：创建6条边，每条边2个dart
    std::vector<Dart_descriptor> darts;
    for (int i = 0; i < 12; ++i) {
        darts.push_back(cmap.create_dart());
    }
    
    // 构建4个三角形面
    // 面1: d0, d1, d2
    cmap.link_beta(darts[0], darts[1], 1);
    cmap.link_beta(darts[1], darts[2], 1);
    cmap.link_beta(darts[2], darts[0], 1);
    
    // 面2: d3, d4, d5
    cmap.link_beta(darts[3], darts[4], 1);
    cmap.link_beta(darts[4], darts[5], 1);
    cmap.link_beta(darts[5], darts[3], 1);
    
    // 面3: d6, d7, d8
    cmap.link_beta(darts[6], darts[7], 1);
    cmap.link_beta(darts[7], darts[8], 1);
    cmap.link_beta(darts[8], darts[6], 1);
    
    // 面4: d9, d10, d11
    cmap.link_beta(darts[9], darts[10], 1);
    cmap.link_beta(darts[10], darts[11], 1);
    cmap.link_beta(darts[11], darts[9], 1);
    
    // 设置beta_2（面内对边）
    // 这里简化处理，实际应该根据拓扑连接
    for (int i = 0; i < 12; i += 3) {
        cmap.link_beta(darts[i], darts[i+1], 2);
        cmap.link_beta(darts[i+1], darts[i+2], 2);
        cmap.link_beta(darts[i+2], darts[i], 2);
    }
    
    std::cout << "Created 3D combinatorial map (tetrahedron)" << std::endl;
    std::cout << "Number of darts: " << cmap.number_of_darts() << std::endl;
    
    // 遍历一个面的darts
    std::cout << "\nDarts of face 1:" << std::endl;
    Dart_descriptor current = darts[0];
    int count = 0;
    do {
        std::cout << "  Dart " << count++ << std::endl;
        current = cmap.beta(current, 1);
    } while (current \!= darts[0] && count < 10);
    
    return 0;
}

4.3 示例3：轨道遍历和属性操作

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <CGAL/Cell_const_iterators.h>
#include <iostream>
#include <vector>
 
// 定义带属性的组合地图
typedef CGAL::Combinatorial_map<2> CMap_2;
typedef CMap_2::Dart_descriptor Dart_descriptor;
 
// 顶点属性
struct Vertex_attribute {
    double x, y;
    Vertex_attribute(double x = 0, double y = 0) : x(x), y(y) {}
};
 
// 自定义Items
template<class Refs>
struct My_items {
    template<class CMap, int i>
    struct Attribute_type {
        typedef Vertex_attribute type;
    };
    
    template<class CMap>
    struct Dart_wrapper {
        typedef CGAL::Dart<2, Refs> Dart;
    };
};
 
int main() {
    CMap_2 cmap;
    
    // 创建一个四边形
    std::vector<Dart_descriptor> darts;
    for (int i = 0; i < 8; ++i) {  // 4个边界darts + 4个内部darts
        darts.push_back(cmap.create_dart());
    }
    
    // 设置beta_1形成四边形
    for (int i = 0; i < 4; ++i) {
        cmap.link_beta(darts[i], darts[(i+1) % 4], 1);
    }
    
    // 设置beta_2（对边）
    for (int i = 0; i < 4; ++i) {
        cmap.link_beta(darts[i], darts[i+4], 2);
    }
    
    // 外部面的beta_1
    for (int i = 4; i < 8; ++i) {
        cmap.link_beta(darts[i], darts[4 + (i-4+3) % 4], 1);
    }
    
    std::cout << "Created quadrilateral" << std::endl;
    
    // 使用轨道遍历
    std::cout << "\nOrbit traversal of the face:" << std::endl;
    int dart_count = 0;
    CGAL::foreach_dart_of_orbit<2>(cmap, darts[0], [&](Dart_descriptor d) {
        std::cout << "  Dart " << dart_count++ << std::endl;
    });
    
    // 标记操作
    auto mark = cmap.get_new_mark();
    std::cout << "\nMarking darts:" << std::endl;
    
    cmap.mark(darts[0], mark);
    cmap.mark(darts[2], mark);
    
    for (int i = 0; i < 4; ++i) {
        std::cout << "  Dart " << i << " marked: " 
                  << (cmap.is_marked(darts[i], mark) ? "yes" : "no") << std::endl;
    }
    
    cmap.free_mark(mark);
    
    return 0;
}

4.4 示例4：与半边数据结构的对比

#include <CGAL/Combinatorial_map.h>
#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
 
// 半边数据结构
typedef CGAL::HalfedgeDS_default<Traits> HDS;
 
// 组合地图
typedef CGAL::Combinatorial_map<2> CMap_2;
 
void compare_structures() {
    std::cout << "=== Comparison: HalfedgeDS vs Combinatorial Map ===" << std::endl;
    
    std::cout << "\nHalfedgeDS (2D):" << std::endl;
    std::cout << "  - Specialized for 2D polygonal meshes" << std::endl;
    std::cout << "  - Explicit Vertex, Halfedge, Face types" << std::endl;
    std::cout << "  - next(), prev(), opposite() operations" << std::endl;
    std::cout << "  - vertex(), face() accessors" << std::endl;
    std::cout << "  - Optimized for surface meshes" << std::endl;
    
    std::cout << "\nCombinatorial Map (nD):" << std::endl;
    std::cout << "  - General n-dimensional representation" << std::endl;
    std::cout << "  - Unified Dart type" << std::endl;
    std::cout << "  - beta_i() operations for i = 0..n" << std::endl;
    std::cout << "  - Orbit-based traversal" << std::endl;
    std::cout << "  - Supports volumes (3D) and higher dimensions" << std::endl;
    
    std::cout << "\nCorrespondence (2D):" << std::endl;
    std::cout << "  HalfedgeDS          Combinatorial Map" << std::endl;
    std::cout << "  ----------          -----------------" << std::endl;
    std::cout << "  Halfedge      <->     Dart" << std::endl;
    std::cout << "  next()        <->     beta_1()" << std::endl;
    std::cout << "  opposite()    <->     beta_2()" << std::endl;
    std::cout << "  vertex()      <->     beta_0()" << std::endl;
    std::cout << "  face()        <->     orbit of beta_1 excluding beta_2" << std::endl;
}
 
int main() {
    compare_structures();
    
    // 创建简单的结构进行比较
    std::cout << "\n=== Creating a triangle ===" << std::endl;
    
    // 使用HalfedgeDS
    std::cout << "\nUsing HalfedgeDS:" << std::endl;
    HDS hds;
    // ... 创建三角形代码 ...
    std::cout << "  Vertices: " << hds.size_of_vertices() << std::endl;
    std::cout << "  Halfedges: " << hds.size_of_halfedges() << std::endl;
    std::cout << "  Faces: " << hds.size_of_faces() << std::endl;
    
    // 使用Combinatorial Map
    std::cout << "\nUsing Combinatorial Map:" << std::endl;
    CMap_2 cmap;
    // 创建三角形的6个darts
    for (int i = 0; i < 6; ++i) {
        cmap.create_dart();
    }
    std::cout << "  Darts: " << cmap.number_of_darts() << std::endl;
    
    return 0;
}

5. 复杂度分析

5.1 时间复杂度

操作	复杂度	说明
create_dart	O(1)	动态分配
erase_dart	O(1)	标记删除
beta(d, i)	O(1)	数组访问
link_beta	O(1)	双向链接
is_free	O(1)	空指针检查
轨道遍历	O(k)	k为轨道大小
标记操作	O(1)	位操作
属性访问	O(1)	指针访问

5.2 空间复杂度

元素	空间	说明
Dart	(d+1) × sizeof(void*) + marks	beta链接 + 标记位
Attribute	sizeof(Attribute)	用户定义
标记	NB_MARKS bits per dart	位集合
总计	O(	D

5.3 与半边数据结构的对比

特性	HalfedgeDS	Combinatorial Map
维度支持	2D	nD
内存效率	高（专用）	中（通用）
灵活性	低	高
学习曲线	平缓	陡峭
适用场景	表面网格	高维复形、体网格
算法生态	丰富	较少

6. 关键文件位置

文件路径	说明
`Combinatorial_map/include/CGAL/Combinatorial_map.h`	主类定义
`Combinatorial_map/include/CGAL/Combinatorial_map_base.h`	基础功能
`Combinatorial_map/include/CGAL/Combinatorial_map_storages.h`	存储策略
`Combinatorial_map/include/CGAL/Combinatorial_map_operations.h`	遍历操作
`Combinatorial_map/include/CGAL/Combinatorial_map_basic_operations.h`	基本操作
`Combinatorial_map/include/CGAL/Dart_const_iterators.h`	Dart迭代器
`Combinatorial_map/include/CGAL/Cell_const_iterators.h`	单元迭代器
`Combinatorial_map/include/CGAL/Generic_map_min_items.h`	最小Items

7. 最佳实践

7.1 使用建议

选择合适的维度：
- 2D表面网格：考虑使用HalfedgeDS或Surface_mesh
- 3D体网格或更高维：使用Combinatorial_map

使用轨道遍历：

CGAL::foreach_dart_of_orbit<2>(cmap, dh, [&](Dart_descriptor d) {
    // 处理dart
});

合理使用标记：

auto mark = cmap.get_new_mark();
// ... 使用标记 ...
cmap.free_mark(mark);

自定义属性：

template<class Refs>
struct My_items {
    template<class CMap, int i>
    struct Attribute_type {
        typedef My_attribute type;
    };
};

7.2 常见陷阱

Beta函数索引：

// 注意：beta_0是特殊的（置换），beta_1..beta_n是对合
cmap.beta(d, 0);  // 顶点关联
cmap.beta(d, 1);  // next
cmap.beta(d, 2);  // opposite（2D）

自由dart检查：

// 检查dart是否在第i维自由
if (cmap.is_free(d, 2)) {
    // d在beta_2方向没有连接
}

轨道遍历的终止条件：

// 确保遍历会终止
int safety_count = 0;
do {
    // 处理
    if (++safety_count > max_darts) break;
} while (current \!= start);

Chunibyo

Explorer

3.5 组合地图（Combinatorial Map）

3.5 组合地图（Combinatorial Map） §

从半边数据结构到组合地图 §

类比：从具体到抽象 §

对照表 §

为什么需要组合地图？ §

2D组合地图可视化 §

简单三角形示例 §

可视化遍历 §

更复杂的例子：两个三角形共享一条边 §

渐进维度学习 §

2D：多边形网格（最直观） §

3D：多面体（扩展到体积） §

nD：一般复形（抽象但强大） §

Combinatorial Map for Surface Mesh Users §

快速转换指南 §

代码对比示例 §

何时选择哪个？ §

性能对比 §

交互式学习：Dart遍历 §

练习1：手动跟踪遍历 §

练习2：编写遍历代码 §

练习3：可视化工具 §

1. 理论基础 §

1.1 组合地图的数学定义 §

1.2 约束条件 §

1.3 维度特化 §

2. 架构分析 §

2.1 Combinatorial_map类层次结构 §

2.2 核心类定义 §

2.3 Dart结构 §

3. 实现细节 §

3.1 Beta函数实现 §

3.2 轨道（Orbit）遍历算法 §

3.3 属性系统实现 §

4. 使用示例 §

4.1 示例1：2D组合地图（三角形） §

4.2 示例2：3D组合地图（四面体） §

4.3 示例3：轨道遍历和属性操作 §

4.4 示例4：与半边数据结构的对比 §

5. 复杂度分析 §

5.1 时间复杂度 §

5.2 空间复杂度 §

5.3 与半边数据结构的对比 §

6. 关键文件位置 §

7. 最佳实践 §

7.1 使用建议 §

7.2 常见陷阱 §

Graph View

Table of Contents

Backlinks

3.5 组合地图（Combinatorial Map）

从半边数据结构到组合地图

类比：从具体到抽象

对照表

为什么需要组合地图？

2D组合地图可视化

简单三角形示例

可视化遍历

更复杂的例子：两个三角形共享一条边

渐进维度学习

2D：多边形网格（最直观）

3D：多面体（扩展到体积）

nD：一般复形（抽象但强大）

Combinatorial Map for Surface Mesh Users

快速转换指南

代码对比示例

何时选择哪个？

性能对比

交互式学习：Dart遍历

练习1：手动跟踪遍历

练习2：编写遍历代码

练习3：可视化工具

1. 理论基础

1.1 组合地图的数学定义

1.2 约束条件

1.3 维度特化

2. 架构分析

2.1 Combinatorial_map类层次结构

2.2 核心类定义

2.3 Dart结构

3. 实现细节

3.1 Beta函数实现

3.2 轨道（Orbit）遍历算法

3.3 属性系统实现

4. 使用示例

4.1 示例1：2D组合地图（三角形）

4.2 示例2：3D组合地图（四面体）

4.3 示例3：轨道遍历和属性操作

4.4 示例4：与半边数据结构的对比

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 与半边数据结构的对比

6. 关键文件位置

7. 最佳实践

7.1 使用建议

7.2 常见陷阱