官方手册：半边数据结构

作者：Lutz Kettner Introduced in 版本引入: CGAL 1.0 BibTeX 文献排版: cgal:k-hds-17b License 版本许可: LGPL

半边结构是一个以边为中心的数据结构，这个结构可以保持顶点、边和面的关联关系，例如对于平面图、多面体或其他嵌入在任意维度中的定向、二维表面。

  • 每一条边被分解为相反反向的两个半边
  • 每个半边中保存有一个关联面和一个关联顶点
  • 对于每一个边和每一个顶点，保存有一个关联半边
  • 半边数据结构变化的减少可以忽略一些信息，例如半边指向面或存储在所有的面中

介绍

半边数据结构，简写为HalfedgeDS，模板参数里写为HDS。是一个以边为中心的数据结构。

平面图，多面体或者其他二维定向表面均可以使用半边数据结构。每个边都分成两个方向相反的半边。每条半边都存储它的一个入射面和一个入射点。
半边数据结构Halfedge Data Structures - 图1

软件设计

三层式的软件设计结构

半边数据结构Halfedge Data Structures - 图2

Items层

items存储了实实在在的点边面的信息，包括成员变量，以及访问它们的成员函数

halfedges被要求提供指向下一个halfedge和对面halfedge的引用。有时候也可以让halfedge提供指向前一个halfedge的引用。

更进一步的，items类还能通过继承与派生扩展机制，可以携带任意属性，任意成员函数

点，半边和面都被当做items类的局部类型传递给半边数据结构和polyhedron。最基本的对点线面的应用CGAL已经提供了，用户可以将其作为基类使用

HalfedgeDS层

HalfedgeDS内部双向链表或者vector可以实现对底层item的存储。HalfedgeDS有两种模型：HalfedgeDS_list和HalfedgeDS_vector。

HalfedgeDS定义了items的handle和iterator。

为了保持这两个模型的接口简洁，有些通用的功能就留给了其他的辅助类，比如HalfedgeDS_decorator, HalfedgeDS_const_decorator, HalfedgeDS_items_decorator

  • 在上图中没有显示，但它们应该画在HalfedgeDS的旁边，因为它们扩展了接口并且没有隐藏这些接口
  • 这些辅助类包含的一些操作能辅助更高的layer比如Polyhedron层实现一些操作
  • 此外，辅助类包含适应性功能。比如说，如果halfedges没有HalfedgeDSHalfedge::prev()成员函数，辅助类中的HalfedgeDS_items_decorator::find_prev()成员函数就会沿着面的正向查找前继的halfedge。但如果有HalfedgeDSHalfedge::prev()这个成员函数，HalfedgeDS_items_decorator::find_prev()就只要调用一下HalfedgeDSHalfedge::prev()就可以了

Polyhedron_3

最高层用Polyhedron_3来举例子

Polyhedron_3对下层接口进行了很好的封装

  • 比如将face重新命名成facet
  • 比如handles不能直接被用户访问
  • 比如提供了circulators使得用户能够访问一个vertex或facet周围环绕的edges的环形序列

这一切都是Polyhedron_3通过从Items中派生出新的vertices, halfedges 和 facets得到的

例子

半边结构的访问

image.png
image.png

默认的半边数据结构

接下来的例子用了默认的半边数据结构和decorator类。

  • 默认的半边数据结构使用了链表式的构造。
  • items之间的关联关系和vertices的类型都在这里定义。
  • trivial traits这个类提供了点的类型

这个程序创建了一个环（loop），环里面包含两条半边，一个点和两个面，程序还检测了这个图形的有效性。

  1. #include <CGAL/HalfedgeDS_default.h>
  2. #include <CGAL/HalfedgeDS_decorator.h>
  3. struct Traits { typedef int Point_2; };
  4. typedef CGAL::HalfedgeDS_default<Traits> HDS;
  5. typedef CGAL::HalfedgeDS_decorator<HDS> Decorator;
  6. int main() {
  7.     HDS hds;
  8.     Decorator decorator(hds);
  9.     decorator.create_loop();
  10.     CGAL_assertion( decorator.is_valid());
  11.     return 0;
  12. }

一个最小的半边数据结构

接下来这个程序用最小的items类 HalfedgeDS_min_items，搭配链表型的半边数据结构定义了一个最小的半边数据结构。

