对在高维GIS中表达对象的多维拓扑数据结构的分类和评价

1、对在高维GIS中表达对象的多维拓扑数据结构的分类和评价想要将像时间、比例尺等附加特性加入地理信息系统数据集，一种解决办法是创造一种高维模型，将这些特性作为与空间维度相垂直的维度来表达。之前的工作大多集中在高维栅格和数结构上，但这两种结构的数据量会随着维度增加而呈指数级增长。因为在更高维度中快速表达有限的拓扑关系变得很困难，所以使用高维拓扑数据结构的拓扑向量似乎很适合。所以我们在这篇论文中对可能用于n维GIS的数据结构进行评估和分类，这包括如何使他们支持真实世界的数据特征，例如孔洞、不相连的元素以及属性；也包括影响他们可行性的问题，像算法、函数库和软件的可行性。关键字：数据结构；n维GIS；拓扑

2、；多维GISKen Arroyo , Hugo Ledoux and Jantien StoterDelft University of Technology, Delft, The Netherlands(Received 14 August 2014; final version received 12 December 2014)1. 介绍点、线段和多边形在二维地理信息系统中的表达可以认为是一个以及解决的问题。有许多知名的拓扑数据结构来表达他们，比如DCEL模型（Muller和Preparata 1978）和四方边缘机构（quad-edge）模型。尽管这两种模型有许多的不同，但在实际应用

3、中，只要能满足最低的实际需求（例如支持孔洞和属性），他们通常被认为是可以互换的。而且，许多GIS应用使用的很少或没有拓扑关系的数据机构，例如简单要素（OGC 2011），而是只在需要时计算拓扑关系（ESRI 2005）。这种非拓扑建模的成功应用，被认为是因为可视化不需要明确拓扑关系的事实、大多数二维数据集相对较小和在二维情况下利用一些突出的内在特性的可能性，例如在大多是平面分割中，两个多边形使用同一边。但是，许多这种特性不能应用于高于二维的情况-例如在三维空间划分中可以有任意多的多边形关联于同一条边。尽管如此，到目前为止将附加特性如第三空间维度、时间和比例尺融入GIS的工作主要是临时性的适应二

4、维数据结构，而不是构建一种新的、高纬度的数据机构，这实际上已经限制了GIS软件的功能。举个例子，第一次见于Raper（1989），三维GIS经常用所谓的2.5D结构模拟三维，这基本上是将第三维作为一个属性对待并且限制了可被表达的几何体；或者使用没有三维拓扑关系的二维数据结构，通过他们的二维边界间接的独立表达三维对象。这表明许多操作需要使用复杂的搜索，而这需要比实际需要多许多的空间。时空GIS拥有多种二维（Armstrong 1988）或三维（Hamre et al. 1997）结构的表达，或者每个对象的变化列表（Worboys 1992a, Peuquet 1994），以及对这些对象的有限的时

5、空想结合的分析；多比例尺的数据集通常由每个比例尺独立数据集组成，这些数据集通过一些共同的ID来相互关联，这可能导致他们之间的不一致。一种代替临时性适应二维结构的表达，是将确定的可参数化的特性作为附加的、垂直于空间维度的一个几何维度，这样真实世界的点实体到三维实体（0维到3维）都被作为嵌入更高维空间的高维对象建模，这种方法通常使用高维数据结构来存储。尽管理论上可用的维度数目没有限制，但由于维度增加模型需要的空间也增加，这将实际的维度数目限制在6-8个。高维模型的使用在一直以来的数学理论上有很好的基础，也为实际应用打开了大门。Descartes（1637）通过将坐标系放入空间中，已经为n维几何打下

6、了基础，这允许对几何元进行数字描述和运用代数方法；n维几何理论由Riemann（1868）从其他理论中发展而来；Poincare（1895）用一个维度独立的公式发展了代数拓扑学，证明了即使n维对象不能被表达，但他们确实有精确的拓扑定义，因此他们的特性可以被研究。从应用的角度来看，Arroyo Ohori等人（2013a）表明了4D对象间的4D拓扑关系如何提供三维拓扑关系所不能提供的视野的；McKenzie等人（2001）主张天气和地下水在少于四维时不能被充分研究；Van Oosterom和Stoter（2010）认为一个融合了空间、时间和比例尺的GIS的5维模型可以用来减轻数据维护难度和改善一

7、致性，因为算法可以检测用五维表达的对象是否连续和是否与其他对象冲突。目前，在GIS中与高维模型和结构有关的研究都局限在将沿着每个轴（n维格网）的规则细分格网和使用树结构的分层细分格网相结合（Varma等人 1990，OConaill等人 1992，Mason等人 1994，Bernard等人 1998），这些最近才在GIS软件中被实现（Mielke 2014）。这种结合利用了大多数应用于2维规则或半规则几何图形的数据结构扩展到更高维十分繁琐的事实，即使大多数研究和软件仅限于使用时间作为第四纬度的四维。但是，作为GIS中2维/3维格网和层次树结构，这些表达有同一个问题：他们不能表达精确的边界，表

