CGAL功能大纲 - HelloWorld开发者社区

算术与代数Arithmetic and Algebra

主要提供了计算几何用到的数学基础：数据类型、多项式、数据结构与算法

代数基础Algebraic Foundations

这个包从概念、类和函数的角度定义了代数对CGAL的意义。

数据类型Number Types

这个包为第三方数据类型库提供数据类型概念以及数据类型类和包装器类。

模运算Modular Arithmetic

这个包提供了有限域的算法。所提供的工具对于基于模块化算法的过滤器和基于余数的算法尤其有用。

多项式Polynomial

这个包介绍了单变量多项式和多变量多项式的概念。虽然这个概念是为任意数量的变量编写的，但是对于这个概念的特定模型，变量的数量被认为是固定的。

代数框架Algebraic Kernel

解多项式的实解是一个应用范围很广的基本问题。这个包的目标是提供最先进算法的黑盒实现，以逼近或近似的求解出单变量多项式和双变量多项式的真实根。这种黑盒称为代数框架。到目前为止，这个包只提供了单变量内核的模型。尽管如此，它已经定义了双变量内核的概念，因为这解决了即将实现的接口问题。

组合算法Combinatorial Algorithms

主要讲述计算几何用到的数学基础：矩阵搜索、线性和二次规划求解器

单调有序矩阵搜索Monotone and Sorted Matrix Search

这个包提供了一个矩阵搜索框架，它是计算凸多边形顶点的所有最远邻居、内接到平面点集的最大k-gons和计算矩形p中心的基础技术。

线性和二次规划求解器Linear and Quadratic Programming Solver

这个包提供了最小化线性和凸二次函数在多面域的算法，由线性方程和不等式描述。算法是精确的，因为最终解是用多精度有理数来计算的。所得到的解决方案是经过验证的，除了所考虑的问题具有最优解、不可行或无界外，算法还提供了这些事实的证明。这些证明可以很容易地(独立于算法)检查正确性。

几何框架Geometry Kernels

主要讲述计算几何中如何表达几何模型

二维和三维线性几何框架2D and 3D Linear Geometry Kernel

这个包提供了多个几何框架，每个框架包含大小不变的对象，例如点、向量、方向、线、射线、段、圆以及这些对象的构造和操作。每个框架处理的健壮性问题不同。

多维度几何框架dD Geometry Kernel

多维度几何框架包含大小恒定的对象，如多维度欧氏空间中的点、向量、方向、线、射线、段、圆等，以及这些对象的构造和操作。

二维圆形几何框架2D Circular Geometry Kernel

这个包是线性CGAL框架的扩展。它在平面上提供圆、圆弧和线段的功能。目标是为用户提供平面上圆形和圆弧的大量功能。包里定义了计算圆弧和这些线段的排列所需的所有功能。为CGAL排列模块提供了三个trait类。

三维球形几何框架3D Spherical Geometry Kernel

这个包是线性CGAL内核的扩展。它提供了在三维空间或限制在参考球面上的球面、圆、圆弧和线段的功能。目标是在三维空间或给定球面上，为用户提供一组关于球面、圆和圆弧的函数。这些功能需要对数据进行计算，这将推动创建一个新的内核概念，扩展CGAL内核概念，该概念仅限于FieldNumberType中的对象和功能。

凸包算法Convex Hull Algorithms

主要讲述二维、三维以及高维度模型的凸包算法

二维凸包和极值点2D Convex Hulls and Extreme Points

这个包提供了计算二维凸壳的函数，以及检查点集是否是强凸的函数。此外，还描述了一些用于计算船体点的特定极值点和子序列的函数，如一组点的上、下船体。

三维凸包3D Convex Hulls

这个包提供了计算三维凸壳的函数，以及检查点集是否是强凸的函数。可以用两种方法在三维空间中计算一组点的凸包：静态凸包构建算法和动态凸包构建。

多维凸包和三角剖分dD Convex Hulls and Delaunay Triangulations

这个包提供了在多维度欧氏空间中计算凸壳和Delaunay三角的函数。

二维多边形Polygons

主要讲述二维多边形相关概念和算法：二维多边形正则布尔集运算、二维多边形凸划分、多边形缓冲区、二维直骨架、二维闵可夫斯基之和、二维多段线简化、二维可视域计算、二维可移动性分析

