2.3 表征空间多面体的拓扑关系与数据结构

由于边界表示法能够更加自然地表现一般多面体（凸体或凹体）的几何形态，能够更加真实地反映裂隙连通情况和块体系统信息，而且非常便于编程。另外，边界表示法实质上是一组从几何模型到模型的顶点、边和面之间拓扑及几何关系的映射。因此，本书采用边界表示法来表征空间多面体的拓扑关系。

2.3.1 空间多面体的拓扑关系

作为三维形体的空间一般多面体，可从其拓扑信息和几何信息考虑对它的处理。几何信息是指多面体的空间位置，而拓扑信息是指各组成元素之间的相互关系。此处定义多面体的元素为顶（角）点、（棱）边、环路、面。

1.有向体（Q）

有向体（图2.4）是由若干个有向面围成的有限空间。它是一个三维空间R³中的非空、有界、连续、封闭的子集，其边界是若干个有向面的并集。

图2.4 有向体

图2.5 有向面

2.有向面（f）

有向面（图2.5）是三维空间R³中由一个外环和若干个内环组成的非空、有界、连续、封闭的子集。

它是具有方向性且方向由其外法向矢量决定的空间平面。设Q的有向面集合F（Q）={f₁，f₂，…，f_m}，则有。f的外法向矢量垂直于f且指向体外，其边界∂f是若干个有向线段的并集。

3.有向环（c）

有向环 （图2.6）是由若干个有序、有向边组成的空间平面上的封闭边界，环中各边不能自交，相邻两条边共享一个端点。环可以分为内环与外环，内环的边界按顺时针走向，外环边界按逆时针走向。基于这种定义，在面上沿面环的某一条边前进，左侧在面内，而右侧在面外。不同线段e_ie_j的交集或为一个点，或为空集。环内每个点都是偶数条线段的交点。

图2.6 有向环

若f是一个有向面，其含有的单环是{c₀，c₁，c₂，…，c_n}（n>0），并令c₀为外环。则有：①∂f=c₀∪c₁∪…∪c_n；②f是由在c₀内的点，c_i（i≥1）外的点和上的所有点组成的；③单环不交。

4.边与和有向边（e）

边是两个相邻面的交集，一条边有两个相邻面，并有两个端点。每条边对应有两条相应的有向边 （图2.7）。令Q为一多面体，设V（Q）为Q的顶点集合，Q的边集E（Q）是在∂Q中满足下列条件的所有边的集合：①边e的端点⊆V（Q）；②e内没有点⊆V（Q）；③对于e上每个点有两个不共面的面f_i，f_j⊆∂Q。

图2.7 有向边

图2.8 有向体各组成单元关系示意图

5.顶（角）点（v）

顶（角）点为不共线的有向边的交点或不共面的有向面的交点，可表示为v=e₁∩e₂或v=f₁∩f₂∩f₃。

图2.8为顶点、有向边、有向环、有向面及有向体之间关系示意图，从图中可以清晰地看到它们之间的相互关系。有向体是由若干有向面所组成封闭区域；有向面则由一个外环和若干内环组成，有向面的边界是若干有向边或顶点的并集；有向环是若干有序、有向边所组成的封闭边界，有向环的边界是若干顶点的并集；顶点是多面体拓扑结构中最低级的元素，也是组成有向边、有向环及有向面的基本元素。

2.3.2 空间多面体的数据结构

为了能够高效、经济、快捷地存储和检索数据，在构建多面体几何信息的数据结构时，应当充分地考虑多面体的拓扑特性。设整数集合M_v=（1，2，…，N_v），M_e=（1，2，…，N_e）及M_f=（1，2，…，N_f），分别是角点数、棱边数和面数的集合。集合V（X）表示角点坐标，即

集合E（V）表示每条棱边上的点对，集合F（V）表示每个面上封闭环路（按逆时针走向）的点序列，即

为了使数据结构更加有效地便于计算机执行，还需要定义三个数据集合来表示块体系统的拓扑信息。一个集合是V（E），用来表示共用一个角点的所有棱边顺序序列；另一个是V（F），用来表示共用一个角点的所有面的顺序序列；第三个集合是F（E），用来表示每个面上封闭环路的棱边序列。

集合V（X）、E（V）及F（V）是表示多面体拓扑信息的基本集合，集合V（E）、V（F）及F（E）是从以上三个基本集合中推导出来的。理论上，后三个集合提供一些多余信息；然而从计算机执行角度来看，这些信息便于直接访问并且相比每次访问时通过计算来获取而言，需要更少的计算时间。因此从计算高效的角度出发，不论是链表还是数组，它们都应该在局部（模块化）和整体数据结构中应该具备这些数据集合。图2.9给出了一个立方体和它的数据集合。

图2.9 立方体的数据集合

目前，已经建立各种不同的具有这个特点的数据结构，其中，最重要的数据结构是链表结构和数组。链表结构具有内存占有量低的优点，但为了信息的储存和检索需要大量地使用指针，计算机执行效率相应较低；数组则需要更多的内存占有量，但是在信息的储存和检索方面要比链表快。这种差异是相对的，计算效率更多地取决于编程技巧。