8、达对象缓慢复杂，尤其当他们是混合纬度，他们所需要的空间随着纬度成指数增长。N维对象的矢量表达解决了这些问题：它们通常更紧凑，可以更加精确的描述边界，也可以直接表达带有属性的对象。这使得他们特别被高维GIS关注，即使对它们的探索已经很难，因为普通的用于GIS的2维矢量的数据结构像高维扩展确实不自然。但是，许多在其他领域已经有的高维几何和拓扑结构可以被应用于这个目的，即使这些数据结构与GIS中的2维数据结构有很大不同，有效的应用和使用也很复杂，也经常需要特别的改变以支持一些真实世界的数据情况（例如孔洞和非流行几何体）。所以它们几乎从来没有在实践中使用过。我们相信，通过更好的理解使用高维结构来表达真

9、实世界对象的可能性和挑战，这些问题可以被克服。因此，在这篇论文中我们总结了我们研究的结果。为此，在第3到第5结了，我们提供了这些数据结构的完整的维度独立的描述，同时为每个数据结构配了2D/3D例子来将它们与2D/3DGIS中相似的案例像联系。尽管对现存的高维数据机构做了很好的调查，尤其对是Lienhardt（1991）、Omi和De Floriani（2012）的，但这些覆盖较少的数据结构，集中在几何建模的理论方面，也没包括那些也会影响这些结构实施的更实际方面，例如算法、类库和软件的可行性。这篇论文是对Arroyo Ohori等人（2013b）的扩展，在那篇文章中我们讨论了如何使用真实世界的数

10、据将高维对象通过一种特定的数据结构建模，笼统的（Lienhardt 1994）。正如在第2节中详细解释的，我们鉴别出主要的三类表达n维对象的可行的空间数据结构。每一组这些数据结构，以相同的方式discretises空间，使用相似的形状元，也拥有他们的大多数特性，包括为使他们支持例如孔洞和属性的特征而采用的技术。所以这些组被单独分析：第二节简单复形，第四节的胞腔复形，第五节整理了拓扑模型。在第六节，我们用使用这些数据结构来表达n维对象的意义来结束讨论。专用术语说明这篇论文主要的是为那些对使用超过三维来表达真实世界对象的GIS专业的读者写的。所以我们在任何可能（例如一个平面，即使它是非流行的，也是

11、一个二维对象）的地方选择使用2D/3D GIS术语（或者GIS方面的术语），并且只在GIS术语不能清楚表达或者模棱两可的时候（例如一个表面可以是任何维度）使用数学术语。2. 高维数据结构和他们的分类空间数据结构由两方面组成：（1）组合部分，由一系列图元和一些他们之间的拓扑关系组成；（2）使得这些图元和他们的几何体和属性想连的嵌入部分。这种区别通常在实际应用中用来从那些计算几何（Mäntylä 1988, Lienhardt 1994）领域的问题中区分出几何建模领域的问题，但这也对描述高维结构和2D/3D结构的不同很有用。当考虑通常在GIS中被使用、只包含一维拓扑关系的数据结

12、构时这种区别更清晰。举个例子，在简单要素规范中（OGC 2011）独立的二维图元被定义为使用隐含线段相连接的点序列（包含坐标）。三维体元则用这样的二维元素的集合表达，否则这些二维元素不相连。尽管隐含在二维图元中的线段被认为是相邻的，但是无法知道二维图元之间的关系，这样的数据结构被认为最多只能存储一维拓扑关系（边之间的相邻关系以及边和顶点的相交关系）。尽管这种数据结构可以被嵌入进任何维度（通过为每个点在n维空间中安排坐标），但是这种数据机构会随着维度的增加成指数的变的低效：低维度的图元需要被编码多次，每次出现在高维度图元中时要被递归一次。这意味着即使是一个简单的几何和拓扑查询都涉及到搜索许多对象

13、（Hazelton 1998）。举个例子，一个简单要素表达的正方形不重复大多数顶点，但一个正方体每个顶点至少重复三次，一个超立方体（正方体的思维类似物）每个顶点至少重复12次，一个五维立方体每个顶点至少重复60次。于是，与Hazelton等人（1990年）给出的地理信息系统的维度的定义相类似，我们认为一个高维空间数据结构的显著特征不是其被嵌入高维空间的能力，而是能够以维度独立的方式明确的存储拓扑关系。为此，我们假定被表达的对象可以在功能上通过使用GIS中的标准拓扑建模方法形成一个空间分区所有对象都被覆盖，他们有意义的边界都被计算，并且模型中的每一个区域都被认为属于一个对象的集合（Rossign

14、ac和OConnor 1989）。做到这样就使得存储一个包含对象的可通过的结构成为可能，在这种结构中边界集合能被准确表达，并且可以通过检查哪些对象在这个集合中来轻松的查询对象之间已经存在的拓扑关系（Egenhofer和Franzosa 1991，Worboys 1992b，Güting等人2000）。所以对GIS最有希望的数据结构，是那些始于空间细分，能存储那些被准确定义的、范围相对广的、任意纬度的对象，这些对象被嵌入相同或更高维度的欧几里得空间的，附加了属性的，并且相互间有足够的拓扑关系以允许结构的快速遍历和基本操作，例如检测两个给出的对象是否相同、相邻或是相交。在大多数GIS文档

