拓扑关系和九交模型

1、认识拓扑关系和九交模型-2008301130103 杨文一、拓扑关系拓扑关系模型主要以结点、弧段、三角形和多边形作为描述空间物体的最简 化元素，运用数学领域中的组合拓扑学来实现对空间简单与复杂物体几何位置和 属性信息的完整描述。在该模型中，0维空间物体代表结点，1维空间物体代表 弧段或边，2维空间物体代表三角形或其它多边形，3维空间物体则代表四面体 或其它多面体，各类型的空间物体含有各自的坐标序列和属性值，并通过基本的 邻接、关联、包含、几何和层次关系等建立之间的相互联系，而不同类型的物体 相互组合又构成复杂的地理空间对象。除了结点没有方向性，弧段和多边形空间对象都具有方向性，如弧段L由A、B

2、结点组成，其方向性可表示为由 A-B或 由B-A，多边形则可用顺、逆时针来表示其方向性。如下图：图1拓扑关系数据模型描述拓扑关系数据模型中建立拓扑数据结构的关键是对元素间拓扑关系的描述， 最基本的拓扑关系包括以下几种：邻接：借助于不同类型拓扑元素描述相同拓扑元素之间的关系，如多边 形和多边形的邻接关系。(2) 关联：不同拓扑元素之间的关系，如结点与链、链与多边形等。(3) 包含：面与其它拓扑元素之间的关系，如结点、线、面都位于某一个面 内，则称该面包含这些拓扑元素。(4) 连通关系：拓扑元素之间的通达关系，如点连通度、面连通度的各种性 质(如距离等)及相互关系。(5) 层次关系：相同拓扑元素之

3、间的等级关系。如国家包含省、省包含市等。拓扑数据结构中弧段和链具有方向性， 通常以顺、逆时针作为方向基准，或 将坐标以顺序方式存储。拓扑元素之间的各种拓扑关系构成了对地理空间实体的 拓扑数据结构表达，如图2所示。PjPsP:图2拓扑关系空间数据模型示例不同拓扑元素的拓扑关系可在空间实体几何表示的同时来建立， 也可单独建 立不同的关系表。若在实体进行几何表达的同时建立拓扑关系，可在关系数据库 中存储各类型几何元素数据的同时存储对应的拓扑关系，如图 3所示。Points litbkGeonietiT DntaPoinMD 仇巧Tapalogical Rehrioii jhip Data Gecme

4、tiv BataArtiibiite Dara Points-IDInformationlines-iDInf erm at ionPolygons-ID InformationPolygons Tablei*Tapalcigica K elation ship Datai Pol'/iCn-IDLtlPlDAttributes Tabk图3几何数据和拓扑关系数据同表存储LireJD StartPoinMD EndPoinMD AllPDints* D(2)(2)二、四交模型、九交模型表达拓扑关系4交模型以点集拓扑学为基础，通过边界和内部两个点集的交进行定义，并 根据其内容进行关系划分

5、，由于它只通过点集交的“空”与“非空”来进行关系 判别，方法简练，所以在一些商用数据库系统、GIs软件设计中应用广泛。设有空间实体A、B, B（A）、B（B）表示A、B的边界，J（A）、J（B）表示A、B的内部， 二者之间的关系可用式（1）来表示：BOTT衣厉衣石行了（3）i L i（A）n b（b） i（A）n /</?）:（1）(2)r/(A)n i(b)I b<a> n KB)Le(a)n /(B)KA) n B(B)B(A) n B(B)E D1(A) n E(B)1B(A) n E(B)E(A) n E(B)J(2)式(2)中的元素或者为“空”，或为“非空”，总共可

6、产生16种情形。排除现 实世界中不具有物理意义的关系，即可得出 8种面一面关系，13种线一线关系、 3种面一点关系、16种线一点关系、3种点一线关系。这里我们列出它所能描述 的八种面一面关系，如图4。但是由于该方法具有普遍性，许多通过人眼都可明显区分开的一些情形， 利 用该方法却无能为力，如图5。二者的4交模型取值完全相同，都为(-，-, -，-)，但是实际上二者的拓扑关系并不等价。:ffiS 4交模殂可区分的八种区域间空间关系| 这样任意九交模型则将现实世界的每一对象都分成边界、内部和余三部分, 两对象之间的空间关系则可表示成 9种情况，每一种情况又有空与非空两种取 值，9种情况可产生29=

