相关章节: CGAL的STL扩展 | 循环迭代器 | 属性映射 | 组合地图 | 曲面网格

3.4 半边数据结构（HalfedgeDS）

1. 理论基础

1.1 半边数据结构的数学定义

半边数据结构（Halfedge Data Structure）是计算几何中表示多边形网格的一种高效拓扑数据结构。其核心思想是将每条边分解为两条方向相反的半边（Halfedge）。

定义 1.1（半边）：半边是一个有向边，定义为有序对 $(v_{so u rce}, v_{t a r g e t})$ ，其中 $v_{so u rce}$ 是源顶点， $v_{t a r g e t}$ 是目标顶点。

定义 1.2（对边）：对于半边 $h = (v_{s}, v_{t})$ ，其对边 $\overset{ˉ}{h} = (v_{t}, v_{s})$ 满足：

$opposite (h) = \overset{ˉ}{h}$
$opposite (\overset{ˉ}{h}) = h$
$opposite (opposite (h)) = h$

定义 1.3（面）：面是由半边组成的闭合环路，满足：

对于面 $f$ 的边界上的半边 $h_{i}$ ，有 $next (h_{i}) = h_{i + 1}$
对于最后一个半边 $h_{n}$ ，有 $next (h_{n}) = h_{0}$

1.2 连接关系的数学表示

半边数据结构通过以下连接关系定义拓扑：

关系	数学定义	说明
`next(h)`	绕面的下一条半边	逆时针方向
`prev(h)`	绕面的上一条半边	逆时针方向
`opposite(h)`	对边	反向半边
`vertex(h)`	半边指向的顶点	$h$ 的目标顶点
`face(h)`	半边所属的面	左侧面

定理 1.1（拓扑完备性）：给定任意半边 $h$ ，可以通过以下操作访问所有关联元素：

顶点： $vertex (h)$
相邻面： $face (opposite (h))$
相邻顶点（one-ring）： $vertex (next (opposite (h)))$

1.3 欧拉公式验证

对于闭合的流形网格，半边数据结构满足欧拉公式：

$V - E + F = 2 - 2 g$

其中：

$V$ = 顶点数
$E$ = 边数（半边数 / 2）
$F$ = 面数
$g$ = 亏格（genus，洞的个数）

在半边数据结构中：

半边数 $H = 2 E$
每个面有 $k$ 条半边，总半边数 $H = \sum_{f \in F} k_{f}$

2. 架构分析

2.1 HalfedgeDS类层次结构

HalfedgeDS概念体系
├── HalfedgeDS（概念）
│   ├── Vertex
│   ├── Halfedge
│   └── Face
│
├── 具体实现
│   ├── HalfedgeDS_default<Traits, Items, Alloc>
│   │   └── HalfedgeDS_list<Traits, Items, Alloc>
│   ├── HalfedgeDS_vector<Traits, Items, Alloc>
│   └── HalfedgeDS_list_types<Traits, Items, Alloc>
│
├── Items（可定制项）
│   ├── HalfedgeDS_items_2（默认）
│   ├── HalfedgeDS_min_items
│   └── 自定义Items
│
└── 基类
    ├── HalfedgeDS_vertex_base<Refs>
    ├── HalfedgeDS_halfedge_base<Refs>
    └── HalfedgeDS_face_base<Refs>

2.2 内存布局

// 半边结构内存布局
struct Halfedge {
    Halfedge_handle next;       // 下一条半边（绕面）
    Halfedge_handle opposite;   // 对边
    Halfedge_handle prev;       // 上一条半边（可选）
    Vertex_handle vertex;       // 指向的顶点
    Face_handle face;           // 所属的面
};
 
// 顶点结构内存布局
struct Vertex {
    Halfedge_handle halfedge;   // 一条 outgoing 半边
    Point point;                // 几何位置
    // 其他属性...
};
 
// 面结构内存布局
struct Face {
    Halfedge_handle halfedge;   // 边界上的一条半边
    // 其他属性...
};

2.3 句柄（Handle）系统

CGAL使用句柄而非原始指针来引用元素：

template<typename Index>
class Handle {
    Index idx;  // 内部索引
public:
    explicit Handle(Index i) : idx(i) {}
    Index idx() const { return idx; }
    bool is_valid() const { return idx != -1; }
    
    // 比较操作
    bool operator==(const Handle& h) const { return idx == h.idx; }
    bool operator!=(const Handle& h) const { return idx != h.idx; }
    bool operator<(const Handle& h) const { return idx < h.idx; }
};

句柄类型：

Vertex_handle / Vertex_const_handle
Halfedge_handle / Halfedge_const_handle
Face_handle / Face_const_handle

3. 实现细节

3.1 HalfedgeDS_list实现

