参考文献："Using generic programming for designing a data structure for polyhedral surfaces"

http://s10/mw690/003tGfdagy6HFDrSPKV09&690
Halfedge_data_structure作为容器类管理Vertex、Halfedge、Facet三项及其之间的拓扑关系。

Topological_map管理Facet上的holes,也为Facet计算内部和外部边界。

Polyhedron类在Halfedge_data_structure上增加了几何操作。（因为半边数据结构可能有其他用途，并未严格按多边形表面的定义来约束）

Halfedge_data_structure和Vertex、Halfedge、Facet被称为概念(concept),有三种不同的Halfedge_data_structure模型，一种采用STL 里的vector,另2中基于list来表示。

Halfedge_data_structure为这些基本item存储组织方式负责，采用双向链表或者STL的vector方式实现。Halfedge_data_structure定义了属于这些item的句柄handle和迭代器iterator.

Polyhedron提供了易于使用的高级函数接口，接口被设计成能保护内部表达的完整性，句柄handle不在是不定的。Polyhedron中加入了方便有效的循环器circulator。

**************************************************************************

CGAL中通过在真实的几何内核kenel和数据结构、算法之间使用traits类，允许我们容易为其他的核提供适配器adaptor.

一个使用基于缺省的双精度的笛卡尔内核的多面体Polyhedron的声明如下：

typedef CGAL::Simple_cartesian Kernel;

typedef CGAL::Polyhedron_default_traits_3 Traits;

typedef CGAL::Polyhedron_3 Polyhedron;

**************************************************************************
CGAL::Polyhedron_incremental_builder_3< HDS > Class

支持增量构造多面体表面，方便从Object File Format (OFF)\OpenInventor\VRML格式的文件构建。

它需要访问多面体表面的半边数据结构中的类型HDS。

**************************************************************************

CGAL中的定义对于顶点，边和面元素进行了封装，将他们放在同一个不带模板参数的类里面，类似下面代码模仿的HalfedgeDS_iems，从而将他们集中到一起并且最外层去掉模板参数，里面通过wrapper将他们的定义包装。用户可以定义不同的顶点类，只要在传给HalfedgeDS的HalfedgeItesms参数的类中typedef 自己定义的顶点类为Vertex即可。

例：

#include
#include
#include
using std::list;
using std::string;
using std::cout;
using std::endl;
template
struct Vertex {
      typedef typename Refs::Halfedge_handle Halfedge_handle;
      Vertex(string name = "vertex0") { m_name = name;}
      void PrintName() const {
            cout << "This is " << m_name << endl;

      }
      Halfedge_handle halfedge() const { return h; }
      void set_halfedge (Halfedge_handle g) { h = g; }
   private:
      Halfedge_handle h;
      string m_name;
};
template
struct Halfedge {
      typedef typename Refs::Vertex_handle Vertex_handle;
      Halfedge(string name = "halfedge0") { m_name = name;}
      void PrintName() const {
            cout << "This is " << m_name << endl;
      }
      Vertex_handle vertex() const { return v;}
      void set_vertex (Vertex_handle vv) { v = vv;}
   private:
      Vertex_handle v;
      string m_name;
};
struct HalfedgeDS_iems {
      template
      struct Vertex_wrapper {
            typedef Vertex Vertex;
      };
      template
      struct Halfedge_wrapper {
            typedef Halfedge Halfedge;
            };
};
template < typename HalfedgeDSItems>
struct HalfedgeDS {
      typedef HalfedgeDS< HalfedgeDSItems>     Self;
      typedef HalfedgeDSItems                         Items;
      typedef typename Items::template Vertex_wrapper       Vertex_wrapper;
      typedef typename Items::template Halfedge_wrapper     Halfedge_wrapper;
      typedef typename Vertex_wrapper::Vertex            Vertex;
      typedef typename Halfedge_wrapper::Halfedge      Halfedge;
      typedef list                       Vlist;
      typedef list                    Hlist;
      typedef typename Vlist::iterator Vertex_handle;
      typedef typename Hlist::iterator Halfedge_handle;
};

int main(int argc, char *argv[])
{
      typedef HalfedgeDS HDS;
      typedef HDS::Vertex Vert;
      typedef HDS::Halfedge HalfEdge;
      typedef HDS::Vlist Vlist;
      typedef HDS::Hlist Hlist;
      Vert v("vertex a");
      HalfEdge h("Halfedge b");
      Vlist vlist;
      Hlist hlist;
      vlist.push_back(v);
      hlist.push_back(h);
      v.set_halfedge(hlist.begin());
      h.set_vertex(vlist.begin());
      v.halfedge()->PrintName();
      h.vertex()->PrintName();
      return 0;
}

