空间关系描述与推理

1、空间关系描述及其推理研究生课程1报告提纲一、空间关系基本概念二、拓扑关系描述三、方向关系描述四、邻近关系描述五、距离关系描述六、空间关系应用七、总结2空间关系及其描述 空间关系指空间对象在几何上存在的一种相互依赖的概念，主要包括： 空间关系描述主要建立一种形式化的模型，通过该形式化的模型，能够把空间对象的几何结构描述为人们能够理解的符号或词语，这些符号或词语就是对空间关系的定性描述。 拓扑关系 方向关系 邻近关系 距离关系3拓扑设X是一个非空集合。X的一个子集族称为X的一个拓扑，如果它满足： （1）X和空集都属于； （2）中任意多个成员的并集仍在中； （3）中有限多个成员的交集仍在中。 定义中

2、的三个条件称为拓扑公理。条件（3）可以等价的换为中两个成员的交集仍在中。 称集合X连同它的拓扑为一个拓扑空间，记作（X,）。 称中的成员为这个拓扑空间的开集。 4拓扑常用集合来代指一个拓扑空间，如拓扑空间X，拓扑空间Y等。 给出某集合的一个拓扑就是规定它的哪些子集是开集。 1.欧几里德空间在通常开集的意义下是拓扑空间，它的拓扑就是所有开集组成的集合。 2.设X是一个非空集合。则集合t：X,是X的一个拓扑。称t为X的平凡拓扑。显然（X,t）只有两个开集，X和。 5拓扑3.设X是一个非空集合。则X的幂集T=2X也是X的一个拓扑。称T为X的离散拓扑。显然X的任意子集都是(X,T)的开集。 4.一个具

3、体的例子。设X=1,2。则X,1,2是X的一个拓扑，但X,1,2不是拓扑。（自己想想为什么） 6拓扑学拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。我国早期曾经翻译成“形势几何学”、“连续几何学”、“一对一的连续变换群下的几何学”，但是，这几种译名都不大好理解，1956年统一的数学名词把它确定为拓扑学，这是按音译过来的。 7拓扑学拓扑学是几何学的一个分支，但是这种几何学又和通常的平面几何、立体几何不同。通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。

4、8拓扑学在通常的平面几何里，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但是，在拓扑学里所研究的图形，在运动中无论它的大小或者形状都发生变化。在拓扑学里没有不能弯曲的元素，每一个图形的大小、形状都可以改变。例如，欧拉在解决哥尼斯堡七桥问题的时候，他画的图形就不考虑它的大小、形状，仅考虑点和线的个数。 9拓扑性质 之拓扑等价在拓扑学里不讨论两个图形全等的概念，但是讨论拓扑等价的概念。比如，尽管圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。10拓扑等价在一个球面上任选一些点用不相交的线把它们连接起来，这样球面就被这些线分成许多块。在拓扑变换下，点

5、、线、块的数目仍和原来的数目一样，这就是拓扑等价。一般地说，对于任意形状的闭曲面，只要不把曲面撕裂或割破，他的变换就是拓扑变换，就存在拓扑等价。 11环面不具有这个性质。把环面切开，它不至于分成许多块，只是变成一个弯曲的圆桶形，对于这种情况，我们就说球面不能拓扑的变成环面。所以球面和环面在拓扑学中是不同的曲面。 直线上的点和线的结合关系、顺序关系，在拓扑变换下不变，这是拓扑性质。在拓扑学中曲线和曲面的闭合性质也是拓扑性质。 12通常讲的平面、曲面通常有两个面，就像一张纸有两个面一样。德国数学家莫比乌斯在1858年发现了莫比乌斯曲面。这种曲面就不能用不同的颜色来涂满两个侧面。 13拓扑关系 to

6、pological relation指满足拓扑几何学原理的各空间数据间的相互关系。即用结点、弧段和多边形所表示的实体之间的邻接、关联、包含和连通关系。如：点与点的邻接关系、点与面的包含关系、线与面的相离关系、面与面的重合关系等。 拓扑关系是指图形元素之间相互空间上的连接、邻接关系并不考虑具体位置.这种拓扑关系是由数字化的点、线、面数据形成的以用户的查询或应用分析要求进行图形选取、叠合、合并等操作 14拓扑关系描述基本概念 什么是拓扑关系？ 拓扑关系指在拓扑变换下保持不变的性质，如旋转、平移和尺度变化 拓扑关系是一种定性关系，而不是定量的 什么是拓扑关系描述模型？ 一种形式化的模型，它能够用数学