// 文件: CGAL/HalfedgeDS_list.h
 
namespace CGAL {
 
template<class Traits_, class HalfedgeDSItems, class Alloc>
class HalfedgeDS_list_types {
public:
    typedef Traits_ Traits;
    typedef HalfedgeDSItems Items;
    typedef Alloc Allocator;
    
    // 使用Items包装器定义具体类型
    typedef typename Items::template Vertex_wrapper<Self, Traits> Vertex_wrapper;
    typedef typename Items::template Halfedge_wrapper<Self, Traits> Halfedge_wrapper;
    typedef typename Items::template Face_wrapper<Self, Traits> Face_wrapper;
    
    // 定义具体类型
    typedef typename Vertex_wrapper::Vertex Vertex_base;
    typedef HalfedgeDS_in_place_list_vertex<Vertex_base> Vertex;
    typedef typename Halfedge_wrapper::Halfedge Halfedge_base;
    typedef HalfedgeDS_in_place_list_halfedge<Halfedge_base> Halfedge;
    typedef typename Face_wrapper::Face Face_base;
    typedef HalfedgeDS_in_place_list_face<Face_base> Face;
    
    // 定义列表类型
    typedef In_place_list<Vertex, false, Vertex_allocator> Vertex_list;
    typedef In_place_list<Halfedge, false, Halfedge_allocator> Halfedge_list;
    typedef In_place_list<Face, false, Face_allocator> Face_list;
    
    // 定义句柄类型
    typedef typename Vertex_list::iterator Vertex_handle;
    typedef typename Vertex_list::const_iterator Vertex_const_handle;
    typedef typename Halfedge_list::iterator Halfedge_handle;
    typedef typename Halfedge_list::const_iterator Halfedge_const_handle;
    typedef typename Face_list::iterator Face_handle;
    typedef typename Face_list::const_iterator Face_const_handle;
};
 
template<class Traits_, class HalfedgeDSItems, class Alloc>
class HalfedgeDS_list : public HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> {
public:
    typedef HalfedgeDS_list<Traits_, HalfedgeDSItems, Alloc> Self;
    typedef HalfedgeDS_list_types<Traits_, HalfedgeDSItems, Alloc> Types;
    
    typedef typename Types::Vertex Vertex;
    typedef typename Types::Halfedge Halfedge;
    typedef typename Types::Face Face;
    
    typedef typename Types::Vertex_handle Vertex_handle;
    typedef typename Types::Halfedge_handle Halfedge_handle;
    typedef typename Types::Face_handle Face_handle;
    
    typedef Iterator_range<Prevent_deref<Vertex_iterator>> Vertex_handles;
    typedef Iterator_range<Prevent_deref<Halfedge_iterator>> Halfedge_handles;
    typedef Iterator_range<Prevent_deref<Face_iterator>> Face_handles;
    
    // 支持的特性标签
    typedef Tag_true Supports_removal;
    typedef typename Vertex::Supports_vertex_halfedge Supports_vertex_halfedge;
    typedef typename Halfedge::Supports_halfedge_prev Supports_halfedge_prev;
    typedef typename Halfedge::Supports_halfedge_vertex Supports_halfedge_vertex;
    typedef typename Halfedge::Supports_halfedge_face Supports_halfedge_face;
    typedef typename Face::Supports_face_halfedge Supports_face_halfedge;
 
private:
    Vertex_allocator vertex_allocator;
    Edge_allocator edge_allocator;  // 分配半边对
    Face_allocator face_allocator;
    
    Vertex_list vertices;
    Halfedge_list halfedges;
    Face_list faces;
    
    size_type nb_border_halfedges;
    size_type nb_border_edges;
    Halfedge_iterator border_halfedges;
 
public:
    // 构造函数
    HalfedgeDS_list() : nb_border_halfedges(0), nb_border_edges(0) {}
    
    HalfedgeDS_list(size_type v, size_type h, size_type f)
        : nb_border_halfedges(0), nb_border_edges(0) {}
    
    // 访问函数
    size_type size_of_vertices() const { return vertices.size(); }
    size_type size_of_halfedges() const { return halfedges.size(); }
    size_type size_of_faces() const { return faces.size(); }
    
    // 迭代器
    Vertex_iterator vertices_begin() { return vertices.begin(); }
    Vertex_iterator vertices_end() { return vertices.end(); }
    Vertex_handles vertex_handles() {
        return make_prevent_deref_range(vertices_begin(), vertices_end());
    }
    
    Halfedge_iterator halfedges_begin() { return halfedges.begin(); }
    Halfedge_iterator halfedges_end() { return halfedges.end(); }
    Halfedge_handles halfedge_handles() {
        return make_prevent_deref_range(halfedges_begin(), halfedges_end());
    }
    
