原文链接

作者：Guillaume Damiand Introduced in 版本引入: CGAL 4.0 Depends on 库依赖: Combinatorial Maps Depends on 库依赖: Generalized Maps BibTeX 文献排版: cgal:d-lcc-12-17b License 版本许可: LGPL

Windows Demo 示例程序: 3D Linear Cell Complex

Common Demo Dlls 动态依赖库: dlls

该包实现了D维空间中线性几何体的线性胞腔复形和对象

  • 对象的组合部分由组合或广义地图描述，代表对象的胞腔加之这些胞腔的关联和邻接关系
  • 几何体通过关联地图的每个顶点的方式被添加在组合数据结构中
  • 以二维组合地图，同时使用三维点，给出了Polyhedron_3的线性胞腔复形替代品

笔者寄语：CGAL中的线性单元其实就是“体”，线性单元复合体，其实就是“体模型” 如果你接受了这种看法，下文中的名词，你可以这么理解

  1. 线性单元、3-Cell <—> 体元
  2. 线性单元复合体 <—> 体模型
  3. darts <—> 二维面

介绍

一个dD维度的线性复合体允许表示一个具有线性几何结构的可定向细分dD对象：细分的每个顶点都与一个点相关联。

The geometry of each edge is a segment whose end points are associated with the two vertices of the edge, the geometry of each 2-cell is obtained from all the segments associated to the edges describing the boundary of the 2-cell and so on.

线性单元复合体的组合部分由dD组合图或dD广义图描述（强烈建议首先阅读组合图用户手册或广义图用户手册以了解定义）。为了添加线性几何嵌入，一个点（Point_2或Point_3或的模型Point_d）与组合数据结构的每个顶点相关联。

图30.1 线性几何对象的示例

  • 左图：一个二维对象，由3个二维单元、9个一维单元、7个零维单元（7个顶点）组成
  • 右图：一个三维对象，由3个三维单元、12个二维单元、16个一维单元、8个零维单元（8个顶点）组成

image.png

笔者寄语：以下内容其实就在介绍，CGAL是怎么组织线性单元复合体的拓扑结构的

如果我们以combinatorial map包的角度考虑图30.1右图中的示例，这个3D对象的组合部分由一个组合地图（3D combinatorial map）描述。如图30.2所示，这个物体的几何部分是通过将一个点与地图的每个顶点相关联来描述的。

图30.2 对图30.1右图的线性单元复合体对象进行详细说明

  • 左图：这个3D线性复合体，包含54个darts（18个3DCell），其中每个顶点与一个点相关联（这里使用的是Point_3），蓝色线段代表\(\beta_3\)关系
  • 中图：将三个3DCell的邻接边部分放大，详细说明了属于边缘六个darts和darts与点之间的关系
  • 右图：将浅灰色和白色3DCell的邻接部分放大，详细说明了属于facet的8个darts和darts与点之间的关系（红色线段）

image.png

与广义地图的情况类似，

组合地图与广义地图的比较

线性单元复合体可以基于组合地图，也可以基于广义地图。那我们选用那种数据结构作为底层呢？

组合映射和广义映射非常相似：它们都基于darts和functions，并且都允许表示准流形D维N个对象。这解释了他们共享他们的主要概念。
但是，它们具有三个主要区别

  • 首先，广义地图允许表示不可定向和可定向的对象，而组合地图只允许表示可定向的对象
  • 其次，广义映射在每个维度上都是齐次的，因为所有函数都是对合的，而组合映射不是齐次的，因为一个函数是排列而其他函数是对合的。这种同质性简化了广义地图的算法，因为它可以避免第一维的特定情况
  • 第三，广义地图需要两倍于组合地图的飞镖数量才能表示可定向对象

考虑到这些不同的优点和缺点，您可以根据应用程序的需要选择使用广义映射或组合映射