15、中，数据模型和数据结构这两个术语是可以互换的。但是，正如Frank（1992）认为的，将它们区分出来是有用的，数据模型即真实世界成为抽象图元的特殊离散，数据结构即数据模型在计算机中的具体表达。一个数据模型广泛的定义了图元的形状和他们之间可能存在的关系，而数据机构清晰的存储了一些这种关系（那些通过一定的计算机花费可以被计算的）并且忽略其他的这种区别通常在2维结构中是模糊的，因为这些二维结构通常拥有以为表达0到2维图元而准确制定的规则为基础的定义，这些图元可能在每个纬度都不同，例如在翼边数据结构（Baumgart 1975）和DCEL数据结构（Muller和Preparata 1978）中的单独的

16、节点、弧和面结构。这种定义事实上跳过了潜在的共同某些的定义，带来的后果就是这些结构没有清晰的通向更高维度的方法。相反的，高维模型必须使用纬度独立的图元来定义（至少是在高维度）。因此它们能表达一种数学上良好定义的对象，即使这种对象在实际实施的高维数据结构中不能被完全支持，但也能被客观的分类。将高维数据结构分类成一系列模型可不仅是理论上的兴趣点，而且对分析是非常有用的。使用相似模型的不同数据结构在空间复杂度方面拥有相似特性，因为他们包含一系列相同顺序的图元。对它们的操作也具有相同的计算复杂性，因为它们拥有相似的拓扑关系，当他们的拓扑关系不相似的时候，它们的计算花费受限于他们从一种到另一种的转换花费

17、，这种转换通常简单并且可以一个图元一个图元做。由于算法操作的是被数据模型定义的图元，这种分析也可以知道那些基本操作可以被应用于这种数据机构。例如，欧拉操作根据细胞复合物定义（Mäntylä 1988），恒星运算符则根据简单符合体（Velho 2003）。因此，总得来说，任何代表细胞复合体的数据机构可以实行欧拉操作，对于恒星操作符和简单复合体来说也是一样的。McKenzie等人（2001）认为，使用的理想的数据模型根据应用决定。一个理想的数据模型应该强大而且可以表达很多种对象，但不幸的是这些特性是相互冲突的。强大的结构建立在小而简单的图元上，这些图元有固定形式并且与其他有关的

18、图元有固定的连接数目（至少是有限的），例如与坐标轴平行的盒子或者单形，使得这些结构可以被进行简单而强大的代数操作并且可以高效的在它们的图元之间导航，例如二维结构终点四方边界（Guibas和Stolfi 1985）或者三维中的小平面边缘结构（Dobkin和Laszlo 1987）。但是，将复杂对象划分为这些简单图元不简单而且会导致产生大量的图元，这些图元需要特殊的处理，要使得它们空间紧凑并且限制可能被存储的对象类型。在这种意义上，不同的数据模型需要做不同的选择并且必然会涉及到取舍。根据所采用的图元和他们的特征，我们将我们已知的、可以表达n维矢量对象的所有数据结构分为了三类，总结在表1并且解释如下

19、：l 几何单纯复形（第三节）：他们直接将对象分解为维度达到n维的单形（例如点、线段、三角形、四面体等），所有这些单形都有直接的几何实现（例如一个模型中的单形代表现实空间中的一个单形），并且以使用单形作为图元的数据结构存储他们。这种数据结构空间更加紧凑，尽管比其他模型更难建立但可以提供更强大的代数操作。l 胞腔复形（第四节）：他们直接将n为对象分解为与n维球体同胚的部分，并且以使用细胞作为图元的数据结构来存储这些部分。这种数据结构很紧凑并且易于建立，但是他们只有有限的代数操作。l 有序拓扑模型（第五节）：首先建立一个细胞复合体，然后将这些细胞分解为不能直接几何实现的抽象单形（例如模型中的一个单形

20、在现实世界空间中没有特别的意义），然后使用以单形为图元的数据结构存储它们。这种结构结合了前面两种的优点和缺点，所以将这种结构归为细胞复合体（Omi和De Floriani 2012）和简单复合体（De Floriani和Hui 2005）的都有。但是，他们实际上区分出了上面说的结构，因为他们允许一组不同的操作，因此可以分别覆盖。模型数据结构描述几何简单复合体以单形为基础的结构将对象在几何上分割为单形，然后存储这些单形和他们之间的相邻关系关联图形以图元的方式存储每一个维度的细胞+他们之间的关联关系细胞复合体多面体在每个顶点周围存储局部金字塔（空间的投影）以减少一个维度流行数据结构将关联关系限制到

21、一个固定的数目（例如半（i-1）细胞数据结构）广义映射/细胞元细胞单形的纯粹的组合分解+以单形为基础的数据机构存储顺序拓扑模型组合映射和上面一样但不分割1-细胞并且每个相连部分定义一个方向映射链广义映射+非流形情况的关联图这些并不是所有能够表达n维矢量数据的模型。只包含n维空间中的点的模型（Pasko等人2001）在遥感和数字采矿环境下被广泛的使用，特别在需要和差值函数一起应用的表达领域（Miller 1997）。几何体的构造表达，例如构造立体几何（CSG）树（Samet和Tamminen 1985, Paoluzzi等人 2004），并且对象被定义为操作序列（Omi等人 2014），在特定的