    Face_iterator faces_begin() { return faces.begin(); }
    Face_iterator faces_end() { return faces.end(); }
    Face_handles face_handles() {
        return make_prevent_deref_range(faces_begin(), faces_end());
    }
    
    // 插入操作
    Vertex_handle vertices_push_back(const Vertex& v) {
        vertices.push_back(*get_vertex_node(v));
        Vertex_handle vh = vertices.end();
        return --vh;
    }
    
    // 半边总是成对分配
    std::pair<Halfedge_handle, Halfedge_handle> edges_push_back() {
        Halfedge h, g;  // g是h的对边
        Halfedge* h2 = get_edge_node(h, g);
        Halfedge* g2 = h2 + 1;
        halfedges.push_back(*h2);
        halfedges.push_back(*g2);
        Halfedge_handle hh = halfedges.end();
        --hh; --hh;
        Halfedge_handle gg = halfedges.end();
        --gg;
        return std::make_pair(hh, gg);
    }
    
    Face_handle faces_push_back(const Face& f) {
        faces.push_back(*get_face_node(f));
        Face_handle fh = faces.end();
        return --fh;
    }
    
    // 遍历操作
    Halfedge_handle next(Halfedge_handle h) const { return h->next(); }
    Halfedge_handle prev(Halfedge_handle h) const { return h->prev(); }
    Halfedge_handle opposite(Halfedge_handle h) const { return h->opposite(); }
    Vertex_handle vertex(Halfedge_handle h) const { return h->vertex(); }
    Face_handle face(Halfedge_handle h) const { return h->face(); }
};
 
// 默认实现
template<class Traits_, class HalfedgeDSItems = HalfedgeDS_items_2, class Alloc = CGAL_ALLOCATOR(int)>
class HalfedgeDS_default : public HalfedgeDS_list<Traits_, HalfedgeDSItems, Alloc> {
public:
    typedef Traits_ Traits;
    typedef HalfedgeDS_list<Traits_, HalfedgeDSItems, Alloc> D_S;
    typedef typename D_S::size_type size_type;
    
    HalfedgeDS_default() {}
    HalfedgeDS_default(size_type v, size_type h, size_type f)
        : HalfedgeDS_list<Traits_, HalfedgeDSItems, Alloc>(v, h, f) {}
};
 
} // namespace CGAL

3.2 遍历操作实现

// 文件: CGAL/HalfedgeDS_items_decorator.h
 
namespace CGAL {
 
// 半边装饰器，提供额外的遍历操作
template<class HDS>
class HalfedgeDS_items_decorator {
public:
    typedef HDS Halfedge_data_structure;
    typedef typename HDS::Vertex_handle Vertex_handle;
    typedef typename HDS::Halfedge_handle Halfedge_handle;
    typedef typename HDS::Face_handle Face_handle;
    
    // 绕面遍历
    void iterate_around_face(Halfedge_handle h, auto&& f) {
        Halfedge_handle start = h;
        do {
            f(h);
            h = h->next();
        } while (h != start);
    }
    
    // 顶点one-ring遍历
    void iterate_vertex_one_ring(Vertex_handle v, auto&& f) {
        Halfedge_handle h = v->halfedge();
        Halfedge_handle start = h;
        do {
            // 获取相邻顶点（通过opposite->vertex）
            Vertex_handle neighbor = h->opposite()->vertex();
            f(neighbor);
            // 移动到下一个outgoing半边
            h = h->opposite()->next();
        } while (h != start);
    }
    
    // 边遍历（跳过对边）
    void iterate_edges(HDS& hds, auto&& f) {
        for (auto h = hds.halfedges_begin(); h != hds.halfedges_end(); ++h) {
            // 只处理"主"半边（例如索引较小的）
            if (h < h->opposite()) {
                f(h);
            }
        }
    }
    
    // 获取顶点的度数
    std::size_t vertex_degree(Vertex_handle v) {
        std::size_t degree = 0;
        Halfedge_handle h = v->halfedge();
        Halfedge_handle start = h;
        do {
            ++degree;
            h = h->opposite()->next();
        } while (h != start);
        return degree;
    }
    
    // 获取面的边数
    std::size_t face_degree(Face_handle f) {
        std::size_t degree = 0;
        Halfedge_handle h = f->halfedge();
        Halfedge_handle start = h;
        do {
            ++degree;
            h = h->next();
        } while (h != start);
        return degree;
    }
};
 
} // namespace CGAL

3.3 自定义HalfedgeDS Items

// 文件: 自定义Items示例
 
#include <CGAL/HalfedgeDS_items_2.h>
#include <CGAL/HalfedgeDS_halfedge_base.h>
#include <CGAL/HalfedgeDS_vertex_base.h>
#include <CGAL/HalfedgeDS_face_base.h>
 
