当前位置： 首页 > news >正文

使用CGAL的半边数据结构HalfedgeDS_list构建一个立方体

news 2026/4/10 19:18:20

HalfedgeDS_list是 CGAL（Computational Geometry Algorithms Library）中 半边数据结构（HalfedgeDS）的链表实现，是表示多边形网格、多面体等拓扑结构的核心容器，底层基于双向链表存储顶点、半边、面等拓扑元素，支持动态增删和灵活的拓扑自定义。

本实例是通过该数据结构对下图的立方体存储，包括点，半边，面，拓扑结构。

cpp文件

#include<CGAL/HalfedgeDS_list.h> #include<CGAL/HalfedgeDS_decorator.h> #include<CGAL/Simple_cartesian.h> #include<CGAL/HalfedgeDS_items_2.h> #include<iostream> using namespace std; typedef CGAL::Simple_cartesian<double> 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_base<Refs,CGAL::Tag_false,My_traits::Point_3> Vertex; }; template <class Refs, class Traits> struct Halfedge_wrapper { typedef CGAL::HalfedgeDS_halfedge_base<Refs,CGAL::Tag_false,CGAL::Tag_true,CGAL::Tag_true> Halfedge; }; template <class Refs, class Traits> struct Face_wrapper { typedef CGAL::HalfedgeDS_face_base<Refs,CGAL::Tag_true,My_traits::Plane_3> Face; }; }; typedef CGAL::HalfedgeDS_list<My_traits,My_items> HDS; typedef CGAL::HalfedgeDS_decorator<HDS> 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_cartesian<double> Kernel; typedef CGAL::Polyhedron_3<Kernel> 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实现的。

http://www.jsqmd.com/news/449511/

相关文章：

  • ez-rce
  • [AI-Talk] OpenClaw如何实现直播评论
  • AI助教新实践：Nanbeige 4.1-3B实现自动化作业批改与反馈
  • 人工智能+AI的微信小程序的考研交流系统
  • nanobot效果展示：Qwen3-4B在Chainlit中解析图片URL、执行shell命令案例
  • CosyVoice-300M Lite应用分享：无障碍服务中的语音导航实现
  • 撤销工作表保护密码破解/工作簿密码破解,考勤表无法编辑？考勤表无法修改？有办法找回密码。
  • Qwen1.5-1.8B GPTQ一键部署体验：对比重装系统与镜像部署效率
  • 为什么有人连操作系统的基本知识都不懂？
  • 【UI自动化测试】1_TPshop项目实战 _项目介绍（重点）
  • 基于声波，超声波和振动传感器三位一体的多模态变电站出厂检测有市场吗？
  • 微信私域自动化
  • 万象熔炉 | Anything XL效果展示：多光源场景下阴影过渡与材质反射效果
  • 智慧物流已成标配：2026年主流AGV叉车厂家市场竞争力和行业格局全景解析 - 品牌推荐
  • 题解：CF2201B Recollect Numbers
  • 2026年制造业选型必看：AMR搬运机器人厂家适配指南与核心指标实测对比 - 品牌推荐
  • 小白也能搞定：ResNet18通用物体识别镜像一键部署指南
  • 基于声波，超声波和振动传感器三位一体的多模态变电站出厂检测市场前景
  • 基于 Qt 实现多客户端 TCP 通信聊天室
  • 全文搜索终极对决：Elasticsearch与Solr核心选型指南
  • 2026年AMR搬运机器人厂家权威榜单发布：五大品牌技术实力深度排位赛 - 品牌推荐
  • 阿里MGeo模型实战：10分钟学会地址匹配，告别人工比对
  • 2026年制造企业选型必看：AGV叉车厂家选购指南与四大核心能力实测 - 品牌推荐
  • 2026年AMR搬运机器人厂家深度测评：基于导航精度与交付效率的五维战力解析 - 品牌推荐
  • Gemini如何解决办公难题：从“工具”到“协作者”的认知升级
  • 用Wan2.2-T2V-A5B做教育动画：自动生成教学演示小片段
  • Qwen3-TTS-VoiceDesign开源镜像实操手册：免配置Docker化部署+Gradio Web快速体验
  • Linux I/O多路复用：深入浅出poll与epoll
  • StructBERT中文相似度模型保姆级教程：Sentence Transformers环境配置
  • 开发者一站式效率工具站，JSON 处理 + 开发调试全搞定