7、的手段区别不同的拓扑关系的，而不是仅仅从直观感觉上区分 描述模型所能区分的拓扑关系应该和人们直观感觉所区分的拓扑关系一致，这包括区分的关系种类数和含义的一致性15拓扑关系描述九交模型(Egenhofer, 1991)16拓扑关系描述九交模型(Egenhofer, 1991) A的内部和B的内部的交，记作 A的内部和B的边界的交，记作 A的内部和B的外部的交，记作 A的边界和B的内部的交，记作 A的边界和B的边界的交，记作 A的边界和B的外部的交，记作 A的外部和B的内部的交，记作 A的外部和B的边界的交，记作 A的外部和B的外部的交，记作17拓扑关系描述面/面拓扑关系(Egenhofer, 1

8、991)DisjointMeetOverlapContainEqualCoveredByInsideCover面与面间有效的拓扑关系共有8个18拓扑关系描述线/面拓扑关系(Egenhofer, 1991)LR11LR12LR13LR22LR31LR32LR33LR42LR44LR46LR62LR64LR66LR71LR72LR73LR74LR75LR76线与面间有效的拓扑关系共有19个19拓扑关系描述线/线拓扑关系(Egenhofer, 1991)LL1LL2LL3LL4LL5LL6LL7LL8LL9LL10LL11LL12LL13LL14LL15LL16LL17LL18LL19LL20LL2

9、1线与线间有效的拓扑关系共有33个，这里只给出了21个20拓扑关系描述Voronoi图模型(陈军等,2001) 九交模型的缺点： 九交模型中的外部太大。对于一个面积有限的空间目标而言，它的外部是无限的。这导致任意两个目标的外部的交总是非空。ABABBAC 外部的无限性，导致目标的外部与边界和内部是线性相关的，使得外部在九交模型中的作用不是很明显。 只能描述简单目标（不带洞而单一的实体）间的拓扑关系，而不能描述复杂目标（带洞或由几个分离目标组成的目标）间的拓扑关系。21拓扑关系描述Voronoi图模型(陈军等,2001) Voronoi图的定义 设有空间目标簇P=P1, P2, P3, , Pn

10、, PiRN, V(Pi) = y | Dist(y, Pi) Dist(y, Pj) 对所有j，式中Dist(y, Pi)点y到Pi的最小距离，V(Pi)被称为空间目标的Voronoi区域，V(P)=V(P1),V(P2),V(Pn)则被称为Voronoi图 Voronoi能把对象间的邻接定义为对应Voronoi区域的邻接，采用等距离原则确定任一物体所处的Voronoi区域的边界线，从而将三种基本空间对象点、线和面纳入某种邻接物的集合 构成V(Pi)的点到Pi的距离比到Pj(i, j=1,n, ji)的距离要近，从而可以构造出点、线、面不同维空间对象的Voronoi区域。点和线、面，线和面之

11、间的Voronoi区域边界线是曲线，而点与点之间，线和线之间的Voronoi区域边界线是直线。 22拓扑关系描述Voronoi图模型(陈军等,2001) Voronoi图的性质 势力范围特性。每个空间对象都有一个唯一的Voronoi区域与之对应。 局域动态特性。分析表明，Voronoi的平均边数不超过6。删除或增加一个生长目标，一般只影响周围6个左右的相邻空间生长目标，即只会影响局部范围内的目标。 侧向邻近特性。若两个空间对象之间没有其它对象，则它们的Voronoi区域必然有一个公共边。通过判断Voronoi区域是否有公共边，就可判断连个对象是否是侧向邻近。 与Delaunay三角形的对偶性。

12、如果空间生长对象满足非共线特性，将其中具有公共Voronoi边的生长点对相连，就可得到Delaunay三角形。23拓扑关系描述Voronoi图模型(陈军等,1997) 空间对象的Voronoi图24拓扑关系描述Voronoi图模型(陈军等,1997) 两个重叠面对象的Voronoi图25拓扑关系描述Voronoi图模型(陈军等,1997) 两个相交线对象的Voronoi图26拓扑关系描述Voronoi图模型(陈军等,1997) 线和面相交的Voronoi图27拓扑关系描述Voronoi图模型(陈军等,2001) 基于Voronoi图的九交模型 每一个空间对象的Voronoi图都可以被分成三部分

13、，即Voronoi区域，空间对象的边界，空间对象的内部。 V9I模型用对象的Voronoi区域代替九交模型中的外部，而对象的边界和内部与九交模型保持一致。V9I定义： 若两个空间对象相邻时， 非空；若被其它目标隔开，则 为空，因而空V9I模型用可以区分相邻和相离两种拓扑关系，而9交模型把二者均描述为相离。28拓扑关系描述Voronoi图模型(陈军等,1997)29拓扑关系描述Voronoi图模型(陈军等,1997)30基于维数扩展的九交模型能够很好地将两个空间目标的交集是空、点、线或面4种情况区分开但同四元矩阵拓扑空间关系描述框架一样, 不能描述邻接和相离等空间目标分离开的拓扑关系基于voro