这个数据结构只包含半边（下一条边和对边的指针），没有存储点或者面的信息。这是个无向图。

  1. #include <CGAL/HalfedgeDS_min_items.h>
  2. #include <CGAL/HalfedgeDS_default.h>
  3. #include <CGAL/HalfedgeDS_decorator.h>
  4. // no traits needed, argument can be arbitrary dummy.
  5. typedef CGAL::HalfedgeDS_default<int, CGAL::HalfedgeDS_min_items> HDS;
  6. typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
  7. int main() {
  8.     HDS hds;
  9.     Decorator decorator(hds);
  10.     decorator.create_loop();
  11.     CGAL_assertion( decorator.is_valid());
  12.     return 0;
  13. }

将默认的链表型的HalfedgeDS改为vector型

默认的半边数据结构内用链表型的构造，继承自最复杂的基类。我们现在将其转化为vector型的构造。

  • trivial traits类决定了点的数据类型
  • 要注意，vector的容量要事先就保留好，通过例子里的构造函数或者reserve()成员函数都能达到这种效果
  • 也可以事后再调用reserve()函数去修改容量，但是要保证内存中的空间是连续的
    1. #include <CGAL/HalfedgeDS_items_2.h>
    2. #include <CGAL/HalfedgeDS_vector.h>
    3. #include <CGAL/HalfedgeDS_decorator.h>
    4. struct Traits { typedef int Point_2; };
    5. typedef CGAL::HalfedgeDS_vector< Traits, CGAL::HalfedgeDS_items_2> HDS;
    6. typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
    7. int main() {
    8.   HDS hds(1,2,2);
    9.   Decorator decorator(hds);
    10.   decorator.create_loop();
    11.   CGAL_assertion( decorator.is_valid());
    12.   return 0;
    13. }

向facet添加颜色

这个例子重新使用了face的基类，加入了一个颜色变量。

  1. #include <CGAL/HalfedgeDS_items_2.h>
  2. #include <CGAL/HalfedgeDS_default.h>
  3. #include <CGAL/IO/Color.h>
  4. // A face type with a color member variable.
  5. template <class Refs>
  6. struct My_face : public CGAL::HalfedgeDS_face_base<Refs> {
  7.     CGAL::Color color;
  8.     My_face() {}
  9.     My_face( CGAL::Color c) : color(c) {}
  10. };
  11. // An items type using my face.
  12. struct My_items : public CGAL::HalfedgeDS_items_2 {
  13.     template <class Refs, class Traits>
  14.     struct Face_wrapper {
  15.         typedef My_face<Refs> Face;
  16.     };
  17. };
  18. struct My_traits { // arbitrary point type, not used here.
  19.     typedef int  Point_2;
  20. };
  21. typedef CGAL::HalfedgeDS_default<My_traits, My_items> HDS;
  22. typedef HDS::Face                                     Face;
  23. typedef HDS::Face_handle                              Face_handle;
  24. int main() {
  25.     HDS hds;
  26.     Face_handle f = hds.faces_push_back( Face( CGAL::RED));
  27.     f->color = CGAL::BLUE;
  28.     CGAL_assertion( f->color == CGAL::BLUE);
  29.     return 0;
  30. }

定义一个更加紧凑的半边结构

Iterator

用默认的半边数据结构创建了两个边以后。可以用半边iterator来计算halfedges了。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_default<Traits> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
typedef HDS::Halfedge_iterator           Iterator;
int main() {
    HDS hds;
    Decorator decorator(hds);
    decorator.create_loop();
    decorator.create_segment();
    CGAL_assertion( decorator.is_valid());
    int n = 0;
    for ( Iterator i = hds.halfedges_begin(); i != hds.halfedges_end(); ++i )
        ++n;
    CGAL_assertion( n == 4);  // == 2 edges
    return 0;
}

用适配器来建立一个edge iterator

用默认的半边数据结构创建了3跳变。适配器N_step_adaptor声明了edge iterator。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/N_step_adaptor.h>
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_default<Traits>            HDS;
typedef CGAL::HalfedgeDS_decorator<HDS>             Decorator;
typedef HDS::Halfedge_iterator                      Halfedge_iterator;
typedef CGAL::N_step_adaptor< Halfedge_iterator, 2> Iterator;
int main() {
    HDS hds;
    Decorator decorator(hds);
    decorator.create_loop();
    decorator.create_segment();
    CGAL_assertion( decorator.is_valid());
    int n = 0;
    for ( Iterator e = hds.halfedges_begin(); e != hds.halfedges_end(); ++e)
        ++n;
    CGAL_assertion( n == 2);  // == 2 edges
    return 0;
}