// 自定义顶点，包含颜色和法向量
template<class Refs, class Traits>
class My_vertex : public CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, typename Traits::Point_3> {
public:
    typedef CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, typename Traits::Point_3> Base;
    typedef typename Traits::Vector_3 Vector_3;
    typedef typename Traits::Color Color;
    
    My_vertex() : Base(), color(0, 0, 0), normal(0, 0, 0) {}
    explicit My_vertex(const typename Traits::Point_3& p) : Base(p), color(0, 0, 0), normal(0, 0, 0) {}
    
    Color color;
    Vector_3 normal;
};
 
// 自定义半边，包含边标记
template<class Refs>
class My_halfedge : public CGAL::HalfedgeDS_halfedge_base<Refs> {
public:
    typedef CGAL::HalfedgeDS_halfedge_base<Refs> Base;
    
    My_halfedge() : Base(), is_sharp(false), edge_weight(1.0) {}
    
    bool is_sharp;
    double edge_weight;
};
 
// 自定义面，包含面标记和材质ID
template<class Refs, class Traits>
class My_face : public CGAL::HalfedgeDS_face_base<Refs> {
public:
    typedef CGAL::HalfedgeDS_face_base<Refs> Base;
    typedef typename Traits::Vector_3 Vector_3;
    
    My_face() : Base(), material_id(0), area(0.0) {}
    
    int material_id;
    double area;
    Vector_3 normal;
};
 
// 自定义Items
template<class Traits>
struct My_items : public CGAL::HalfedgeDS_items_2 {
    template<class Refs, class T>
    struct Vertex_wrapper {
        typedef My_vertex<Refs, T> Vertex;
    };
    
    template<class Refs, class T>
    struct Halfedge_wrapper {
        typedef My_halfedge<Refs> Halfedge;
    };
    
    template<class Refs, class T>
    struct Face_wrapper {
        typedef My_face<Refs, T> Face;
    };
};

4. 使用示例

4.1 示例1：基本HalfedgeDS使用

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
 
// 定义HalfedgeDS类型
struct Traits {
    typedef Point_3 Point_3;
};
 
typedef CGAL::HalfedgeDS_default<Traits> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS> Decorator;
typedef HDS::Vertex_handle Vertex_handle;
typedef HDS::Halfedge_handle Halfedge_handle;
typedef HDS::Face_handle Face_handle;
 
int main() {
    HDS hds;
    Decorator decorator(hds);
    
    // 创建四面体的顶点
    Vertex_handle v0 = hds.vertices_push_back(Vertex_handle::value_type(Point_3(0, 0, 0)));
    Vertex_handle v1 = hds.vertices_push_back(Vertex_handle::value_type(Point_3(1, 0, 0)));
    Vertex_handle v2 = hds.vertices_push_back(Vertex_handle::value_type(Point_3(0, 1, 0)));
    Vertex_handle v3 = hds.vertices_push_back(Vertex_handle::value_type(Point_3(0, 0, 1)));
    
    std::cout << "Created " << hds.size_of_vertices() << " vertices" << std::endl;
    
    // 创建面（需要正确连接半边）
    // 创建第一个面 (v0, v1, v2)
    auto edge_pair1 = hds.edges_push_back();
    auto edge_pair2 = hds.edges_push_back();
    auto edge_pair3 = hds.edges_push_back();
    
    Halfedge_handle h0 = edge_pair1.first;
    Halfedge_handle h1 = edge_pair2.first;
    Halfedge_handle h2 = edge_pair3.first;
    
    // 设置半边连接
    h0->set_next(h1);
    h1->set_next(h2);
    h2->set_next(h0);
    
    h0->set_prev(h2);
    h1->set_prev(h0);
    h2->set_prev(h1);
    
    // 设置顶点
    h0->set_vertex(v1);
    h1->set_vertex(v2);
    h2->set_vertex(v0);
    
    // 创建面
    Face_handle f0 = hds.faces_push_back(Face_handle::value_type());
    f0->set_halfedge(h0);
    h0->set_face(f0);
    h1->set_face(f0);
    h2->set_face(f0);
    
    // 设置顶点的halfedge
    v0->set_halfedge(h2);
    v1->set_halfedge(h0);
    v2->set_halfedge(h1);
    
    std::cout << "Created " << hds.size_of_faces() << " face" << std::endl;
    std::cout << "Total halfedges: " << hds.size_of_halfedges() << std::endl;
    
    // 遍历面的边界
    std::cout << "\nFace boundary vertices:" << std::endl;
    Halfedge_handle h = f0->halfedge();
    Halfedge_handle start = h;
    int count = 0;
    do {
        Point_3 p = h->vertex()->point();
        std::cout << "  Vertex " << count++ << ": (" 
                  << p.x() << ", " << p.y() << ", " << p.z() << ")" << std::endl;
        h = h->next();
    } while (h != start);
    
    return 0;
}

