3.2 三维块体几何识别的数据结构

3.2.1 目标体的输入数据格式

为了便于目标体的输入，通常要求输入数据以最小的数据量来完整地描述目标体的空间拓扑特性。因此，本书采用分段线性复合形（Piecewise Linenr Complexes，PLC）来表示目标体。另外，这里的目标体暂时考虑为任意空间单连通多面体（凹或凸）。

目标体的输入数据包括两部分内容，一部分是几何信息，以角点空间坐标来表示；另外就是拓扑信息，以组成目标体的每个面上封闭环路（按逆时针走向）的点序列来表示。具体格式如下：

以某一工程边坡为例（图3.1），此边坡几何模型为单连通多面体，并且为凹面体；共有50个面，135个棱边，87个角点。此目标体的输入数据见表3.1。其中，20号面的拓扑表示为：20，8，19，18，55，28，27，40，39，25。

图3.1 目标体模型

3.2.2 几何块体的数据结构

为了能够高效、经济、快捷地存储和检索数据，在构建多面体几何信息的数据结构应考虑以下三方面内容：

第一，能够充分地反映空间任意多面体的拓扑特性；

第二，尽可能减少冗余数据，减少内存占有量；

第三，执行效率要高，譬如检索方便、快捷。

由于多面体形态的复杂多变性，其组成点、棱边及面（环）之间的关系也是非常复杂的，这就要求建立的数据结构能够完整且全面地反映几何块体的拓扑特性。前面引入一些集合来表征多面体的拓扑关系（见2.3.2一节），这些集合之间存在一定的关联关系，它们之间是可以相互推导的，但为了降低数据结构存储和检索的复杂程度，有必要寻找能够代表物体边界拓扑信息的这些集合的最小交集，从而保证算法的有效性，例如集合V（X）和F（V）就可完整地表示空间任意形状的多面体。因此，本书采用集合V（X）和F（V）来表示几何块体，其中集合V（X）表示目标体的几何信息，集合F（V）表示目标体的拓扑信息。

在程序设计方面，目前主要数据结构是链表结构和数组，链表结构具有内存占有量低的优点，但为了信息的储存和检索需要大量地使用指针，计算机执行效率相应较低；数组则需要更多的内存占有量，但是在信息的储存和检索方面要比链表快。

综合以上分析，作者采用动态数组与Fortran90语言中“type”自定义数据类型来表示空间块体，其中，动态数组用于储存角点空间坐标等信息，而“type”类型数据则用来储存块体的拓扑信息。这种复合型的数据存储方式既能全面地反映几何块体的拓扑特性，又能充分地发挥了动态数组的灵活性，达到了完整反映块体拓扑信息、内存占有量小以及执行效率高等要求。

以下是该数据结构的部分源代码。

3.2.3 起辅助作用的数据结构

由于在迹线生成、空间面环识别以及空间块体识别中会产生大量临时性数据，例如各个裂隙面的迹线段、各裂隙面上迹线段之间的交点等数据。虽然它们都是一些临时性数据，但却是进行块体几何识别不可缺少的基本数据；另外，这些数据还具有类型相同、个数不同以及生成时刻不同等特点。为此，需要建立一种合适的数据结构来存储它们。鉴于链表数据结构具有内存占有量小、储存灵活的特点，为此，建立一种节点数据为动态数据类型的单链表数据结构来存储这些数据。

该数据结构的源代码如下：