CGAL笔记之单元格复合体和多面体篇—半边数据结构

2023-12-07 19:40
文章标签 数据结构 笔记 单元格 多面体 cgal 半边 复合体

本文主要是介绍CGAL笔记之单元格复合体和多面体篇—半边数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CGAL笔记之单元格复合体和多面体篇—半边数据结构

  • 1 介绍
  • 2 程序设计
  • 3 示例程序
    • 3.1 默认的半边数据结构
    • 3.2 最小半边数据结构
    • 3.3 使用向量而不是列表的默认值
    • 3.4 为面添加颜色的示例
    • 3.5 定义更紧凑的半边的示例
    • 3.6 使用半边迭代器的示例
    • 3.7 构建边缘迭代器的适配器示例

1 介绍

半边数据结构（缩写为HalfedgeDS，或HDS用于模板参数）是一种以边为中心的数据结构，能够维护顶点、边和面的关联信息，例如平面地图、多面体或其他可定向的二维表面嵌入在任意维度。每条边被分解为两个方向相反的半边。每个半边存储一个入射面和一个入射顶点。对于每个面和每个顶点，存储一个关联的半边。半边数据结构的简化变体可以省略其中一些信息，例如面中的半边指针或面的存储。

在这里插入图片描述

halfedge 数据结构是一种组合数据结构，几何解释由建立在 halfedge 数据结构之上的类添加。这些类可能比直接使用 halfedge 数据结构更方便，因为 halfedge 数据结构意味着作为一个实现层。

此处提供的数据结构也称为 FE 结构、halfedges 、或双连接边列表 (DCEL) ，尽管 DCEL 的原始参考描述了不同的数据结构。半边数据结构也可以看作是四边数据结构的变体之一。通常，四边形数据可以表示不可定向的 2-流形，但此处的变体仅限于可定向的 2-流形。

2 程序设计

在这里插入图片描述

图说明了软件设计的三层职责，以Polyhedron_3顶层为例。项为实际存储的信息提供了空间，即在Vertex, Halfedge, 和Face分别。半边需要提供对下一个半边和相对半边的引用。可选地，它们可以提供对先前半边、入射顶点和入射面的参考。顶点和面可能是空的。可选地，它们可以提供对事件 halfedge 的引用。半边数据结构和多面体支持提到的选项，例如，欧拉运算更新可选引用（如果存在）。此外，项目类可以使用任意属性和成员函数进行扩展，这些属性和成员函数将通过继承提升到用于多面体的实际类。

顶点、半边和面作为类的局部类型传递Items给半边数据结构和多面体。提供了满足要求的强制性部分的顶点、半边和面的实现。它们可以用作用户扩展的基类。还提供了更丰富的实现作为默认值；对于多面体，它们提供了所有可选的关联，顶点类型中的三维点和面类型中的平面方程。

Halfedge 数据结构概念HalfedgeDS，负责项目的存储组织。当前，提供了在内部使用双向列表或向量的实现。定义HalfedgeDS属于项的句柄和迭代器。这些类型被提升为项目本身的声明，并在那里用于提供对事件项目的引用。Refs这种类型的提升是通过项目类型的模板参数完成的。halfedge 数据结构提供成员函数来插入和删除项目，遍历所有项目，并提供对项目的访问。

这个HalfedgeDS概念有两种不同的模型，HalfedgeDS_list并且HalfedgeDS_vector，可能还会有更多。因此，我们保持它们的接口较小，并将通用功能分解为单独的辅助类、HalfedgeDS_decorator、HalfedgeDS_const_decorator和HalfedgeDS_items_decorator，它们未在图中显示，但将放置在HalfedgeDS因为他们扩大了界面但没有隐藏它。这些辅助类包含有助于实现下一层操作的操作，例如多面体。例如，他们添加了欧拉运算和部分运算，从中可以构建进一步的欧拉运算，例如在顶点处将边插入到边环中。此外，辅助类包含自适应功能。例如，如果HalfedgeDSHalfedge::prev()没有为 halfedges 提供成员函数，则HalfedgeDS_items_decorator::find_prev()辅助类的成员函数会沿面的正方向搜索前一个 halfedges。但是如果HalfedgeDSHalfedge::prev()提供了成员函数，HalfedgeDS_items_decorator::find_prev()成员函数只是调用它。这种区别在编译时通过称为编译时标记的技术解决，类似于迭代器标签。

作为Polyhedron_3第三层的例子，增加了几何解释，提供了一个易于使用的高级功能接口，并统一了对底层提供的灵活性的访问。它将面重命名为面，这对于三维表面更常见。该界面旨在保护内部表示的完整性，存储在项目中的句柄不能再由用户直接编写。多面体添加了方便高效的环行器，用于访问顶点或小平面周围的圆形边序列。为实现这一点，Polyhedron_3从中提供的那些派生新的顶点、半边和面Items。这些新项目是实际使用的项目HalfedgeDS，这为我们提供了此设计中连贯的类型结构。

