拓扑关系和九交模型

认识拓扑关系和九交模型 ---2008301130103    杨文 一、拓扑关系 拓扑关系模型主要以结点、弧段、三角形和多边形作为描述空间物体的最简化元素，运用数学领域中的组合拓扑学来实现对空间简单与复杂物体几何位置和属性信息的完整描述。在该模型中，0 维空间物体代结点，1 维空间物体代表弧段或边，2 维空间物体代表三角形或其它多边形，3 维空间物体则代表四面体或其它多面体，各类型的空间物体含有各自的坐标序列和属性值，并通过基本的邻接、关联、包含、几何和层次关系等建立之间的相互联系，而不同类型的物体相互组合又构成复杂的地理空间对象。除了结点没有方向性，弧段和多边形空间对象都具有方向性，如弧段L 由A、B 结点组成，其方向性可表示为由A-B或由B-A，多边形则可用顺、逆时针来表示其方向性。如下图： 图1 拓扑关系数据模型描述 拓扑关系数据模型中建立拓扑数据结构的关键是对元素间拓扑关系的描述，最基本的拓扑关系包括以下几种： (1)邻接：借助于不同类型拓扑元素描述相同拓扑元素之间的关系，如多边形和多边形的邻接关系。 (2)关联：不同拓扑元素之间的关系，如结点与链、链与多边形等。 (3)包含：面与其它拓扑元素之间的关系，如结点、线、面都位于某一个面内，则称该面包含这些拓扑元素。 (4)连通关系：拓扑元素之间的通达关系，如点连通度、面连通度的各种性质（如距离等）及相互关系。 (5)层次关系：相同拓扑元素之间的等级关系。如国家包含省、省包含市等。 拓扑数据结构中弧段和链具有方向性，通常以顺、逆时针作为方向基准，或将坐标以顺序方式存储。拓扑元素之间的各种拓扑关系构成了对地理空间实体的拓扑数据结构表达，如图2 所示。 图2 拓扑关系空间数据模型示例 不同拓扑元素的拓扑关系可在空间实体几何表示的同时来建立，也可单独建立不同的关系表。若在实体进行几何表达的同时建立拓扑关系，可在关系数据库中存储各类型几何元素数据的同时存储对应的拓扑关系，如图3 所示。 图3 几何数据和拓扑关系数据同表存储 二、四交模型、九交模型表达拓扑关系 4交模型以点集拓扑学为基础，通过边界和内部两个点集的交进行定义，并根据其内容进行关系划分，由于它只通过点集交的“空”与“非空”来进行关系判别，方法简练，所以在一些商用数据库系统、GIs软件设计中应用广泛。设有空间实体A、B，B(A)、B(B)表示A、B的边界，J(A)、J(B)表示A、B的内部，二者之间的关系可用式(1)来表示：                 （1） （2） 式(2)中的元素或者为“空”，或为“非空”，总共可产生16种情形。排除现实世界中不具有物理意义的关系，即可得出8种面一面关系，13种线一线关系、3种面一点关系、16种线一点关系、3种点一线关系。这里我们列出它所能描述的八种面一面关系，如图4。 但是由于该方法具有普遍性，许多通过人眼都可明显区分开的一些情形，利用该方法却无能为力，如图5。二者的4交模型取值完全相同，都为（-Φ，-Φ，-Φ，-Φ），但是实际上二者的拓扑关系并不等价。 九交模型则将现实世界的每一对象都分成边界、内部和余三部分，这样任意两对象之间的空间关系则可表示成9 种情况，每一种情况又有空与非空两种取值，9 种情况可产生29=512种不同的空间关系情形，但其中有些关系并不存在。9-交模型形式化的描述了离散空间对象之间的拓扑关系，虽然理论上可表达512 种关系，但大部分关系无实际意义或是不存在，可以说9-交模型所描述的拓扑关系只是拓扑关系的类别，每一类别又可能有多种情形。由于地理对象又可分为点、线、面三类，而且其中任意两者的交集又有T、F、*、0、1、2 六种取值，因而9-交模型的空间关系又可拓展成69=10077696 种非常复杂的空间情形，形成9-交扩展模型，并通过对大量的空间关系进行归纳和分类，得出5 种基本的空间关系：相离关系(Disjoint)、相接关系(Touch)、相交关系(Cross)、包含于关系(In)、交叠关系(Overlap)。基于此，不少学者又研究更为复杂对象之间更加复杂、细致的空间关系，如Clementini 首先对平面上复杂几何对象（不连通并含有洞的面、闭曲线和自相交的折线集和多点集）进行了定义，明确了其边界、内部等的含义，然后用CBM（Calculated Based Method）对这些对象之间的拓扑关系进行了描述，并证明了这5 种关系的互斥性[20]；还有学者提出基于Voronoi图的混合方法，它利用控件对象的Voronoi 区域作为其外部对原9-交扩展模型进行了修改。 在基于拓扑关系思想的基础上，Egenhofer 在点集关系中引入了对象的边界与内部以进一步描述对象间的空间关系，而后建立了描述两个集合对象的拓扑空间关系模型，即四交模型（Egenhofer and Franzosa，1991），在四交模型的基础上，加上两对象外部的相交关系来表达实体间更为复杂的空间关系即形成了9-交模型（Egenhofer and Herring，1994）。九交模型以代数拓扑空间数据模型的基本几何对象为基准，几何对象被称作元素，元素通过维数进行划分：0 维元素即一个结点；1 维元素即链，其两端点为两个结点；2 维元素即面，由一系列互不相交的链构成，任何包含在n 维元素中的元素被称为子部。 九交模型将地理空间中的每个元素都分为内部、边界和余三部分，这样任意两个n 维元素的空间关系可通过这三部分相互组合来详细描述，设地理空间中有两个地理元素A、B， I（A）、I（B）表示A、B 内部，B（A）、B（B）表示A、B 边界，E（A）、E（B）表示A、B 的余，那么这六部分相互组合求交可形成3×3=9 种交集，并构成了拓扑关系描述的基本框架，即九交模型，如表1。 表1 九交模型 I(A)∩I(B) I(A)∩B(B) I(A)∩E(B) B(A)∩I(B) B(A)∩B(B) B(A)∩E(B) E(A)∩I(B) E(A)∩B(B) E(A)∩E(B) 为表达方便，九交模型可用3×3 的矩阵来描述，由于9 种交集中的每一个交集有空（θ）与非空（¬θ）两种取值，9 种情况可产生29=512 种不同的空间关系，如地理元素A、B 相互分离，则用矩阵可表示为： 简记为： 拓扑关系表达时侧重于多边形间的关系描述，尤其是在2 维拓扑空间中，九交模型中多边形（有空多边形和无孔多边形）间拓扑关系的存在需满足一定的条件，9-交模型中任意多边形之间拓扑关系存在的基本条件有9 个，而在地图表达时常常遇到无孔多边形间拓扑关系的描述，相对于有空多边形，无孔多边形的边界是连续的，且多边形间的拓扑关系在满足9个基本条件的同时，还需更多限制条件，如：若两多边形的边界都与对方的内部相交，则两边界也相交等（Egenhofer and Herring，1994）。 根据这些条件，得出任意两多边形（有空或无孔）在2 维拓扑空间中只存在18 种拓扑关系，对于无孔多边形则只存在8 中拓扑关系，其它拓扑关系并无实际意义或不存在。通过对大量空间关系进行归纳和分类，得出以下几种基本的空间关系：相离、相接、相交、重合、包含、覆盖，其表示如图6 所示。 图6  2平面中多边形之间基本的拓扑关系 九交模型描述的拓扑关系只是拓扑关系的类别，每一类别又有多种情形，如两个面边界相交，交点可能是一个点，也可能是一条线，这种关系用九交模型模型表示是一致的，但其拓扑关系并不同，而且这几种基本空间关系被定义为空间关系的最小集，并具有如下特点： (1)相互之间不能转化； (2)能表达所有的复杂空间关系； (3)能应用于不同维几何目标； (4)每一种拓扑关系对应唯一的9-交模型矩阵。 由于地理对象分点、线、面三类，而且其中任意两者的交集又有6 种取值，因而9-交模型的空间关系又可拓展成69 种非常复杂的空间关系，形成9-交扩展模型。基于此，不少 学者研究了更为复杂、细致的空间关系，如Clementini 首先对平面上复杂几何对象（不连通并含有空的面、闭曲线和自相交的折线集和多点集）进行了定义，明确了边界、内部等的含义，然后用CBM（Calculated Based Method）对这些对象间的拓扑关系进行了描述，并证明了基本空间关系的互斥性（Clementini,1996）；还有学者提出基于Voronoi 图的混合方法，它利用空间对象的Voronoi 区域作为其外部对原9-交扩展模型进行了改进（Chen，1997）。