HalfedgeDS_list是 CGALComputational Geometry Algorithms Library中 半边数据结构HalfedgeDS的链表实现是表示多边形网格、多面体等拓扑结构的核心容器底层基于双向链表存储顶点、半边、面等拓扑元素支持动态增删和灵活的拓扑自定义。本实例是通过该数据结构对下图的立方体存储包括点半边面拓扑结构。cpp文件#includeCGAL/HalfedgeDS_list.h #includeCGAL/HalfedgeDS_decorator.h #includeCGAL/Simple_cartesian.h #includeCGAL/HalfedgeDS_items_2.h #includeiostream using namespace std; typedef CGAL::Simple_cartesiandouble Kernel; typedef Kernel::Point_3 Point_3; typedef Kernel::Plane_3 Plane_3; struct My_traits { typedef Point_3 Point_3; typedef Plane_3 Plane_3; }; struct My_items :public CGAL::HalfedgeDS_items_3{ template class Refs, class Traits struct Vertex_wrapper { typedef CGAL::HalfedgeDS_vertex_baseRefs,CGAL::Tag_false,My_traits::Point_3 Vertex; }; template class Refs, class Traits struct Halfedge_wrapper { typedef CGAL::HalfedgeDS_halfedge_baseRefs,CGAL::Tag_false,CGAL::Tag_true,CGAL::Tag_true Halfedge; }; template class Refs, class Traits struct Face_wrapper { typedef CGAL::HalfedgeDS_face_baseRefs,CGAL::Tag_true,My_traits::Plane_3 Face; }; }; typedef CGAL::HalfedgeDS_listMy_traits,My_items HDS; typedef CGAL::HalfedgeDS_decoratorHDS Decorator; typedef HDS::Vertex_handle Vertex_handle; typedef HDS::Face_handle Face_handle; typedef HDS::Halfedge_handle Halfedge_handle; typedef HDS::Vertex Vertex; typedef HDS::Halfedge Halfedge; typedef HDS::Face Face; void test10() { HDS hds; Decorator decorator(hds); Vertex V0(Point_3(0,0,0)); Vertex V1(Point_3(1,0,0)); Vertex V2(Point_3(0,1,0)); Vertex V3(Point_3(1,1,0)); Vertex V4(Point_3(0,0,1)); Vertex V5(Point_3(1,0,1)); Vertex V6(Point_3(0,1,1)); Vertex V7(Point_3(1,1,1)); Vertex_handle v0 hds.vertices_push_back(V0); Vertex_handle v1 hds.vertices_push_back(V1); Vertex_handle v2 hds.vertices_push_back(V2); Vertex_handle v3 hds.vertices_push_back(V3); Vertex_handle v4 hds.vertices_push_back(V4); Vertex_handle v5 hds.vertices_push_back(V5); Vertex_handle v6 hds.vertices_push_back(V6); Vertex_handle v7 hds.vertices_push_back(V7); Halfedge he01, he10; Halfedge_handle he01_handle hds.edges_push_back(he01, he10); Halfedge_handle he10_handle he01_handle-opposite(); he01_handle-set_vertex(v0); he10_handle-set_vertex(v1); Halfedge he02, he20; Halfedge_handle he02_handle hds.edges_push_back(he02,he20); Halfedge_handle he20_handle he02_handle-opposite(); he02_handle-set_vertex(v0); he20_handle-set_vertex(v2); Halfedge he04, he40; Halfedge_handle he04_handle hds.edges_push_back(he04,he40); Halfedge_handle he40_handle he04_handle-opposite(); he04_handle-set_vertex(v0); he40_handle-set_vertex(v4); Halfedge he13, he31; Halfedge_handle he13_handle hds.edges_push_back(he13,he31); Halfedge_handle he31_handle he13_handle-opposite(); he13_handle-set_vertex(v1); he31_handle-set_vertex(v3); Halfedge he15, he51; Halfedge_handle he15_handle hds.edges_push_back(he15,he51); Halfedge_handle he51_handle he15_handle-opposite(); he15_handle-set_vertex(v1); he51_handle-set_vertex(v5); Halfedge he23, he32; Halfedge_handle he23_handle hds.edges_push_back(he23, he32); Halfedge_handle he32_handle he23_handle-opposite(); he23_handle-set_vertex(v2); he32_handle-set_vertex(v3); // 边 V2-V6 Halfedge he26, he62; Halfedge_handle he26_handle hds.edges_push_back(he26, he62); Halfedge_handle he62_handle he26_handle-opposite(); he26_handle-set_vertex(v2); he62_handle-set_vertex(v6); // 边 V3-V7 Halfedge he37, he73; Halfedge_handle he37_handle hds.edges_push_back(he37, he73); Halfedge_handle he73_handle he37_handle-opposite(); he37_handle-set_vertex(v3); he73_handle-set_vertex(v7); // 边 V4-V5 Halfedge he45, he54; Halfedge_handle he45_handle hds.edges_push_back(he45, he54); Halfedge_handle he54_handle he45_handle-opposite(); he45_handle-set_vertex(v4); he54_handle-set_vertex(v5); // 边 V4-V6 Halfedge he46, he64; Halfedge_handle he46_handle hds.edges_push_back(he46, he64); Halfedge_handle he64_handle he46_handle-opposite(); he46_handle-set_vertex(v4); he64_handle-set_vertex(v6); // 边 V5-V7 Halfedge he57, he75; Halfedge_handle he57_handle hds.edges_push_back(he57, he75); Halfedge_handle he75_handle he57_handle-opposite(); he57_handle-set_vertex(v5); he75_handle-set_vertex(v7); // 边 V6-V7 Halfedge he67, he76; Halfedge_handle he67_handle hds.edges_push_back(he67, he76); Halfedge_handle he76_handle he67_handle-opposite(); he67_handle-set_vertex(v6); he76_handle-set_vertex(v7); Face f1, f2, f3, f4, f5, f6; he01_handle-set_next(he13_handle); he13_handle-set_next(he32_handle); he32_handle-set_next(he20_handle); he20_handle-set_next(he01_handle); //0132 Face_handle f1_handle hds.faces_push_back(f1); f1_handle-set_halfedge(he01_handle); he01_handle-set_face(f1_handle); he13_handle-set_face(f1_handle); he32_handle-set_face(f1_handle); he20_handle-set_face(f1_handle); he10_handle-set_next(he04_handle); he04_handle-set_next(he45_handle); he45_handle-set_next(he51_handle); he51_handle-set_next(he10_handle); //1045 Face_handle f3_handle hds.faces_push_back(f3); f3_handle-set_halfedge(he10_handle); he10_handle-set_face(f3_handle); he04_handle-set_face(f3_handle); he45_handle-set_face(f3_handle); he51_handle-set_face(f3_handle); he31_handle-set_next(he15_handle); he15_handle-set_next(he57_handle); he57_handle-set_next(he73_handle); he73_handle-set_next(he31_handle); //3157 Face_handle f5_handle hds.faces_push_back(f5); f5_handle-set_halfedge(he31_handle); he31_handle-set_face(f5_handle); he15_handle-set_face(f5_handle); he57_handle-set_face(f5_handle); he73_handle-set_face(f5_handle); he23_handle-set_next(he37_handle); he37_handle-set_next(he76_handle); he76_handle-set_next(he62_handle); he62_handle-set_next(he23_handle); //2376 Face_handle f4_handle hds.faces_push_back(f4); f4_handle-set_halfedge(he23_handle); he23_handle-set_face(f4_handle); he37_handle-set_face(f4_handle); he76_handle-set_face(f4_handle); he62_handle-set_face(f4_handle); he02_handle-set_next(he26_handle); he26_handle-set_next(he64_handle); he64_handle-set_next(he40_handle); he40_handle-set_next(he02_handle); //0264 Face_handle f6_handle hds.faces_push_back(f6); f6_handle-set_halfedge(he02_handle); he02_handle-set_face(f6_handle); he26_handle-set_face(f6_handle); he64_handle-set_face(f6_handle); he40_handle-set_face(f6_handle); he54_handle-set_next(he46_handle); he46_handle-set_next(he67_handle); he67_handle-set_next(he75_handle); he75_handle-set_next(he54_handle); //5467 Face_handle f2_handle hds.faces_push_back(f2); f2_handle-set_halfedge(he54_handle); he54_handle-set_face(f2_handle); he46_handle-set_face(f2_handle); he67_handle-set_face(f2_handle); he75_handle-set_face(f2_handle); //5467 assert(decorator.is_valid()); } int main() { test10(); return 0; }可以看到这样很麻烦CGAL提供更方便的方式。通过polyhedron_3提供的欧拉算子下图展示了将一个四面体通过拓扑操作变换为一个六面体的过程。#include CGAL/Simple_cartesian.h #include CGAL/Polyhedron_3.h #include iostream template class Poly typename Poly::Halfedge_handle make_cube_3( Poly P) { // appends a cube of size [0,1]^3 to the polyhedron P. CGAL_precondition( P.is_valid()); typedef typename Poly::Point_3 Point; typedef typename Poly::Halfedge_handle Halfedge_handle; Halfedge_handle h P.make_tetrahedron( Point( 1, 0, 0), Point( 0, 0, 1), Point( 0, 0, 0), Point( 0, 1, 0)); Halfedge_handle g h-next()-opposite()-next(); // Fig. (a) P.split_edge( h-next()); P.split_edge( g-next()); P.split_edge( g); // Fig. (b) h-next()-vertex()-point() Point( 1, 0, 1); g-next()-vertex()-point() Point( 0, 1, 1); g-opposite()-vertex()-point() Point( 1, 1, 0); // Fig. (c) Halfedge_handle f P.split_facet( g-next(), g-next()-next()-next()); // Fig. (d) Halfedge_handle e P.split_edge( f); e-vertex()-point() Point( 1, 1, 1); // Fig. (e) P.split_facet( e, f-next()-next()); // Fig. (f) CGAL_postcondition( P.is_valid()); return h; } typedef CGAL::Simple_cartesiandouble Kernel; typedef CGAL::Polyhedron_3Kernel Polyhedron; typedef Polyhedron::Halfedge_handle Halfedge_handle; int main() { Polyhedron P; Halfedge_handle h make_cube_3( P); return (P.is_tetrahedron(h) ? 1 : 0); }Polyhedron_3的底层采用的就是半边数据结构这个过程其实是通过半边数据结构的装饰器decorator实现的。