3 示例程序

3.1 默认的半边数据结构

以下示例程序使用默认的 halfedge 数据结构和装饰器类。默认的半边数据结构使用基于列表的表示。定义了项目的所有关联和顶点的点类型。trivial traits 类提供了用于点的类型。该程序创建一个循环，由两个半边、一个顶点和两个面组成，并检查其有效性。

在这里插入图片描述

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <cassert>
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_default<Traits> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS> Decorator;
int main() {HDS hds;Decorator decorator(hds);decorator.create_loop();assert( decorator.is_valid());return 0;
}

3.2 最小半边数据结构

以下程序使用最小项类HalfedgeDS_min_items和基于列表的半边数据结构定义了最小半边数据结构。结果是一个数据结构只维护带有 next 和 opposite 指针的半边。没有存储顶点或面。数据结构表示无向图。

#include <CGAL/HalfedgeDS_min_items.h>
#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <cassert>
// no traits needed, argument can be arbitrary dummy.
typedef CGAL::HalfedgeDS_default<int, CGAL::HalfedgeDS_min_items> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
int main() {HDS hds;Decorator decorator(hds);decorator.create_loop();assert( decorator.is_valid());return 0;
}

3.3 使用向量而不是列表的默认值

默认的 halfedge 数据结构在内部使用一个列表和最大基类。我们在这里将列表更改为矢量表示。同样，一个普通的特征类提供了用于点的类型。请注意，对于向量存储，半边数据结构的大小应事先保留，可以使用示例中所示的构造函数或成员函数reserve()。稍后可以通过进一步调用reserve()成员函数来调整数据结构的大小，但前提是数据结构处于一致的状态，即有效状态。

#include <CGAL/HalfedgeDS_items_2.h>
#include <CGAL/HalfedgeDS_vector.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <cassert>
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_vector< Traits, CGAL::HalfedgeDS_items_2> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
int main() {HDS hds(1,2,2);Decorator decorator(hds);decorator.create_loop();assert( decorator.is_valid());return 0;
}

3.4 为面添加颜色的示例

此示例重新使用可用于人脸的基类并添加一个成员变量color。

#include <CGAL/HalfedgeDS_items_2.h>
#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/IO/Color.h>
#include <cassert>
// A face type with a color member variable.
template <class Refs>
struct My_face : public CGAL::HalfedgeDS_face_base<Refs> {CGAL::IO::Color color;My_face() {}My_face( CGAL::IO::Color c) : color(c) {}
};
// An items type using my face.
struct My_items : public CGAL::HalfedgeDS_items_2 {template <class Refs, class Traits>struct Face_wrapper {typedef My_face<Refs> Face;};
};
struct My_traits { // arbitrary point type, not used here.typedef int  Point_2;
};
typedef CGAL::HalfedgeDS_default<My_traits, My_items> HDS;
typedef HDS::Face                                     Face;
typedef HDS::Face_handle                              Face_handle;
int main() {HDS hds;Face_handle f = hds.faces_push_back( Face( CGAL::IO::red()));f->color = CGAL::IO::blue();assert( f->color == CGAL::IO::blue());return 0;
}

3.5 定义更紧凑的半边的示例

此处介绍的半边数据结构的空间效率略低，例如翼边数据结构、DCEL 或四边数据结构的变体。另一方面，它在遍历过程中不需要任何搜索操作。

以下示例使用传统 C 技术（即类型转换和指针，尤其是来自mallocor 的指针new，指向偶数地址的指针）以遍历时间换取紧凑的存储表示。这个想法如下：halfedge 数据结构成对分配 halfedges。关于基于向量的数据结构，这意味着相对于 C 指针算法，半边与其相反的半边之间的差的绝对值始终为 1。我们可以用编码此差异符号的单个位来替换相反的指针。我们将把这个位存储为下一个半边句柄中的最低有效位。此外，我们没有实现指向前半边的指针。剩下的是每个半边三个指针。

我们使用静态成员函数HalfedgeDS::halfedge_handle()将指针转换为半边句柄。相同的解决方案可以应用于基于列表的 halfedge 数据结构HalfedgeDS_list，这是基于向量的数据结构的示例。