多了一个HalfedgeDS_iems包装的一个好处是由于HalfedgeDS_iems没有模板参数，所以下面的定义是可能的，CGAL中定义有Polyhedron它的一个模板参数是HDS，即半边结构，考虑上面没有封装到HalfedgeItesms的方案，

template < template class Vertex, template class Halfedge>
struct HalfedgeDS

HalfedgeDS的定义已经有两级模板参数了，如果再被传递会有三级模板参数，C++是不允许这样的，所以HalfedgeDS_iems方法不失为一种绕过的技巧。

template < class Traits,
           class Items = Items_default,
           template < class, class> calss HDS = HalfedgeDS_default>
struct Polyhedron {
      typedef Polyhedron_items Deerived_items;
      typedef HDS< Traits, Derived_items> HDS；
      typedef typename HDS::Vertex                  Vertex;
      typedef typename HDS::Halfedge               Halfedge;
      typedef typename HDS::Face                    Face;

 .....
};

先看一个用户自己扩充面的例子，完全继承已有的边和顶点，用户当然也可以全部扩充，总之通过wrapper是很灵活的。

template
class My_facet : public CGAL_HalfedgeDS_facet_base {
      int face_cost;  // we need to sore addtional info
    public:
       typename Traits::Vector_3 normal; 
};

struct My_items : public CGAL_Polyhedron_items_3 {
      template
      struct Face_wrapper {
            typedef My_facet< Refs, Traits> Facet;
      };
};

typedef CGAL_Polyhedron_3My_items> Polyhedron;

这样我们的Polyhedron就是应用用户定义的facet了同时保留了CGAL_Polyhedron_items_3中定义的facet的所以属性函数，如set_handle.由于用户没有定义Vertex和Halfedge所以它们完全用CGAL_Polyhedron_items_3中提供的Vertex和Halfege不加任何扩充。

class Polyhedron_items_3 {
public:
    template < class Refs, class Traits>
    struct Vertex_wrapper {
        typedef typename Traits::Point_3 Point;
        typedef HalfedgeDS_vertex_base< Refs, Tag_true, Point> Vertex;
    };
    template < class Refs, class Traits>
    struct Halfedge_wrapper {
        typedef HalfedgeDS_halfedge_base< Refs>                Halfedge;
    };
    template < class Refs, class Traits>
    struct Face_wrapper {
        typedef typename Traits::Plane_3 Plane;
        typedef HalfedgeDS_face_base< Refs, Tag_true, Plane>   Face;
    };
};

template < class Refs >
class HalfedgeDS_face_base< Refs, Tag_true, Tag_false> {
public:
    typedef Refs                                 HalfedgeDS;
    typedef HalfedgeDS_face_base< Refs, Tag_true, Tag_false>   Base;
    typedef Tag_true                             Supports_face_halfedge;
    typedef typename Refs::Vertex_handle         Vertex_handle;
    typedef typename Refs::Vertex_const_handle   Vertex_const_handle;
    typedef typename Refs::Halfedge_handle       Halfedge_handle;
    typedef typename Refs::Halfedge_const_handle Halfedge_const_handle;
    typedef typename Refs::Face_handle           Face_handle;
    typedef typename Refs::Face_const_handle     Face_const_handle;
    typedef typename Refs::Vertex                Vertex;
    typedef typename Refs::Halfedge              Halfedge;
    // Additional tags required by Polyhedron.
    typedef Tag_false                            Supports_face_plane;
    struct Plane_not_supported {};
    typedef Plane_not_supported                  Plane;
    // No longer required.
    //typedef Tag_false                            Supports_face_normal;

private:
    Halfedge_handle hdg;
public:
   Halfedge_handle       halfedge()                        { return hdg; }
    Halfedge_const_handle halfedge() const                  { return hdg; }
    void                  set_halfedge( Halfedge_handle h)  { hdg = h; }
};

用户自定义的Items，Vetex会被当作模板参数传递如下。

template <</span>class Vertex_base>
struct Polyhedron_vertex : public Vertex_base {

      typedef Vertex_base Base;
private:

      void set_halfedge(typename Base::Halfedge_handle g) {

            Base::set_halfedge(g);
      }
};

template <</span>class Items>
struct Polyhderon_items {
      template <</span>class Refs, class Traits>

      struct Vertex_wrapper {
            typedef typename Items::Vertex_wrapper<</span>Refs, Traits> Wrapper;
            typedef typename Wrapper::Vertex Vertex_base;
            typedef Polyhedron_vertex<</span>Vertex_base> Vertex;
      };

      //http://www.cnblogs.com/Images/dot.gifsimilar for facet and halfedge
};