二维多边形2D Polygons

这个包定义了二维多边形类的基本概念和数据结构，提供了多边形的构建，并提供了相关操作，比如边界框、极值点、有符号区域、简单性和凸性测试、方向和点位置。

二维正则布尔集运算2D Regularized Boolean Set-Operations

这个包提供了在二维欧氏空间中对由弱x单调曲线约束的点集进行布尔集运算的实现。特别是，它包含了正则布尔集操作、交集谓词和点包含谓词的实现。

二维布尔运算2D Boolean Operations on Nef Polygons

Nef多边形是通过集合补和集合交运算从有限半空间集合中得到的任意集合。由于并集、差分和对称差分等所有二元集合运算都可以简化为求交和补的运算，所以Nef多边形在这些运算下也是封闭的。除了集合补运算外，还有更多的拓扑一元集运算是在Nef多边形的内部、边界和闭包域中封闭的。

对嵌在球面上的Nef多边形进行二维布尔运算2D Boolean Operations on Nef Polygons Embedded on the Sphere

这个包提供了相当于平面上的二维Nef多边形。这里的半平面相当于由大圆分隔的半球体。

二维模型凸分解2D Polygon Partitioning

这个包提供了将多边形划分为单调多边形或凸多边形的函数。该算法可以在多边形数最少的情况下得到结果，也可以在凸块数不超过最优凸块数四倍的情况下得到近似结果，但它们在运行时的复杂性有所不同。

二维直骨架与缓冲2D Straight Skeleton and Polygon Offsetting

这个包提供了构造一个表示二维带孔多边形内部直线骨架的halfedge数据结构，以及构造给定直线骨架的任意偏移距离的向内偏移多边形。

**[带洞多边形拓扑规定]**一个有洞的二维多边形称之为外轮廓，在其有界区域内有零个或多个轮廓，称为内轮廓或洞或孔。外轮廓的有界区域与内轮廓的无界区域的交点是带孔多边形的内部。孔的方向必须与外轮廓的方向相反，任何轮廓之间不能有交集。一个孔不能在任何其他孔的有界区域内。

2D Straight Skeleton 2D Polygon Offsetting

二维闵可夫斯基之和2D Minkowski Sums

这个包由计算平面上两个简单多边形的闵可夫斯基和的函数组成。它还包含计算多边形和圆盘的闵可夫斯基和的函数，这种操作称为多边形偏移或扩张。该包可以计算偏移多边形的精确表示，或提供一个保证的近似偏移量。

二维线简化2D Polyline Simplification

这个包可以简化折线，同时保证折线的拓扑结构不会改变。这可以用于单个折线，也可以用于约束三角剖分中的一组折线约束。简化过程可以通过权重进行控制功能。

二维可视域计算2D Visibility Computation

这个包提供了几个变量来计算二维多边形区域内一个点的可见面积。

2D Movable Separability of Sets

集合的可动可分性是处理物体移动集合的问题，如平面上的多边形，在考虑不同类型的运动和不同的分离定义时，如何避免物体之间的碰撞是一个难题。

复合体和多面体Cell Complexes and Polyhedra

主要讲述三维多面体的数据结构：半边结构、三角网表面、二维流向结构、闭合性、三维多边形正则布尔集运算、三维多边形凸划分、三维闵可夫斯基之和

三维多面体表面3D Polyhedral Surface

三维多面体表面由顶点、边、面片及其上的关联关系组成。下面的组织是一个halfedge数据结构，它将可表示曲面类限制为可定向的2流形——有边界和没有边界。如果曲面是闭合的，称之为多面体。

半边结构Halfedge Data Structures

halfedge数据结构是以边为中心的数据结构，能够维护顶点、边和面的关联信息，例如平面地图、多面体或嵌入任意维的其他可定向二维表面。每条边分解成两个方向相反的半棱。每个半网格中存储一个入射面和一个入射顶点。对于每个面和每个顶点，存储一个入射半边缘。halfedge数据结构的简化变体可以省略其中一些信息。

表面网格Surface Mesh

这个包提供的曲面网格类是halfedge数据结构的一个实现，它允许表示多面体曲面。它是一个替代包Halfedge数据结构和三维多面体表面。主要的区别在于，它是基于索引而不是基于指针的，并且向顶点、半边、边和面添加信息的机制要简单得多，可以在运行时使用，而不是在编译时使用。