#include <CGAL/HalfedgeDS_items_2.h>
#include <CGAL/HalfedgeDS_vector.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <cstddef>
#include <cassert>
// Define a new halfedge class. We assume that the Halfedge_handle can
// be created from a pointer (e.g. the HalfedgeDS is based here on the
// In_place_list or a std::vector with such property) and that halfedges
// are allocated in pairs. We encode the opposite pointer in a single bit,
// which is stored in the lower bit of the next-pointer. We use the
// static member function HDS::halfedge_handle to translate pointer to
// handles.
template <class Refs>
class My_halfedge {
public:typedef Refs                                 HDS;typedef My_halfedge<Refs>                    Base_base;typedef My_halfedge<Refs>                    Base;typedef My_halfedge<Refs>                    Self;typedef CGAL::Tag_false                      Supports_halfedge_prev;typedef CGAL::Tag_true                       Supports_halfedge_vertex;typedef CGAL::Tag_true                       Supports_halfedge_face;typedef typename Refs::Vertex_handle         Vertex_handle;typedef typename Refs::Vertex_const_handle   Vertex_const_handle;typedef typename Refs::Halfedge              Halfedge;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;
private:std::ptrdiff_t  nxt;
public:My_halfedge() : nxt(0), f( Face_handle()) {}Halfedge_handle opposite() {// Halfedge could be different from My_halfedge (e.g. pointer for// linked list). Get proper handle from 'this' pointer first, do// pointer arithmetic, then convert pointer back to handle again.Halfedge_handle h = HDS::halfedge_handle(this); // proper handleif ( nxt & 1)return HDS::halfedge_handle( &* h + 1);return HDS::halfedge_handle( &* h - 1);}Halfedge_const_handle opposite() const { // same as aboveHalfedge_const_handle h = HDS::halfedge_handle(this); // proper handleif ( nxt & 1)return HDS::halfedge_handle( &* h + 1);return HDS::halfedge_handle( &* h - 1);}Halfedge_handle next() {return HDS::halfedge_handle((Halfedge*)(nxt & (~ std::ptrdiff_t(1))));}Halfedge_const_handle next() const {return HDS::halfedge_handle((const Halfedge*)(nxt & (~ std::ptrdiff_t(1))));}void  set_opposite( Halfedge_handle h) {assert(( &* h - 1 == &* HDS::halfedge_handle(this)) ||( &* h + 1 == &* HDS::halfedge_handle(this)));if ( &* h - 1 == &* HDS::halfedge_handle(this))nxt |= 1;elsenxt &= (~ std::ptrdiff_t(1));}void  set_next( Halfedge_handle h) {assert( ((std::ptrdiff_t)(&*h) & 1) == 0);nxt = ((std::ptrdiff_t)(&*h)) | (nxt & 1);}
private:    // Support for the Vertex_handle.Vertex_handle    v;
public:// the incident vertex.Vertex_handle         vertex()                     { return v; }Vertex_const_handle   vertex() const               { return v; }void                  set_vertex( Vertex_handle w) { v = w; }
private:Face_handle      f;
public:Face_handle           face()                       { return f; }Face_const_handle     face() const                 { return f; }void                  set_face( Face_handle g)     { f = g; }bool                  is_border() const { return f == Face_handle(); }
};
// Replace halfedge in the default items type.
struct My_items : public CGAL::HalfedgeDS_items_2 {template <class Refs, class Traits>struct Halfedge_wrapper {typedef My_halfedge<Refs> Halfedge;};
};
struct Traits { typedef int Point_2; };
typedef CGAL::HalfedgeDS_vector<Traits, My_items> HDS;
typedef CGAL::HalfedgeDS_decorator<HDS>  Decorator;
int main() {HDS hds(1,2,2);Decorator decorator(hds);decorator.create_loop();assert( decorator.is_valid());return 0;
}

3.6 使用半边迭代器的示例

在默认的 halfedge 数据结构中创建了两条边。halfedge 迭代器用于计算 halfedges。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <cassert>
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();assert( decorator.is_valid());int n = 0;for ( Iterator i = hds.halfedges_begin(); i != hds.halfedges_end(); ++i )++n;assert( n == 4);  // == 2 edgesreturn 0;
}

3.7 构建边缘迭代器的适配器示例

在默认的 halfedge 数据结构中创建了三个边。适配器N_step_adaptor用于声明用于对边进行计数的边迭代器。

#include <CGAL/HalfedgeDS_default.h>
#include <CGAL/HalfedgeDS_decorator.h>
#include <CGAL/N_step_adaptor.h>
#include <cassert>
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();assert( decorator.is_valid());int n = 0;for ( Iterator e = hds.halfedges_begin(); e != hds.halfedges_end(); ++e)++n;assert( n == 2);  // == 2 edgesreturn 0;
}

这篇关于CGAL笔记之单元格复合体和多面体篇—半边数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/467116。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...
【C++学习笔记 20】C++中的智能指针

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别，使用new关键字创建变量时，需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时，不必自己去调用delete，甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针，是一种作用域指针，意思是当指针超出该作用域时，会自动调用delete。它名为unique的原因是这个
阅读更多...
查看提交历史 —— Git 学习笔记 11

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新，又或者克隆了某个项目之后，你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2