22、情况下有可能并且有用，例如透射的产生和计算过程（Damiand等人 2008）。但是，这些方法没有一个可以直接存储对象和它们的属性，特别是那些低维度的，所以需要被转为另一种、更明确显示的模型，为了它们能被可视化或者被执行在GIS中可能的计算过程，例如几何体相交运算。所以这些模型对高维GIS没有意义，这篇文章中也不做考虑。3. 几何单纯复形一个i-维单形（i-单形），是由i+1个顶点和一个由这些顶点组成的j维表面的子集组成的j-单形组成的合成图元。直观的，一个n维几何单纯复形，也被称为欧拉单纯复形，是将n维空间细分为一个通过为每个顶点附加一组坐标的方式将封闭n-单形直接嵌入空间的结构，这种细分的

23、方式是它们的内部都是几何上不相交的（两两不相交）。如，在一个n维单纯复形中，一个i维对象被表达为一组i-单形。更为一般的，一个单纯复形可被定义为一组如下的单形：l 单形的每个表面也在单纯复形中；l 任何两个单形的相交不是空就是它们的共同表面；图 1 一组由几何单纯复形表达的建筑。每个三围建筑被分割成了一组不相交的三维单形（四面体），他们的2维墙面和屋顶由一组二维单形表达（三角形）表达一个i-单形通过一个i+1个仿射独立顶点的（i+1）元组来简单描述。因为它们是仿射独立的，所以它的几何实现是它顶点的凸壳在多维单纯复形中一个顶点可以通过一组坐标描述，来表达其被嵌入多维欧拉空间。因为我们在考虑多维空

24、间的细分，单纯复形中的每个单形至少是一个n-单形的一个面。代数单纯复形拥有一个简单但强大的结构，并且易于查找。如果两个i-单形拥有共同表面那么它们是相邻的，一个i-单形和一个j-单形（i不等于j）如果一个另一个表面，那么它们是相交的。在多维单纯复形中，每一个n-单形至多与n+1个其他n-单形相邻，并且在边界上拥有n+1个（n-1）-面。对于每个n-单形来说，于是就可能进行n+1种不同的边界和相邻运算，第n个边界运算返回在相对一面的第n个顶点的n-单形的（n-1）-面这种操作通过移除顶点元组的第n个元素，第n个相邻操作返回相对一面第n个顶点的相邻n-单形，如果有的话，也与第n个边界运算出的面相交

25、。结构使用几何单纯复形来表达n维对象的最大的挑战是将可能的将被建模的复杂n维对象三角化的难度，例如用算法将他们分割为单形，这样单形的联合代表一个对象并且与原来的几何体一致。尽管n维空间中点集的三角网已经被广泛的研究并且有强大的软件去计算它们，例如快包法（Barber等人 1996），这些三角网通常不适用与n为对象，因为一个对象的顶点的三角网通常导致和对象边界不一致的单形，比如部分在对象内和部分在对象外。但是，通过约束或者协调三角网，可以使得边界成为三角网的一部分。这两种方法使得三角网包含确定的单形，这些单形以约束的形式成为三角网的一部分，在这个例子中会成为对象的边界，与约束三角网中约束条件直接

26、是结构的一部分不同，在协调三角网中它们被允许被分割为更小的单形。尽管在一些例子中为了构建n维约束三角网而描述和演算的特性已经有了发展（Shewchunk 2000），在实际操作中他们这种结构在普遍例子中很难应用，为此不得不解决健壮性问题并且可能需要额外的大量的顶点和随之而来的额外的单形，因为不是每一个三维或者更高维的对象都可以不需要额外顶点而被三角化的（Ruppert和Seidel 1992）。不幸的是，尽管在二维和三维方面有许多强大而可靠的约束和协调三角网库存在，例如Triangle（Shewchunk 1996）、CGAL（Boissonnat等人 2002）和Tetgen（Si和G

27、28;rtner 2005），但我们没有意识到任何软件或算法是否能够构建超过三维的约束或协调三角网。孔洞、属性和不相连的部分假设对象已经被成功三角化，那就意味着在单纯复形中的孔洞和不相连的部分变得不重要了，因为这些变成了集成进组合三角网结构中（Ledoux等人 2014）。通常，一个三角化算法一一组点为基础开始工作，并且确保这些点的凸壳能被三角化，使用“大三角”或者远点（Liu和Snoeyink 2008）的概念可以做一些事，从而使得不相连的部分或者在更高维度单形中不相连的部分相连。相似的，因为有孔洞的多面体的内部可被三角化，额外的单形通过剩下的结构与代表孔洞的空白区域相连。通过这种方式，二维

28、孔洞可以通过一组被标记为空白的三角形来表达，三维孔洞通过一组四面体，更高维度与此类似。这种方式确保了复合体中的单形可被查找。操作另一个单纯复形的好处是许多对他的操作是高效和简便的。例如，一个单纯复形可以被高效的横切而不需要任何外部数据。从任何一个单形开始，为了查找可以以任何想要的方向在单纯复形内“走”，例如一个点在哪个单形（Devillers等人 2002），而这每一步都只花固定的时间。比较由一组单形组成的对象也是简单的，假设它们已经通过确定的方式被三角化，因为它们能找到一个共同单形后一个一个相比较（按顺序），这种比较可以通过在个个单纯复形中“走”来完成。检查两个对象几何上是否相邻或相交是另一