Combinatorial Maps ？？
Generalized Maps ？？
Linear Cell Complex ？？
布尔运算3D Boolean Operations on Nef Polyhedra

三维Nef多面体是一种以halfedge数据结构为界的复合体的边界表示，它支持布尔运算和全通用性的拓扑运算，包括无界模型、混合维度模型(如孤立的顶点和天线)。Nef多面体区分开集和闭集，可以表示非流形几何。

在实体建模中，使用了两种主要的表示方案:构造实体几何(CSG)和边界表示(B-rep)。两者都有优点和缺点。

在CSG中，实体表示为基本实体对象（如块、棱镜、柱面或环面）的布尔组合。对象用树结构隐式表示，叶节点表示原始对象，内部节点表示布尔运算或刚性运动（如平移和旋转）。在这种CSG树上的算法首先评估基本对象上的属性，然后使用树结构推算结果。

B-rep描述实体边界所有低维特征的入射结构和几何性质。表面的朝向决定了固体的内部和外部。

CSG中可表示对象的类别通常受到基本实体选择的限制。B-rep通常受限于边缘支撑曲线几何形状和表面贴片支撑曲面几何形状的选择，以及允许的连接性结构。特别是，B-rep在布尔集操作下并不总是关闭。例如，可定向2流形对象的类是B-reps常用的一类表面，这类表面很受欢迎，也很容易理解。它们可以被有效地表示和操作，数据结构在存储大小上是紧凑的，许多算法是简单的。另一方面，这个对象类在布尔集合操作下是不封闭的，很多例子都可以说明这一点，如上图所示，它可以使用多维数据集上的布尔集合操作生成。包围隧道的顶点，或连接"屋顶"与立方体的边缘是非流形情况。

在3D Nef多面体实现中，提供了B-rep数据结构，它在布尔操作下是封闭的，并且具有通用性。可以从halfspaces （也可以直接从面向2-流形）开始，进行集并集、集交集、集差集、集补集、内、外、边界、闭包和正则化操作。从本质上说，可以计算一个以halfspaces为基元的CSG树，并将其转换为B-rep表示。

实际上，CGAL使用的是两种数据结构，它表示顶点的局部邻域，本身就是一个完整的描述，以及一个数据结构，并将这些邻域连接到具有边edges、面facet和体volumes的全局数据结构。提供了丰富的接口来研究这些数据结构、它们的不同元素及其连接性。提供了仿射(刚性)转换和点位置查询操作。提供了一个自定义的文件格式，用于存储和读取文件中的Nef多面体。

三维模型凸分解Convex Decomposition of Polyhedra

这个包提供了一个将有界多面体分解为凸子多面体的函数。分解得到O(r2)凸块，其中r为边数，其相邻面相对于多面体内部形成180度以上的角度。这个界限是最坏情况下最优的。

三维闵可夫斯基之和3D Minkowski Sum of Polyhedra

这个包提供了一个函数，它计算R3中两个点集的闵可夫斯基之和。这些点集可以由孤立的顶点、孤立的边、没有孔的凸面和开闭固体组成。因此，可以计算平移机器人的配置空间(即使是在狭窄的通道场景中)以及一些图形操作，例如滑翔操作，它计算沿多边形线移动的多面体扫过的点集。

排列Arrangements

这个模块提供了空间排列的方法，使得能够快速查找定位

二维排列2D Arrangements

此包可用于构造、维护、更改和显示平面中的排列。一旦构建了排列，就可以使用这个包来获得关于该排列的各种查询的结果，例如点位置。该包还包括两个算法框架的通用实现，即计算一个排列的区域和在平面上扫线，排列是嵌入的。这些框架依次用于排列上的其他操作的实现。例如，计算两种排列的叠加是基于扫描线框架的。还可以扩展排列和排利组件来存储额外的数据。一个重要的扩展存储了布局的构造历史，这样就可以获得布局子曲线的原始曲线。

二维相交曲线2D Intersection of Curves

这个包提供了三个基于扫描线范例实现的免费功能：给定一组输入曲线，计算所有交集点；计算出相交与相离的子曲线，并检查是否有至少其中一条曲线相交在内部。