4.2 示例2：面遍历和顶点one-ring遍历

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/Simple_cartesian.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
 
template<class HDS>
class MeshTraversal {
    typedef typename HDS::Vertex_handle Vertex_handle;
    typedef typename HDS::Halfedge_handle Halfedge_handle;
    typedef typename HDS::Face_handle Face_handle;
    
    HDS& hds;
    
public:
    explicit MeshTraversal(HDS& h) : hds(h) {}
    
    // 遍历面的所有顶点
    template<typename Func>
    void traverse_face_vertices(Face_handle f, Func&& func) {
        Halfedge_handle h = f->halfedge();
        Halfedge_handle start = h;
        do {
            func(h->vertex());
            h = h->next();
        } while (h != start);
    }
    
    // 遍历面的所有边
    template<typename Func>
    void traverse_face_edges(Face_handle f, Func&& func) {
        Halfedge_handle h = f->halfedge();
        Halfedge_handle start = h;
        do {
            func(h);
            h = h->next();
        } while (h != start);
    }
    
    // 遍历顶点的one-ring邻居
    template<typename Func>
    void traverse_vertex_one_ring(Vertex_handle v, Func&& func) {
        Halfedge_handle h = v->halfedge();
        if (h == Halfedge_handle()) return;  // 孤立顶点
        
        Halfedge_handle start = h;
        do {
            // 获取相邻顶点（通过opposite->vertex）
            Vertex_handle neighbor = h->opposite()->vertex();
            func(neighbor);
            // 移动到下一个outgoing半边
            h = h->opposite()->next();
        } while (h != start);
    }
    
    // 遍历顶点的邻接面
    template<typename Func>
    void traverse_vertex_faces(Vertex_handle v, Func&& func) {
        Halfedge_handle h = v->halfedge();
        if (h == Halfedge_handle()) return;
        
        Halfedge_handle start = h;
        do {
            Face_handle f = h->face();
            if (f != Face_handle()) {
                func(f);
            }
            h = h->opposite()->next();
        } while (h != start);
    }
    
    // 获取顶点度数
    std::size_t get_vertex_degree(Vertex_handle v) {
        std::size_t degree = 0;
        traverse_vertex_one_ring(v, [&](Vertex_handle) { ++degree; });
        return degree;
    }
    
    // 计算面的面积（三角形）
    double compute_triangle_area(Face_handle f) {
        std::vector<Point_3> points;
        traverse_face_vertices(f, [&](Vertex_handle v) {
            points.push_back(v->point());
        });
        
        if (points.size() != 3) return 0.0;
        
        Kernel::Vector_3 v0 = points[1] - points[0];
        Kernel::Vector_3 v1 = points[2] - points[0];
        Kernel::Vector_3 cross = CGAL::cross_product(v0, v1);
        return std::sqrt(cross.squared_length()) / 2.0;
    }
};
 
// 使用示例
int main() {
    // 假设已经创建了一个HDS对象hds
    // 这里仅展示遍历函数的用法
    
    std::cout << "MeshTraversal functions:" << std::endl;
    std::cout << "  - traverse_face_vertices: 遍历面的所有顶点" << std::endl;
    std::cout << "  - traverse_face_edges: 遍历面的所有边" << std::endl;
    std::cout << "  - traverse_vertex_one_ring: 遍历顶点的one-ring邻居" << std::endl;
    std::cout << "  - traverse_vertex_faces: 遍历顶点的邻接面" << std::endl;
    std::cout << "  - get_vertex_degree: 获取顶点度数" << std::endl;
    std::cout << "  - compute_triangle_area: 计算三角形面积" << std::endl;
    
    return 0;
}

4.3 示例3：自定义HalfedgeDS Items

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Vector_3 Vector_3;
 
// 颜色结构
struct Color {
    unsigned char r, g, b;
    Color(unsigned char r = 0, unsigned char g = 0, unsigned char b = 0)
        : r(r), g(g), b(b) {}
};
 
// 自定义顶点
template<class Refs, class Traits>
class Custom_vertex : public CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, Point_3> {
public:
    typedef CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, Point_3> Base;
    
    Custom_vertex() : Base(), color(255, 255, 255), normal(0, 0, 0), selected(false) {}
    explicit Custom_vertex(const Point_3& p) : Base(p), color(255, 255, 255), normal(0, 0, 0), selected(false) {}
    
    Color color;
    Vector_3 normal;
    bool selected;
    int id = -1;
};
 
// 自定义半边
template<class Refs>
class Custom_halfedge : public CGAL::HalfedgeDS_halfedge_base<Refs> {
public:
    typedef CGAL::HalfedgeDS_halfedge_base<Refs> Base;
    