29、种可以通过一个一个单形来完成的操作。以单形为基础的数据结构因为在n维单纯复形中顶点的数量、（n-1）-面的数量和n-单形的相邻的单形的数量输固定的和可知的，这就在计算机中能够容易的使用简单的数组而不是链表或其他可变长度的数据结构来表达。通常，这种表达通过使用n-单形为基础的数据结构，图2所示的是二维情况，这种结构中n-单形是主要图元。这有时被称为邻接或入射模型，这取决于在结构中被表达的单形的维度只有最高维的那一个在邻接模型中，而可能所有的都在入射模型中。一个n维单纯复形被表达为一个n-单形图元的集合，每个集合与他的n+1个相邻n-单形相连。上面说的模型，也包含以下信息：l 邻接模型：对每个n-

30、单形，与他n+1个顶点的包含坐标和属性的顶点图元有n+1个连接，或者这些信息被直接存储在n-单形中。从一维到n-1维的单形和它们直接的入射关系于是没有被显性表达。l 入射模型：对每个i-单形，i在0到n间任取，与他的（i-1）-面有包含几何和属性的图元有i+1个连接，或者这些信息被直接存储在i-单形中。每个维度的所有单形，拥有所有它们的入射关系，所以可以被显性表达，或作为更高维单形的一部分。图 2 以2-单形（三角形）为基础的数据结构存储的几何体的图元间一些可能的关系。（a）2-单形的相邻关系（b） 2-单形的边界关系（c）1-单形的边界关系（d）1-单形的星型（共边）关系（e）1-单形的边界

31、关系（f）0-单形的嵌入。除了这些，嵌入结构中0、1、2-单形可能存储属性。邻接模型至少使用（a）、（c）和（f），而入射模型至少使用（b）、（e）和（f）。邻接模型于是形成了n-单形为节点的（n+1）-规则图，即每个顶点都有n+1度的图。入射模型的是一个最大为n+1度的图，这个图的代表i-单形的节点的度是i+1。注意邻接模型所以更紧凑，但仅允许n维对象的显性表达，而入射模型更为冗余但支持表达任意维度的对象。其他数据模型其他可能的模型设计到使用单纯复形的强代数特性来描述单形的更为紧凑，然而这很难在超过三维中扩展。例如，在二维和三维中，可以这样：存储每个单形的一些顶点的几何体（Blandford

32、等人 2005）（剩下的存储在其他相交的单形），使用相邻单形的集合而不是一个作为图元，使用逐步接近单纯复形的渐进表达（Popovic和Hoppe 1997），或者将它压缩为一个原始结构可以被推测的简单操作序列。此外，因为一个单形也是一个胞腔，可以使用意味着更加通用胞腔复形的数据结构，例如那些在第4和第5节描述的。这些在实际处理一个胞腔复形三角化的过程中常被使用（因为在那种情况下不是一个单纯复形结构并且不能被定义为只为单纯复形存储的数据结构），但这在运用时非常低效当它被三角化后。应用单纯复形在超过三维的情况通常只在理论中描述而很少用于实践。在GIS中，Paoluzzi等人（1993）描述了翼型方

33、案，以便描述任意多面体的单纯复形，Karimipour等人（2010）使用顶点列表来存储任意维度的单形，以便使用Delaunay三角网作为例子来做空间分析。4. 胞腔复形一个与在拓扑学中CW复合体概念相关的n维胞腔复形，是将n维空间细分为不相交的胞腔（两两不相交），于是对所有0到n间的i，一个i-维胞腔是一个与开放i-球同质的对象（即点、开放弧、开放圆盘等）。一个i-胞腔的j维面（j-面）是一个j-胞腔，j小于等于i，并且在这个i胞腔的边界上。与单纯复形相似，如果有共同面则两个i-胞腔相邻，一个i-胞腔和j-胞腔是包含关系，i不等于j，如果一个不是另一个的表面。更为一般的，一个胞腔复形可以被归

34、纳定义，如Hatcher（2002）。一个n维胞腔复形从一组分离的顶点开始建立，并且任取0到n，一个i-胞腔通过将（i-1）-面附加给自己的边界来建立，这些面之前已经被增加到复合体上了。这样，一个边是通过连接边界上的点来建立，一个面是通过连接边界上的边，一个体是通过连接边界上的边，如此下去。与在单纯复形中一样，一个在n维胞腔复形中的n-胞腔的面处在这个胞腔和相邻n-胞腔之间，除非它在复合体的边界上。代数胞腔复形与单纯复形在两个相关的方面不同：（1）一个胞腔在边界上有很多的小平面，每一个小平面也有不同数量的小平面，持续向下递归至顶点层面；小平面不需要递归查找的胞腔没有简单的几何解释。这个导致胞腔