14、ni图的九交模型在区分地理空间中邻近关系和相离关系时具有一定的优势31目前, 空间拓扑关系形式化描述方法存在的主要问题体现在基于点集拓扑的空间关系描述框架无法描述相离的和没有公共元素的空间目标间的拓扑空间关系, 即存在所谓的模型描述错误或者无法描述的情形32空间拓扑关系形式化描述模型的发展结合人们空间认知的理论模型研究,形式化描述模型对空间目标间距离较近等复杂情况下空间方向关系的描述常会出现与人们认知不一致的情况。融合不同的空间关系描述方法, 进一步完善空间关系的理论模型, 如方向关系的判定准则以及对度关系的形式化描述等, 建立更符合人类认知模式的统一的空间关系描述体系, 使得对地理空间目标间

15、关系的刻画更准确、更全面33空间拓扑关系的推理由空间对象已知的空间拓扑关系信息，推测和确定未知的其可能成立的空间拓扑关系。例如，若已知空间对象A 和B 的拓扑关系为R1 （ A，B），B 和C 的拓扑关系为R2 （ B，C），通过已有的空间知识进行空间分析，从而可推导出A 和C 之间可能存在的空间拓扑关系R3 （ A，C）。34空间拓扑关系的推理分类一种是在对动态空间目标建模时，空间目标之间的拓扑关系随着时间的变化而变化，在已知空间拓扑关系初始状态和空间目标的运动轨迹或其他相关度量指标时确定下一时刻未知的两空间目标之间的可能拓扑关系。35另一种：要求两空间目标之间的空间拓扑关系，但直接获取它们

16、之间相关空间关系信息困难，而仅能获得它们与其他另一空间目标之间的关系，基于获得的空间拓扑信息，用空间推理的方法推出两空间对象间的空间拓扑关系。36第一种情形，可通过构建拓扑概念邻域图的方法进行定性推理；第二种情形则可利用空间拓扑关系的组合运算的方法进行分析。37Cui 和Cohn 等人给出了一套空间逻辑用来推理空间数据库中的空间对象间的拓扑关系。Abdelmoty 等基于广义的交模型定义了线/面和面/面多种空间对象类型拓扑关系推理组合表。Renz J 等研究了基于区域连接演算（RCC）进行空间拓扑关系推理的理论和方法。38基于RCC-8 的空间区域关系的推理组合表39“*”表示全部关系。但Re

17、nz J 的工作没有涉及点、线等空间对象的空间关系的推理，对空间区域的形状等具有很强的限制，不利于扩展。Li S J 等研究了基于一致性组合表（RCC8-CT），对RCC 模型进行了扩展分析，给出了RCC8 组合表的扩展形式。40为了定性描述和推理形状、大小和位置等随时间发生变化的空间对象间的空间拓扑关系，Egenhofer 等9基于九交模型给出了拓扑距离的定义，给出了相关的概念邻域图，基于概念领域图进一步分析了不同动态变化情形下的空间拓扑关系转变路径。41Egenhofer 的研究成果针对空间面对象的空间关系推理，对点和线对象的空间关系推理无效。郭庆胜等在线和面空间拓扑关系组合描述的基础上，

18、对线与面的组合推理方法进行了研究，给出了线与面的拓扑关系组合推理表。42包含点和线的多维空间对象的空间关系表示和推理王生生和刘大有将点和线对象视为特殊的区域，提出了能直接用RCC 理论描述空间多维对象拓扑关系的MRCC 理论，推导出36 种基本MRCC 关系，讨论了基于概念邻域图和复合表的MRCC 推理。4344拓扑关系描述拓扑关系相似性 概念邻居图45自然语言空间关系以线/面为例那些关系与语言“道路进入公园”基本一致？那些关系与语言“道路穿过公园”基本一致？46自然语言空间关系道路进入公园(Mark, et al., 1994)19个线/面拓扑关系与自然语句“道路进入公园”的一致性程度471

19、9个线/面拓扑关系与自然语句“道路穿过公园”的一致性程度自然语言空间关系道路穿过公园(Mark, et al., 1994)48自然语言空间关系道路穿过公园(Mark, et al., 1994)穿过公园的道路必须属于这5个关系中的一个穿过公园的道路不能完全在公园外部或位于其边界上穿过公园的道路不能有端点在公园内49方向关系描述基本概念 方向关系要素 一个参照对象、一个目标对象 主方向概念。人们认知的方向概念是离散的，能分辨的方向概念个数有限，并且以词语描述为主。如，东、南、西、北等 主方向个数，即用多少个方向概念来描述空间对象间的方向关系 方向区域。为确定目标对象位于参照对象的那个方向，必须