    Custom_halfedge() : Base(), is_sharp(false), edge_weight(1.0), visited(false) {}
    
    bool is_sharp;
    double edge_weight;
    bool visited;
    int edge_id = -1;
};
 
// 自定义面
template<class Refs, class Traits>
class Custom_face : public CGAL::HalfedgeDS_face_base<Refs> {
public:
    typedef CGAL::HalfedgeDS_face_base<Refs> Base;
    
    Custom_face() : Base(), material_id(0), area(0.0), visible(true) {}
    
    int material_id;
    double area;
    Vector_3 normal;
    bool visible;
};
 
// 自定义Items
template<class Traits>
struct Custom_items : public CGAL::HalfedgeDS_items_2 {
    template<class Refs, class T>
    struct Vertex_wrapper {
        typedef Custom_vertex<Refs, T> Vertex;
    };
    
    template<class Refs, class T>
    struct Halfedge_wrapper {
        typedef Custom_halfedge<Refs> Halfedge;
    };
    
    template<class Refs, class T>
    struct Face_wrapper {
        typedef Custom_face<Refs, T> Face;
    };
};
 
// 使用自定义Items的HDS
struct Traits {
    typedef Point_3 Point_3;
    typedef Vector_3 Vector_3;
    typedef Color Color;
};
 
typedef CGAL::HalfedgeDS_default<Traits, Custom_items<Traits>> Custom_HDS;
typedef Custom_HDS::Vertex_handle Vertex_handle;
typedef Custom_HDS::Halfedge_handle Halfedge_handle;
typedef Custom_HDS::Face_handle Face_handle;
 
int main() {
    Custom_HDS hds;
    
    // 创建顶点
    Vertex_handle v0 = hds.vertices_push_back(Custom_vertex<Point_3>(Point_3(0, 0, 0)));
    Vertex_handle v1 = hds.vertices_push_back(Custom_vertex<Point_3>(Point_3(1, 0, 0)));
    Vertex_handle v2 = hds.vertices_push_back(Custom_vertex<Point_3>(Point_3(0, 1, 0)));
    
    // 设置自定义属性
    v0->color = Color(255, 0, 0);
    v1->color = Color(0, 255, 0);
    v2->color = Color(0, 0, 255);
    
    v0->id = 0;
    v1->id = 1;
    v2->id = 2;
    
    v0->selected = true;
    
    // 计算并设置法向量
    Vector_3 n = CGAL::cross_product(v1->point() - v0->point(), v2->point() - v0->point());
    v0->normal = n;
    v1->normal = n;
    v2->normal = n;
    
    // 输出顶点信息
    std::cout << "Vertex information:" << std::endl;
    for (auto v = hds.vertices_begin(); v != hds.vertices_end(); ++v) {
        std::cout << "  Vertex " << v->id << ":" << std::endl;
        std::cout << "    Position: (" << v->point().x() << ", " 
                  << v->point().y() << ", " << v->point().z() << ")" << std::endl;
        std::cout << "    Color: RGB(" << (int)v->color.r << ", " 
                  << (int)v->color.g << ", " << (int)v->color.b << ")" << std::endl;
        std::cout << "    Selected: " << (v->selected ? "yes" : "no") << std::endl;
    }
    
    return 0;
}

4.4 示例4：半边数据结构构建完整网格

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/Simple_cartesian.h>
#include <vector>
#include <iostream>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
 
template<class HDS>
class MeshBuilder {
    typedef typename HDS::Vertex_handle Vertex_handle;
    typedef typename HDS::Halfedge_handle Halfedge_handle;
    typedef typename HDS::Face_handle Face_handle;
    
    HDS& hds;
    CGAL::HalfedgeDS_decorator<HDS> decorator;
    
public:
    explicit MeshBuilder(HDS& h) : hds(h), decorator(h) {}
    
    // 添加顶点
    Vertex_handle add_vertex(const Point_3& p) {
        return hds.vertices_push_back(typename HDS::Vertex(p));
    }
    
    // 添加面（假设顶点已存在）
    Face_handle add_face(const std::vector<Vertex_handle>& vertices) {
        std::size_t n = vertices.size();
        if (n < 3) return Face_handle();
        
        // 创建半边
        std::vector<Halfedge_handle> halfedges;
        for (std::size_t i = 0; i < n; ++i) {
            auto edge_pair = hds.edges_push_back();
            halfedges.push_back(edge_pair.first);
        }
        
        // 连接半边形成环
        for (std::size_t i = 0; i < n; ++i) {
            halfedges[i]->set_next(halfedges[(i + 1) % n]);
            halfedges[i]->set_prev(halfedges[(i + n - 1) % n]);
            halfedges[i]->set_vertex(vertices[(i + 1) % n]);
        }
        
        // 创建面
        Face_handle f = hds.faces_push_back(typename HDS::Face());
        f->set_halfedge(halfedges[0]);
        
        // 设置面的半边
        for (auto h : halfedges) {
            h->set_face(f);
        }
        
        // 更新顶点的halfedge指针
        for (std::size_t i = 0; i < n; ++i) {
            vertices[i]->set_halfedge(halfedges[(i + n - 1) % n]);
        }
        
        return f;
    }
    