35、复形拥有与单纯复形相比更为复杂的表达和代数。例如，单纯复形能够通过添加或移除由一组顶点表达的单形，或者通过分割和合并已有的单形来简单的构建，但胞腔复形为了要增加或移除胞腔需要更为复杂的操作，因为这些胞腔是以它们的小平面维基础描述的（Arroyo Ohori等人 2014）。横切一个胞腔复形（例如寻找点在那个胞腔或者查找哪些胞腔与给出的几何体相交）也要困难的多（De Berg等人 1997）。构建和属性一个有属性的i维对象通常能被直接表达为胞腔复形中的一个附有属性的i-胞腔，需要的最小预处理只需要它是I-球同胚的或者可以被修改的，这样它在功能上只需要使用简单的“戏法”或者组合操作。表达同样一组对

36、象胞腔复形中胞腔的数量比单纯复形中单形的数量要小意味着胞腔复形可以更高效的存储对象，只要使用足够的数据结构。表达胞腔复形通常基于使用它们的（n-1）维边界表达它们的技术来建模（即边界表达），不像对象通常使用相同维度的主要图元来建模的单纯复形（即对象表达，或者更为所知的它的三维名字，实体或体积表达）。这是一个不易被察觉的差别，但这代表着胞腔是使用基于递归定义的更隐式的方式，不像可以被显示存储为一组顶点的单形。因为这样会使很多操作变慢，对胞腔的操作可以通过添加给出的维度的所有胞腔和/或给出空间范围内的所有胞腔的索引来改善。关联图结构任意胞腔复形的最常用的结构是关联图和其他有关的结构（Rossign

37、ac和OConnor 1989，Sobhanpanah 1989，Masuda 1993），这种结构将复合体中的所有胞腔（所有维度）作为独立的包含几何和属性信息的嵌入图元来存储。和单纯复形一样，只要需要线性几何，唯一需要的几何信息就是0-胞腔的的点的坐标。但是，因为一组顶点不足以描述一个胞腔，每个维度的所有嵌入结构都需要存在（尽管他们可以简单的像每个胞腔使用一个唯一ID或内存地址）。正如图3所示，这些通过包含胞腔间关联关系的组合结构连接，例如一个i-胞腔边界上有（i-1）-胞腔。由于这些关联的数量一般是不固定的或有界的，不像一个单纯复形，他们融入胞腔图元更难。一个解决方案是使用可变长度的数据结

38、构（例如，一个胞腔的面连接的列表）。另一个是存储有一对i-胞腔和（i-1）-胞腔组成的组合图元适合数据库实现的方法对。虽然在空间上的关联图是有效的，它们是难以导航和操纵，因为它们包含在有限的拓扑信息。这大大复杂化了许多在单纯复形中相对简单的查询，如：求一个在2-胞腔周围的0-和1-胞腔的序列；或是否两个n-胞腔具有相同的几何（因为他们的面，每一个隐式表示自己的方面，可能存储在任何顺序）。图 3 在一个复杂的细胞的胞腔，是最常见的关系被存储在一个关联图和类似的数据结构到二维，和嵌入的0-胞腔从而支持几何。（a）三个相邻的多边形。（b）胞腔复形中的胞腔。（c）一种2-胞腔的边界关系。（d）1-胞腔

39、的共同边界关系。（e）1-胞腔的边界关系。（f）0-胞腔的嵌入和共边关系。半空间结构和Nef多面体另一种方法涉及将胞腔表达为半空间相交的联合，这种方法可以通过执行（交替）分解成凸部（Lien和Amato 2006, Bulbul和Frank 2009）。大多数实现这一概念的数据结构将胞腔隐式存储为半空间的操作树，如图4所示，其中每个存储为一个包含一个超平面方程加上/下方向的系数的元组（Naylor 1990）；或者是一系列代表所有的胞腔小平面的超平面，每个胞腔被表示为一组布尔值的元组，其中的每个值指出胞腔是在特定的超平面的上侧或下侧（Tammik 2007）。虽然这是相当麻烦的，不能很好的扩展

40、到更高的维度和复杂的几何形状，Nef的多面体（Bieri和Nef 1988）遵循类似的方法，但使用本地金字塔的概念扩展了它，将每个顶点的邻域信息如图5所示，包含每个维度的所有与它关联的胞腔，这种扩展通过将他们投影到一个无限小的顶点周围的超球面，并且通过使用（n-1）维数据结构的超球面几何体来存储这些信息，这样减少胞腔的复杂的维度。图 4 （a）多边形被储存为一个凸多边形的联合。（b）和（c）每个凸多边形被表示为一组相交的半平面。一组多边形可以被减小到一组环形区间，在更高的维度，一组多面体到一组球上的面，等等。这意味着，超平面的全局安排只存储在顶点水平，这种规模更复杂的几何形状和允许属性的存储（

41、在顶点，循环间隔、球面、等）。这种技术在三维是非常有用的，因为它允许一个使用任何数量的的二维数据结构表示三维。在理论上，这种方法可以重复降低尺寸，以便有一个完整的描述的胞腔复合物，这样做的实际好处是少的因为维度增加，导航变得更麻烦。此外，这是非常复杂的处于完全维度独立的方式来实现这一点，需要能够计算点集与一个超球面投影内核的交集。事实上，已知的全部现有的实现限制为3D，如在CGAL那个（Granados等人2003，Hachenberger 2006）。图 5 相同的多边形被根据在顶点使用Nef的多面体本地金字塔存储。 （a）本地金字塔被示为圆形。 （b）从所述本地金字塔基于其角度的视角投影到