二维网格对其2D Snap Rounding

单元四舍五入是一种将任意精度的分段排列转换为固定精度表示的方法。在健壮性几何计算的研究中，它可分为一种有限精度逼近技术。迭代单元四舍五入是单元四舍五入的一种修改，其中每个顶点与任何非关联边之间的距离至少为0.5像素。这个包支持这两种方法。

二维轮廓2D Envelopes

这个包由一些函数组成，这些函数在二维中计算一组任意曲线的下(或上)包络线。输出用包络图表示，即将x轴细分为区间，这样在每个区间上诱导包络线的曲线的恒等式就是唯一的。

三维轮廓3D Envelopes

这个包由计算一组任意曲面的三维上(或下)包络线的函数组成。输出被表示为一个二维包络图，也就是一个平面细分，使得在每个图单元上对应包络线的表面的标识是唯一的。

三角化Triangulations and Delaunay Triangulations

这个模块主要提供二维、三维以及高维度数据三角剖分的函数

二维三角剖分2D Triangulation

这个包允许构建和处理二维点集的各种三角关系。任何CGAL三角剖分都覆盖其顶点的凸包。三角形是增量构建的，可以通过插入或删除顶点进行修改。包提供了简单的三角剖分(其面取决于顶点的插入顺序)和Delaunay三角剖分。还提供了加权点集的规则(Regular)三角剖分。Delaunay和规则三角剖分提供了最近邻查询和构建双Voronoi和power图。最后，约束三角剖分和Delaunay约束三角剖分允许强制一些约束段作为三角形的边缘出现。提供了几个版本的约束三角剖分和Delaunay约束三角剖分：其中一些处理输入约束段之间的交集，而另一些则不处理。

二维三角剖分数据结构2D Triangulation Data Structure

这个包提供了一个数据结构来存储具有二维球面拓扑结构的二维三角剖分。包充当三角剖分顶点和面的容器，并提供三角剖分的基本组合操作。

二维周期性三角剖分2D Periodic Triangulations

这个包允许在二维平面环面上构建和处理点集的三角关系。三角形是增量构建的，可以通过插入或删除顶点进行修改。他们提供点位设施。该包提供了Delaunay三角剖分，并提供了构建双Voronoi图的最近邻查询和原语。

三维三角剖分3D Triangulations

这个包允许构建和处理三维点集的三角关系。任何CGAL三角剖分都覆盖其顶点的凸包。三角形是增量构建的，可以通过插入、位移或删除顶点来修改。他们提供点位设施。包提供了简单的三角剖分(其面取决于顶点的插入顺序)和Delaunay三角剖分。还提供了加权点集的规则三角剖分。Delaunay和规则三角剖分提供了最近邻查询和原语来构建双Voronoi和power图。此外，主要的Delaunay和常规三角剖分算法(插入、删除)支持多核共享内存架构，以利用可用的并行性。

三维三角剖分数据结构3D Triangulation Data Structure

这个包提供了一个数据结构来存储具有三维球体拓扑结构的三维三角剖分。包充当三角剖分顶点和单元格的容器，并提供三角剖分的基本组合操作。

三维周期性三角剖分3D Periodic Triangulations

这个包允许在三维平面环面上构建和处理点集的三角关系。三角形是增量构建的，可以通过插入或删除顶点进行修改。他们提供点位设施。该包提供Delaunay和常规三角剖分，并提供最近邻查询和原语来构建双Voronoi图。

多维度三角剖分dD Triangulations

这个包提供了在欧几里得空间中操作三角函数(纯单纯复合体)的类，这些类的维数可以在编译时或运行时指定。具体来说，它提供了一个数据结构来存储三角形，以及两个类来处理点集的三角化和Delaunay三角剖分。支持点定位和点插入。Delaunay三角剖分也支持点删除。

二维2D Alpha Shapes

假设有一组二维或三维的点，我们希望得到"这些点形成的形状"。这是相当模糊的概念,有许多可能的解释,α-shape是其中之一。Alpha形状可用于从密集的无组织数据点集进行形状重建。事实上,α-shape划定的边界,这是一个线性近似的原始形状。