    // 验证网格完整性
    bool validate() {
        // 检查每个顶点的halfedge
        for (auto v = hds.vertices_begin(); v != hds.vertices_end(); ++v) {
            if (v->halfedge() == Halfedge_handle()) {
                std::cerr << "Vertex has no halfedge" << std::endl;
                return false;
            }
            if (v->halfedge()->vertex() != v) {
                std::cerr << "Vertex halfedge inconsistency" << std::endl;
                return false;
            }
        }
        
        // 检查每个面的halfedge
        for (auto f = hds.faces_begin(); f != hds.faces_end(); ++f) {
            if (f->halfedge() == Halfedge_handle()) {
                std::cerr << "Face has no halfedge" << std::endl;
                return false;
            }
            if (f->halfedge()->face() != f) {
                std::cerr << "Face halfedge inconsistency" << std::endl;
                return false;
            }
        }
        
        // 检查半边连接
        for (auto h = hds.halfedges_begin(); h != hds.halfedges_end(); ++h) {
            if (h->next()->prev() != h) {
                std::cerr << "Halfedge next/prev inconsistency" << std::endl;
                return false;
            }
            if (h->opposite()->opposite() != h) {
                std::cerr << "Halfedge opposite inconsistency" << std::endl;
                return false;
            }
        }
        
        return true;
    }
    
    // 统计信息
    void print_statistics() {
        std::cout << "Mesh Statistics:" << std::endl;
        std::cout << "  Vertices: " << hds.size_of_vertices() << std::endl;
        std::cout << "  Halfedges: " << hds.size_of_halfedges() << std::endl;
        std::cout << "  Edges: " << hds.size_of_halfedges() / 2 << std::endl;
        std::cout << "  Faces: " << hds.size_of_faces() << std::endl;
        
        // 计算欧拉示性数
        int V = hds.size_of_vertices();
        int E = hds.size_of_halfedges() / 2;
        int F = hds.size_of_faces();
        int chi = V - E + F;
        std::cout << "  Euler characteristic: " << chi << std::endl;
    }
};
 
int main() {
    typedef CGAL::HalfedgeDS_default<Traits> HDS;
    HDS hds;
    MeshBuilder<HDS> builder(hds);
    
    // 创建四面体
    auto v0 = builder.add_vertex(Point_3(0, 0, 0));
    auto v1 = builder.add_vertex(Point_3(1, 0, 0));
    auto v2 = builder.add_vertex(Point_3(0, 1, 0));
    auto v3 = builder.add_vertex(Point_3(0, 0, 1));
    
    // 添加四个面
    builder.add_face({v0, v1, v2});
    builder.add_face({v0, v1, v3});
    builder.add_face({v0, v2, v3});
    builder.add_face({v1, v2, v3});
    
    // 验证和输出
    std::cout << "Validation: " << (builder.validate() ? "PASSED" : "FAILED") << std::endl;
    builder.print_statistics();
    
    return 0;
}

5. 复杂度分析

5.1 时间复杂度

操作	复杂度	说明
创建顶点	O(1)	列表尾部插入
创建半边对	O(1)	分配和初始化
创建面	O(k)	k为面的边数
next/prev/opposite	O(1)	直接指针访问
vertex/face	O(1)	直接指针访问
绕面遍历	O(k)	k为面的边数
one-ring遍历	O(d)	d为顶点度数
边遍历	O(E)	E为边数

5.2 空间复杂度

元素	空间	说明
Vertex	1 × sizeof(void*) + Point	halfedge指针 + 几何
Halfedge	4 × sizeof(void*)	next, prev, opposite, vertex, face
Face	1 × sizeof(void*)	halfedge指针
总计	O(V + H + F) ≈ O(V + F)	H ≈ 2E ≈ 3F（三角形网格）

5.3 与其他数据结构的对比

特性	HalfedgeDS	Winged-edge	Quad-edge	Corner Table
半边表示	是	否	是	否
面遍历	O(k)	O(k)	O(k)	O(k)
顶点one-ring	O(d)	O(d)	O(d)	O(d)
内存效率	高	中	中	高
边界处理	自然	复杂	自然	需要特殊处理
实现复杂度	中	高	高	低

6. 关键文件位置