42、圆和参数化的表面基于，这减少了2D多边形到1D的维数。本地金字塔从而成为一组相邻的间隔。各种数据结构有些可能涉及到限制有强代数性质的胞腔复形的表达，如那些流行域。流行域是区域中类似于某种维度的欧氏空间的对象，即使在全局它们不是。更确切地说，一个n维流形（或简单地n - manifold）M是一个拓扑空间，其每一个属于M的点具有与R同胚的邻居。最重要的是为一个空间数据模型，多支管有两个非常有用的性质：l 一个带有边界的n-manifold有一个性质，就是它的边界是（n-1）-manifold，这确保了一个n维对象可以通过他的（n-1）维边界使用流行数据结构来递归表达l 一个（i+1）-胞腔中一个

43、（i-1）胞腔最多与两个i-胞腔关联，这限制了边界表达为基础的模型的复合体图元之间所需要的连接数。一些二维和三维胞腔复形的数据结构限制为流形，或分割对象为流行部分（Lopes和Tavares 1997，Pesco等人 2004），它允许这样的数据结构的效率更高，因为他们需要处理简单的配置（Aguila和Ramirez 2003）。例如，如果我们限制使用每个胞腔的流行域俩表示n维胞腔复形，一个（n-2）-胞腔最多与两个（n-1）-胞腔关联，（n-2）胞腔可以作为图元或被指出，同时能够绕过它们。这样的结果是基于2D的半边数据结构，如DCEL（Muller和Preparata 1978），在三维，如

44、CIEL（Lévy等人 2001），但概念可以推广到任意维度。各种用于修改n维胞腔复形的“半（n-2）-胞腔”数据结构因此有可能，这由一对相连的（n-2）-半-胞腔图元组成。但是，请注意，这是独立于单独的（n-1）-胞腔的表达问题，这通过DCEL中的定向的边和CIEL中的定向边环来解决。虽然一般可以使用各种技巧和多种数据结构来表达non-manifold，如图6所示，如连接到单一嵌入的组合结构中的重复元素，往往会有歧义的表达（例如，重复胞腔）或损失大约一个模型的非流形部分的适航性。孔洞和断开部分一胞腔复形为基础的数据结构的主要问题是处理孔洞和断开对象，使用上述的数据结构中的任何一种，

45、这两者都将通常导致在一个断开图。因为在一个胞腔复形中n-胞腔被认为是同胚的开放n-球，孔洞破坏了胞腔复形的定义。然而，一个n维的洞是同胚于n维胞腔n-球可以在一个特设的方式使用下列技术处理：图 6 （a）一个2-胞腔是一个non-2-manifold因为在顶点一圈突出的空间不是同胚于平面。（b）和（c），它仍然可以使用一个循环的面向（一半）的边，有一个重复的顶点在该位置（如2个半球），但有2种方式它可以做。请注意，（c）导致了一个断开的图形。l 分裂的胞腔：细胞含有一个孔被细分为多个细胞，所有这些都是相邻的。该解决方案的概念是很简单的，实际上相当于做了什么与单纯复形。这也能尊重一个细胞的定义，

46、从细分的细胞可以同胚球和洞是一个类似细胞但代表空区其他。然而，找到一种方法来分割一个单元格，因此需要几何运算，并在实践中，可以是困难的，特别是在3和更高的维度。l 桥接的胞腔：一个孔被连接到其他的组合结构使用比孔洞低维的'桥'的胞腔。这桥胞腔通常需要一个边连接孔的形式，它包含的胞腔。该解决方案是简单的实现，通常只需要找到一个合适的桥（例如，完全在胞腔内部的边）。含孔的胞腔不再是同胚于球体，但大部分计算工作很少或没有变化（Bryant和Singerman 1985）。然而，主要的拓扑查询可能需要特殊情况处理（如不显示添加这样的边，当显示胞腔或计实际的桥梁将在同一侧有相同的胞腔）。

47、l 孔洞作为属性：孔可以存储为完全独立的胞腔，在他们所在的对象作为特殊属性连接，反之亦然，这可以扩展为在一棵树上有完整的层次结构对象（Worboys 2012）。该解决方案可能是最简单的实现在存储方面，但它违背了一个胞腔复形的数学定义，并会中断或需要一个复杂的特殊处理的拓扑计算过程。以这种方式创建无效的孔也很简单，如孔在（部分）应该包含他们的胞腔之外。然而，值得注意的是，复杂的不同胚n-balls的孔可以存在，例如环面，并找到一个很好的细分，可以用来处理这样一个孔洞可能非常复杂。后者的方法也可以应用于断开的组件。断开连接的组件可以通过桥胞腔连接，或者所有的组件都可以被看作是（空）总体胞腔。应用