这个包提供了一个数据结构，它编码了与给定的2D Delaunay或规则三角剖分相关的所有alpha复合体。特别是该数据结构允许检索任意alpha值的alpha复合体、关键alpha值的整个频谱以及三角剖分面上的筛选。

三维3D Alpha Shapes

这个包提供了一个数据结构，可以编码一个字母复合体，也可以编码与给定的3D Delaunay或规则三角剖分相关的整个字母复合体系列。在后一种情况下，数据结构允许检索任意alpha值的alpha复合体、关键alpha值的整个频谱以及三角剖分面上的筛选。

泰森多边形Voronoi Diagrams

此模块提供了泰森多边形的构建和应用

二维段Delaunay 图2D Segment Delaunay Graphs

这个包用于计算平面上一组可能相交的段的Delaunay图，提供了一种在欧几里得度量下计算一组段的Voronoi图对偶的算法。它是点的标准Voronoi图的推广。所提供的算法是动态增量的。

无穷Delaunay 图L Infinity Segment Delaunay Graphs

计算算法和几何特征的双重泰森多边形法图的一组点和下段L∞ 指标。

二维Apollonius图（Delaunay圆盘图）2D Apollonius Graphs (Delaunay Graphs of Disks)

计算二维Apollonius图的算法。Apollonius graph是Apollonius diagram的对偶图，也被称为加性加权Voronoi diagram。后者可以看作是欧几里得度量下的一组圆盘的Voronoi图，是点的标准Voronoi图的推广。所提供的算法是动态的。

二维Voronoi图适配器2D Voronoi Diagram Adaptor

2D Voronoi图适配器包提供了一个适配器，该适配器将二维三角化的Delaunay图转换为相应的Voronoi图，表示为双连通边缘列表(DCEL)数据结构。适配器能够以一致的方式自动消除Voronoi图的退化特征，这些特征是要求Delaunay图即使在退化配置中也应该三角化的工件。根据底层Delaunay图支持的操作类型，适配器允许增量或动态构建Voronoi图，并支持点位置查询。

网格生成Mesh Generation

此模块包含了模型网格生成构建的方法

二维三角化和网格2D Conforming Triangulations and Meshes

这个包实现了一个Delaunay细分算法来构造符合要求的三角化二维网格。细化约束边，得到符合条件的Delaunay三角形。通过进一步细化约束边得到符合的Gabriel三角形，直到它们成为Gabriel三角形。该包还提供了一个2D网格生成器，用于细化三角形和约束边，直到满足用户定义的三角形大小和形状标准。生成的网格可以使用Lloyd算法进行优化，该算法也在这个包中提供。该包可以处理交叉输入约束，并且不限制共享端点的两个约束形成的角度。

如果三角剖分的结果是任意一个三角形组成的外接圆内部不包含其他顶点，则称之为一个Delaunay三角剖分。受约束的Delaunay三角剖分的任意面围成的圆在其内部不包含从该面可见的数据点。

如果一条边内切成一个空圆(其内部不包含任何数据点)，则称其为Delaunay边。如果直径圆为空，则称这条边为Gabriel边。

如果每个约束边都是Delaunay边，则约束Delaunay三角剖分就称为符合条件的Delaunay三角剖分。因为约束Delaunay三角剖分中的任意一条边要么是Delaunay边，要么是约束边，所以符合条件的Delaunay三角剖分实际上就是Delaunay三角剖分。唯一的区别是一些边被标记为受约束的边。

如果每个有约束的边都是Gabriel边，则一个有约束的Delaunay三角剖分也被称为符合Gabriel三角剖分。Gabriel性质强于Delaunay性质，每条Gabriel边都是Delaunay边。因此，符合Gabriel三角关系也就符合Delaunay三角关系。

任何有约束的Delaunay三角剖分都可以被细化为符合Delaunay三角剖分或者符合Gabriel三角剖分，方法是在有约束的边上添加顶点，称为Steiner顶点，直到它们被分解成足够小的子约束，成为Delaunay或Gabriel边。

三维表面生成3D Surface Mesh Generation

这个包提供了一些生成插值光滑表面的曲面网格的函数。该网格划分算法是基于Delaunay精细化算法，对生成的网格提供了一定的保证:用户可以控制网格元素的大小和形状，以及曲面逼近的精度。输入表面的拓扑结构和组件数量没有限制。表面网格发生器也可用于非光滑表面，但没有保证。目前，隐式曲面描述为一些函数的零水平集，曲面描述为三维图像中的灰度水平集。