文件路径	说明
`HalfedgeDS/include/CGAL/HalfedgeDS_default.h`	默认HalfedgeDS实现
`HalfedgeDS/include/CGAL/HalfedgeDS_list.h`	基于列表的实现
`HalfedgeDS/include/CGAL/HalfedgeDS_vector.h`	基于向量的实现
`HalfedgeDS/include/CGAL/HalfedgeDS_items_2.h`	默认Items定义
`HalfedgeDS/include/CGAL/HalfedgeDS_decorator.h`	遍历装饰器
`HalfedgeDS/include/CGAL/HalfedgeDS_vertex_base.h`	顶点基类
`HalfedgeDS/include/CGAL/HalfedgeDS_halfedge_base.h`	半边基类
`HalfedgeDS/include/CGAL/HalfedgeDS_face_base.h`	面基类
`HalfedgeDS/include/CGAL/HalfedgeDS_iterator.h`	迭代器定义

7. 最佳实践

7.1 使用建议

使用HalfedgeDS_decorator简化遍历：

CGAL::HalfedgeDS_decorator<HDS> decorator(hds);
decorator.iterate_around_face(h, [&](auto v) { ... });

自定义Items时继承基类：

class My_vertex : public CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, Point> {
    // 自定义属性
};

验证网格完整性：
```
assert(decorator.is_valid());
```

使用句柄而非指针：

Vertex_handle v = ...;  // 推荐
// 而非 Vertex* v = ...;

7.2 常见陷阱

忘记设置对边：

// 错误：半边对需要正确链接
auto pair = hds.edges_push_back();
// 对边已经自动链接，不需要手动设置

边界处理：

// 边界半边的face()返回空句柄
if (h->face() == Face_handle()) {
    // 这是边界半边
}

顶点halfedge选择：

// 顶点的halfedge()可以是任意一条outgoing半边
// 如果需要特定半边，需要手动遍历

Chunibyo

Explorer

3.4 半边数据结构（HalfedgeDS）

3.4 半边数据结构（HalfedgeDS）

1. 理论基础

1.1 半边数据结构的数学定义

1.2 连接关系的数学表示

1.3 欧拉公式验证

2. 架构分析

2.1 HalfedgeDS类层次结构

2.2 内存布局

2.3 句柄（Handle）系统

3. 实现细节

3.1 HalfedgeDS_list实现

3.2 遍历操作实现

3.3 自定义HalfedgeDS Items

4. 使用示例

4.1 示例1：基本HalfedgeDS使用

4.2 示例2：面遍历和顶点one-ring遍历

4.3 示例3：自定义HalfedgeDS Items

4.4 示例4：半边数据结构构建完整网格

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 与其他数据结构的对比

6. 关键文件位置

7. 最佳实践

7.1 使用建议

7.2 常见陷阱

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

3.4 半边数据结构（HalfedgeDS）

3.4 半边数据结构（HalfedgeDS） §

1. 理论基础 §

1.1 半边数据结构的数学定义 §

1.2 连接关系的数学表示 §

1.3 欧拉公式验证 §

2. 架构分析 §

2.1 HalfedgeDS类层次结构 §

2.2 内存布局 §

2.3 句柄（Handle）系统 §

3. 实现细节 §

3.1 HalfedgeDS_list实现 §

3.2 遍历操作实现 §

3.3 自定义HalfedgeDS Items §

4. 使用示例 §

4.1 示例1：基本HalfedgeDS使用 §

4.2 示例2：面遍历和顶点one-ring遍历 §

4.3 示例3：自定义HalfedgeDS Items §

4.4 示例4：半边数据结构构建完整网格 §

5. 复杂度分析 §

5.1 时间复杂度 §

5.2 空间复杂度 §

5.3 与其他数据结构的对比 §

6. 关键文件位置 §

7. 最佳实践 §

7.1 使用建议 §

7.2 常见陷阱 §

Graph View

Table of Contents

Backlinks

3.4 半边数据结构（HalfedgeDS）

1. 理论基础

1.1 半边数据结构的数学定义

1.2 连接关系的数学表示

1.3 欧拉公式验证

2. 架构分析

2.1 HalfedgeDS类层次结构

2.2 内存布局

2.3 句柄（Handle）系统

3. 实现细节

3.1 HalfedgeDS_list实现

3.2 遍历操作实现

3.3 自定义HalfedgeDS Items

4. 使用示例

4.1 示例1：基本HalfedgeDS使用

4.2 示例2：面遍历和顶点one-ring遍历

4.3 示例3：自定义HalfedgeDS Items

4.4 示例4：半边数据结构构建完整网格

5. 复杂度分析

5.1 时间复杂度

5.2 空间复杂度

5.3 与其他数据结构的对比

6. 关键文件位置

7. 最佳实践

7.1 使用建议

7.2 常见陷阱