7、512种不同的空间关系情形，但其中有些关系并不存在。9-交模型形式化的描述了离散空间对象之间的拓扑关系，虽然理论上可表达512种关系，但大部分关系无实际意义或是不存在，可以说9-交模型所描述的拓扑关系只是拓扑关系的类别，每一类别又可能有多种情形。由于地理对象又可分为 点、线、面三类，而且其中任意两者的交集又有T、F、*、0、1、2六种取值，因而9-交模型的空间关系又可拓展成 69=10077696种非常复杂的空间情形，形 成9-交扩展模型，并通过对大量的空间关系进行归纳和分类，得出5种基本的空间关系：相离关系(Disjoi nt)、相接关系(Touch)、相交关系(Cross)、包含于 关系(

8、In)、交叠关系(Overlap)。基于此，不少学者又研究更为复杂对象之间更 加复杂、细致的空间关系，如 Cleme nti ni首先对平面上复杂几何对象(不连通 并含有洞的面、闭曲线和自相交的折线集和多点集) 进行了定义，明确了其边界、 内部等的含义，然后用 CBM( Calculated Based Method )对这些对象之间的拓 扑关系进行了描述，并证明了这 5种关系的互斥性20;还有学者提出基于 Voronoi图的混合方法，它利用控件对象的 Voronoi区域作为其外部对原9-交 扩展模型进行了修改。在基于拓扑关系思想的基础上，Egenhofer在点集关系中引入了对象的边界与内部以

9、进一步描述对象间的空间关系，而后建立了描述两个集合对象的拓扑空 间关系模型，即四交模型（Egenhofer and Franzosa ， 1991），在四交模型的基 础上，加上两对象外部的相交关系来表达实体间更为复杂的空间关系即形成了9-交模型（Egenhofer and Herring ， 1994）。九交模型以代数拓扑空间数据模型 的基本几何对象为基准，几何对象被称作元素，元素通过维数进行划分：0维元 素即一个结点；1维元素即链，其两端点为两个结点；2维元素即面，由一系列 互不相交的链构成，任何包含在 n维元素中的元素被称为子部。九交模型将地理空间中的每个元素都分为内部、边界和余三部分，这

10、样任意两个n维元素的空间关系可通过这三部分相互组合来详细描述，设地理空间中有两个地理元素 AB,I（A）、I（B）表示 A B内部，B（A）、B（B）表示A、B边界，E（A）、E（B）表示A、B的余，那么这六部分相互组合求交可形成 3 X 3=9种交集，并构成了拓扑关系描述的基本框架，即九交模型，如表 1。IR(A9B) =I- 5(4) c 1(B) 0B(A) c B(B) = 0表1九交模型i（a）n i（b）I(A) n B(B)I(A) n E(B)B(A) n I(B)B(A) n B(B)B(A) n E(B)E(A) n I(B)E(A) n B(B)E(A) n E(B)为表

11、达方便，九交模型可用3X3的矩阵来描述，由于9种交集中的每一个交 集有空（9 ）与非空（？ B ）两种取值，9种情况可产生29=512种不同的空间关 系，如地理元素A、B相互分离，则用矩阵可表示为：简记为：丨r e oHHrG4,b）= e e-.<9iII拓扑关系表达时侧重于多边形间的关系描述，尤其是在 2维拓扑空间中， 九交模型中多边形（有空多边形和无孔多边形）间拓扑关系的存在需满足一定的 条件，9-交模型中任意多边形之间拓扑关系存在的基本条件有 9个，而在地图表 达时常常遇到无孔多边形间拓扑关系的描述， 相对于有空多边形，无孔多边形的 边界是连续的，且多边形间的拓扑关系在满足 9个

12、基本条件的同时，还需更多限 制条件，如：若两多边形的边界都与对方的内部相交，则两边界也相交等（Ege nhofer and Herri ng, 1994）。根据这些条件，得出任意两多边形（有空或无孔）在 2维拓扑空间中只存 在18种拓扑关系，对于无孔多边形则只存在8中拓扑关系，其它拓扑关系并无 实际意义或不存在。通过对大量空间关系进行归纳和分类， 得出以下几种基本的 空间关系：相离、相接、相交、重合、包含、覆盖，其表示如图 6所示。8 8e e -ee e& w& -d e卡七七.A iiiiE ct?a= si± :tl;?i' A sni 3 :?aid.

13、?A GhiE tcu:h-eV d 0凡倒=e e -e-e e eA4?二e -e -e-e_e e -e_-6-e e_ie Q -e_-e -e 一Aec-ntsin; 33 icntuis AE cjvsrs AA sie E图6 2平面中多边形之间基本的拓扑关系九交模型描述的拓扑关系只是拓扑关系的类别，每一类别又有多种情形，如两个面边界相交，交点可能是一个点，也可能是一条线，这种关系用九交模型模 型表示是一致的，但其拓扑关系并不同，而且这几种基本空间关系被定义为空间 关系的最小集，并具有如下特点：(1) 相互之间不能转化；(2) 能表达所有的复杂空间关系；(3) 能应用于不同维几何目标；(4) 每一种拓扑关系对应唯一的9-交模型矩阵。由于地理对象分点、线、面三类，而且其中任意两者的交集又有 6种取值， 因而9-父模型的空间关系又可拓展成 6种非常复杂的空间关系，形成9-交扩展 模型。基于此，不少学者研究了更为复杂、细致的空间关系，如Cleme ntini首先