20、根据参照对象的空间形状和范围，按照主方向的个数，把参照对象所在空间划分成与主方向个数相等的空间区域 50方向关系描述评价描述方法的准则 能够统一描述不同维对象之间的方向关系 对参照对象和目标对象的空间形状、大小和岛屿是敏感的 ABBABABA51方向关系描述基本概念 能够与人们的认知概念一致 北 A A A北北 是可推理和比较的 52方向关系描述基本特征 方向关系描述的实质就是确定一个方向关系模型，难点在于采用何种方法对参照对象所在的空间范围进行划分，使得基于这种划分所得到的方向概念与人们的认知概念较为一致 根据需求确定方向关系中原子方向的个数 选择方向区域划分方法，确定每个方向的空间区域 把

21、目标对象映射到根据参照对象确定的方向区域中去，计算目标对象与参照对象之间的方向关系53方向关系描述锥形方法(Peuquet , 1987)北西南东北西北东北西南东南西东南 4个主方向：东、南、西、北 8个主方向：东、南、西、北、东北、西北、东南、东北 锥形方向区域、等角度划分 把参照对象和目标对象均当作点处理 锥形方法特点54方向关系描述投影方法(Frank,1995)西东北南东北东南西南西北西东北南北西南东东北东南西北西南 方向区域为半平面或矩形区域 仍然把参照对象当作点处理55方向关系描述MBR模型(Papadias,1995)AB 利用参照对象和目标对象分别在x轴和y轴上投影间的关系来区

22、分和描述方向关系 本质是对参照对象和目标对象均采用它们的外接矩形来近似56方向关系描述MBR模型(Papadias,1995)NorthwestRestricted_northNortheastRestricted_westSouthwestRestricted_southSoutheastRestricted_eastnorth_west(p, q) X(pc)Y(qc) restricted_north(p, q) X(pc)=X(qc)Y(pc)Y(qc)north_east(p, q) X(pc)X(qc) Y(pc)Y(qc)restricted_west(p, q) X(pc)X(

23、qc) Y(pc)=Y(qc)south_west(p, q) X(pc)X(qc) Y(pc)Y(qc)restricted_south(p, q) X(pc)=X(qc) Y(pc)X(qc) Y(pc)700 and areaval5) or (Tw.tpopulation10000 and NORTH(Su.Location, Tw.Location) and DISJOINT(Su.Location, Tw.Location) 找出所有与高速公路距离不超过5公里或者在城镇的北部且在城镇外的所有超市101空间关系应用基于图标的查询(Morris,2004)SELECT * FROM r

24、oad As Ru, country As CtWHERE ( Rd.type = “Motorway” and Ct.tpopulation50000 and CROSS(Ru.Location, Ct.Location) 找出所有高速公路和城镇，城镇人口50000，且高速公路穿越城镇102空间关系应用基于草图的空间查询 扩展SQL是基于文本的查询语言，空间关系的文本描述是模棱两可的，很容易造成误解释或误匹配，尤其是在多语言环境中，同一个词语可能有不同的含义 基于图标的查询语言使用了可视化的图标和界面来描述和组织查询语句，优点是把用户从记忆繁琐而复杂的语法规则中解放出来。但图标查询的语法和句

25、法与结构化SQL是类似的，仅仅使用一些由系统预定义的标准图标很难真实而准确地描述对象间的空间关系，仍然会造成误匹配，并且由于不能从细节和数量上描述空间关系，导致匹配的结果集太大，其中一些可能不是用户所期望的结果。 在基于草图的空间中，用户可以用鼠标、笔或手在触摸屏上画他要查询的空间对象结构，形成草图，包括对象间相对大小比例、空间关系的细节信息以及空间对象形状等。相对图标而言，草图包含了明确而详细的信息，可以做为查询条件提交给GIS，通过空间关系相似性匹配就可检索到用户所需的数据。 在基于草图的空间中，草图的输入方式、管理、组织和描述非常重要。103空间关系应用基于草图的空间查询 (Blaser,2000)104空间关系应用空间查询语言实例介绍4 基于草图的查询 105空间关系应用空间场景的相似性 106空间关系推理基本概念 GIS中空间关系推理就是把人们这种推理能力通过某种定理或规律表达处理，以方便计算机实现。具体的讲，空间关系推理就是根据两个已知的空间关系，利用空间关系间蕴藏的规律和知识来推理未知的空间关系 这种推理不需要进行大量的几何计算，