48、超过三维的细胞复合体已很少描述或实施。Hazelton等（1990）描述了关联图可以放在一个关系数据库模式以存储4D多面体，对四维拓扑关系可以查询（Hazelton等。1992）。然而，到我们所知，在工作中这从未被付诸实践。5. 有序拓扑模型有序拓扑模型的表示方法结合了单纯复形和胞腔复形的特点。他们在一个胞腔复形的基础上工作，但细分每个胞腔为抽象的单形使用纯粹的组合操作，概念来自代数拓扑的抽象单纯复形。精确细分，取决于使用的数据结构，但如图7所示，它类似于一个重心三角凸多面体的顶点，由代表不同维度胞腔的抽象顶点组成（即不仅0-胞腔），和连接这些顶点以一个特定的方式。代表维度大于0不在空间有确定

49、的位置的胞腔的顶点（虽然他们通常被放在它们应该代表胞腔的某个地方），但单形仍然形式了空间组合正确的细分。例如，邻接和关联是有意义的和可以被定义在一个几何单纯复形中。试想，一个i-单形的j-面，j小于等于i，是一个有一组i-单形的顶点组成的j-单形，两个i单形如果有公共面就相邻，i单形和j-单形如果其中一个不是另一个的面那么它们关联。表达在一个有序的拓扑模型，对象是由一组单形表达，与单纯复形相似。然而，不像在一个几何单纯复形或者胞腔复形，在那里一个i维对象被表示为一组i-单形或胞腔，如图7所示，在一个n维的有序拓扑模型，所有的对象都是n-单形。更准确的说，一个胞腔被表达为一组在胞腔上有顶点的单形

50、。在这种方式下，即使顶点也可能表示很大的一组单形。图 7 单纯分解以得到一个二维的单形：（a）全面图，（b）组合图。（C）所有的胞腔都表现为2-单形集合，如图示的顶点，是由四个三角形几何形成。注意，1-和2-胞腔的顶点的位置是任意的，那些为1-胞腔已定义为边的中点，那些2-胞腔已定，所以单形完全在于其相应的2-胞腔内部。属性属性和几何可以以几何单纯复形类似的方式附加在一个有序的拓扑模型的单纯复形上。因为每一个单一的顶点都有一个已知的顺序，每一个单一的顶点表示一个胞腔，它是可能的，在一个有序的拓扑模型中将单形连接到一组它的顶点代表的胞腔的属性和几何信息。许多几何单纯复形上的操作都有可能是在一个有

51、序的拓扑模型上操作，即使考虑到许多它的顶点不在空间有一个特定的位置。拓扑查询可以用相同的方式来处理，而一些几何运算需要最小的变化。例如，长度，面积，体积，一个细胞等，可以使用包含排斥原理计算，其工作方式类似于一个多边形的使用“鞋带公式”计算面积。比较的对象也可以通过一个一个单形做（Gosselin等人 2011），这利用了有序拓扑模型的有序性质。构造因为这种单形分解在一个有序的拓扑模型中只能组合进行，它是没有必要建立一个约束三角剖分的输入，其中，在3节所述，可能很难做到。然而，使用一个有序的拓扑模型在单纯复形中仍然可以使用更强的代数性质，这是为了用于遍历和操作一个胞腔复形。结果单纯复形与几何三

52、角化比可以有更大或更小数量的单形，但它也有优势，顶点和单形在数量上是已知的，不依赖于几何。我们都知道有两个不同的单形分解计划用在有序拓扑模型，一个用于细胞元组结构（Brisson 1989）和广义的地图（lienhardt 1994），另一个用于n维的组合图（lienhardt 1994）。假设输入n维胞腔复形，这个复形包含了所有胞腔的关联图（每个维度）为节点，且关联关系从每个i-胞腔到它的边界上的（i-1）-面作为有向边，单形分解如图7所示，解释如下：l 胞腔元组/广义图：在图中每一条可能的直接从n-胞腔到一个0-胞腔的路径产生一个单形的顶点。每个单形可以这样定义一个独特的元组（c0,c1,

53、cn），C1是细胞腔复形中的i维胞腔的顶点表示，所有这都彼此关联。这样的一个n元组实际上是相当于一个n维单形。它可以被看作是一个基础结构的板条的概括（Joy等人 2003）有时用于二维和三维地理信息系统。l N维组合图：图中从一个n-胞腔到1-胞腔的每一条可能路径产生一个单形，从n维到2维直接使用胞腔的顶点，前面的两个顶点所对应的两种0-胞腔关联到1-胞腔（即顶点的边的端点）。每个n-单形可以定义的一个n元组（c0,c0,cn），其中C0和C0是两0-胞腔关联到1-胞腔，对于i大于0，Ci也是胞腔复形中i维胞腔的顶点表示，所有这些彼此关联并与两个0-胞腔关联。由于两0-胞腔可以以任何顺序，顺序是由指定的胞腔复形的方向（或每个连接组件）通过指定单形的顶点分别为C0和C0，然后为其他单形建立元组使邻近的单形有相反的顺序。如图8所示，这可能会导致每个胞腔组合图（或连接组件）有两个可能的方向。在实践中，这意味着，如果我们考虑由C0和C0形成的1-面作为C0到C0的有向边，表面形成有向边的环，和相对的表面方向相反，正如大多数二维/三维结构基于半边缘，例如DCEL（Muller和Preparata1978）。图 8 在关联图中有两种可能的连接每个组件的组合方向。数据结构胞腔元组结构（Brisson 1989）、广义图和n