template <</span> class Traits,

           class Items = Items_default,
           template <</span> class, class> calss HDS = HalfedgeDS_default>
struct Polyhedron {
      typedef Polyhedron_items<</span>Items> Deerived_items;
      typedef HDS<</span> Traits, Derived_items> HDS；
      typedef typename HDS::Vertex                  Vertex;
      typedef typename HDS::Halfedge                Halfedge;
      typedef typename HDS::Face                    Face;

 .....
};

也就是说最后实际用的是Polyhedron_items 中定义的Vertex Polyhedron_vertex

而 Items即为用户定义并传递的点面边数据类型类。Vertex_base是用户定义的Vertex类型。

下面看一下CGAL实际的代码，这里的I_Polyhedron_vertex其实就是上面的Polyhedron_vertex。

template <</span>class VertexBase>
class I_Polyhedron_vertex  : public VertexBase  {
public:

    typedef VertexBase                            Base;

    //typedef typename Base::HalfedgeDS              HDS;
    typedef typename Base::Point                   Point;

    typedef Point                                  Point_3;



    // Handles have to explicitly repeated, although they are derived
    typedef typename Base::Vertex_handle           Vertex_handle;

    typedef typename Base::Halfedge_handle         Halfedge_handle;

    typedef typename Base::Face_handle             Face_handle;

    typedef typename Base::Face_handle             Facet_handle;

    typedef typename Base::Vertex_const_handle     Vertex_const_handle;

    typedef typename Base::Halfedge_const_handle   Halfedge_const_handle;

    typedef typename Base::Face_const_handle       Face_const_handle;

    typedef typename Base::Face_const_handle       Facet_const_handle;

    typedef typename Base::Halfedge                Halfedge;

    typedef typename Base::Face                    Face;

    typedef typename Base::Face                    Facet;



    // Supported options by HDS.
    typedef typename Base::Supports_vertex_halfedge

                                                  Supports_vertex_halfedge;

    typedef typename Base::Supports_vertex_point  Supports_vertex_point;



    // Circulator category.
    typedef typename Halfedge::Supports_halfedge_prev  Supports_prev;


public:

    // Circulator category.
    typedef HalfedgeDS_circulator_traits<</span>Supports_prev> Ctr;

    typedef typename Ctr::iterator_category circulator_category;



    // Circulators around a vertex and around a facet.
    typedef I_HalfedgeDS_facet_circ<</span> Halfedge_handle, circulator_category>

                                         Halfedge_around_facet_circulator;



    typedef I_HalfedgeDS_vertex_circ<</span> Halfedge_handle, circulator_category>

                                        Halfedge_around_vertex_circulator;



    typedef I_HalfedgeDS_facet_circ<</span>

        Halfedge_const_handle,

        circulator_category>       Halfedge_around_facet_const_circulator;



    typedef I_HalfedgeDS_vertex_circ<</span>

        Halfedge_const_handle,

        circulator_category>      Halfedge_around_vertex_const_circulator;







    typedef typename Halfedge_around_vertex_circulator::size_type

        size_type;

    typedef typename Halfedge_around_vertex_circulator::difference_type

        difference_type;


public:

    // We need to repeat the constructors here.
    I_Polyhedron_vertex() {}

    I_Polyhedron_vertex( const VertexBase& b) : VertexBase(b) {}

    I_Polyhedron_vertex( const Point_3& p) : VertexBase(p) {}


// New Access Functions (not provided in VertexBase).


    Halfedge_around_vertex_circulator vertex_begin() {

        // a circulator of halfedges around the vertex (clockwise).
        return Halfedge_around_vertex_circulator( this->halfedge());

    }

    Halfedge_around_vertex_const_circulator vertex_begin() const {

        // a circulator of halfedges around the vertex (clockwise).
        return Halfedge_around_vertex_const_circulator( this->halfedge());

    }



    // the degree of the vertex, i.e., edges emanating from this vertex 
    std::size_t vertex_degree() const { 

        return this->halfedge()->vertex_degree(); 

    }

    size_type degree() const { return vertex_degree(); } //backwards compatible



    // returns true if the vertex has exactly two incident edges
    bool is_bivalent() const { return  this->halfedge()->is_bivalent(); }



    // returns true if the vertex has exactly three incident edges
    bool is_trivalent() const { return  this->halfedge()->is_trivalent(); }



    // No longer hidden. Now the restricted version with precondition.

    // sets incident halfedge to h. Precondition: h is incident, i.e.,

    // h->vertex() == v.
    void  set_halfedge( Halfedge_handle hh) {
        CGAL_assertion( &*(hh->vertex()) == this);
        Base::set_halfedge(hh);
    }

};