三维表面网格构建3D Skin Surface Meshing

这个包允许建立一个表面的三角形网格。表面用于生物计算中的大分子建模。表面是由一组球来定义的，这些球代表分子的原子，而收缩因子决定了将这些球粘在一起的光滑斑块的大小。为了进一步分析和快速可视化，光滑皮肤表面的三角形网格的构造通常是必要的。这个包提供了一些函数来构造一个三角形网格，该网格从一组球和一个收缩因子来近似皮肤表面。它还包含有效细分网格的代码。

三维网格生成3D Mesh Generation

这个包致力于生成离散三维域的各向同性单纯网格。要网格化的域是一个必须有界的三维空间区域。该区域可以连接或由多个组件或细分在几个子域中。域作为输入，能够回答域上的一些不同类型的查询。边界和细分曲面或光滑或分段光滑，由平面或曲面斑块形成。表面可能表现出一维特征(如折痕边缘)和零维特征(如作为角尖、尖端或飞镖的奇异点)，这些特征在网格中必须相当近似。此外，这些算法还支持多核共享内存架构，以利用可用的并行性。

三维规律性网格生成3D Periodic Mesh Generation

这个包致力于生成离散周期性三维域的各向同性单纯网格。拟网格域是三维平面环面的一个区域。周期性网格生成器为用户提供了与3D网格生成包相同的灵活性。

形状重构Shape Reconstruction

此模块提供了几种模型形状构建的方法。

泊松表面重建Poisson Surface Reconstruction

这个包实现了一个曲面重建方法:泊松曲面重建。它以一组有向法线的点作为输入，并计算一个隐式函数。然后可以使用CGAL表面网格生成器从这个函数中提取等值面。

尺度空间表面重建Scale-Space Surface Reconstruction

这种方法允许重建一个表面插值一组三维点使用和alpha形状或前进的前表面重建方法。输出插值点集(与近似点集相反)。表面如何连接这些点取决于一个比例变量，它可以半自动地估计。

推进前表面重建Advancing Front Surface Reconstruction

这个包提供了一个贪婪的算法，从一个无组织的点集重建曲面。首先添加最可信的三角形，避免拓扑奇点的出现。

Optimal Transportation Curve Reconstruction

这个程序包提供了一种算法，可以从平面上的一个点集重构和简化形状，该点集可能受到噪声和异常值的影响。它生成一组线段和孤立点的输出，这些线段和孤立点近似于输入点集。

模型处理Geometry Processing

网格处理Polygon Mesh Processing

这个包提供了多边形网格处理的方法和类的集合，从简单的基本操作到复杂的几何处理算法。

表面细分3D Surface Subdivision Methods

细分方法递归地细化控制网格，生成逼近极限曲面的点。这个包由四种常用的细分方法及其细化主机组成。支持包括Catmull-Clark细分方法,循环,Doo-Sabin和根号3细分。

网格分区Triangulated Surface Mesh Segmentation

这个程序包提供了一种生成三角曲面网格分割的方法。该算法首先计算所有切面的形状直径函数(SDF)，并在这些值上应用基于图形切割的算法。提供了低级函数来用自定义步骤替换任何中间步骤。

网格简化Triangulated Surface Mesh Simplification

这个程序包提供了一种通过折叠边来简化三角曲面网格的算法。它是Turk/Lindstrom无记忆曲面网格简化算法的实现。

网格变形Triangulated Surface Mesh Deformation

这个包提供了曲面网格变形算法，该算法在一些顶点的位置约束下为曲面网格的顶点提供新的位置，而不需要除了曲面网格本身之外的任何其他结构。

网格参数化Triangulated Surface Mesh Parameterization

对曲面进行参数化就等于找到从合适的域到曲面的一对一映射。在这个包中，我们主要关注与同态的三角曲面，以及到平面域的分段线性映射。该包实现了几种表面网格参数化方法，如刚性参数化、离散自适应参数化、离散保角映射、浮点均值坐标、最小二乘保角映射、Orbifold Tutte嵌入或Tutte重心映射。该代码是通用的，适用于FaceGraph概念的任何模型。