空间关系课件

空间关系周晓光Zxg@mail.csu.edu.cn测绘与国土信息工程系内容空间拓扑关系的描述四元交模型（4I模型）九元交模型（9I模型）基于Voronoi图的九元交模型（V9I模型）空间拓扑关系的表达空间拓扑关系的计算与查询时空拓扑关系及其应用空间方向关系的描述空间关系的概念空间关系是数字环境下空间认知、空间分析、空间推理的前提和基础。空间关系包括由空间物体的几何特性（如空间物体的地理位置与形状）引起的空间关系，如：距离、方位、邻近、包含、连通性、相似性等；由空间对象的几何和非几何属性共同引起的空间关系，如空间分布现象中的统计相关、空间自相关、空间相互作用、空间依赖等。时间上的先后关系；成因上的因果关系等。

空间拓扑关系描述陈军,2002,Voronoi动态空间数据模型

空间拓扑关系描述

交互模型：是运用空间目标的整体，而不是将目标分解为更细的组成部分，去区分和定义空间关系，最具代表性的是Randell等人提出的空间逻辑（spatiallogic）。缺点：需要预先假设目标间的可能的关系，不可能保证完备性，但对每一种可能的关系，描述结果是唯一的。交叉模型：4元组9元组模型基于Voronoi图的9元组模型（V9I）交叉模型的内部、边界、外部的定义补A-边界

A内部A

全域X对于二维简单面状目标而言，其边界

A为连续曲线，内部A

应是连通的，且A为一个闭包，

A∪A

∪A-1=X，X为整个连续空间。交叉模型的不包括的情况a.目标不连通b.目标为非闭包四元组模型四元组模型将空间目标看作是点集，利用两个点集间边界、内部之间的交，构成如下式所示的4元组： R4I(A,B)= 其中

A、A

是目标A的边界和内部，

B和B

是目标B的边界和内部。4元组区分的简单面域间的8种空间拓扑关系

ABABABBAABABABBA序号图例语义解释4元组值1A、B相离（不相交）2

A、B相接3

A、B相等4

A包含于B，且两者边界不交5

A包含B，且两者边界不交6

A包含于B，且两者边界相交7

A包含B，且两者边界相交8

A、B部分重叠四元组模型对线目标的内部、边界的定义外部A-1内部A

边界

A简单线状目标应满足以下条件：(a)有且仅有两个端点，

A={pa,pb}，且pa≠pb(b)边界

A与内部A

不相交，即

A∩A

=

。(c)内部A

与A

不相交，即A

∩A

=

。非简单线性目标举例16种简单线状目标间的拓扑空间关系1

序号图例语义解释4元组值其它4元组值等价图例1

A与B相离（不相交）

2A的两边界点分别与B的两边界点相接3A的一个边界点与B的内部相接4

B的一个边界点与A的内部相接5

A的内部与B的内部相交6A的一个边界点与B的一个边界点相接，且A的另一个边界点与B的内部相接

7B的一个边界点与A的一个边界点相接，且B的另一个边界点与A的内部相接

ABABABABABBAABABABABAB16种简单线状目标间的拓扑空间关系2

ABABABABBAABAABABBABABABABABABABAB8A的一个边界点与B的一个边界点相接，且A的内部与B的内部相交9

A的一个边界点与B的内部相接，且B的一个边界点与A的内部相接

10

A的一个边界点与B的内部相接，且A的内部与B的内部相交11

B与A的内部重合

12

A的一个边界点与B的一个边界点相接，A的另一个边界点与B的内部相接，且B的另一个边界点与A的内部相接，

13

A的一个边界点与B的一个边界点相接，A的另一个边界点与B的内部相接，且A的内部与B的内部相交

14

A的边界点与B的内部相接，B的一个边界点与A的内部相接，且A的内部与B的内部相交

15

A的一个边界点与B的一个边界点相接，A的另一个边界点与B的内部相接，且A的内部与B的内部相交

16

A的一个边界点与B的一个边界点相接，A的另一个边界点与B的内部相接，B的另一个边界点与A的内部相接，且A的内部与B的内部相交

基于边界、内部和外部的9元组

Egenhofer等（1991）提出将空间目标的补（complements）引入空间关系描述框架。其理由是，对于一个拓扑空间的点集A，其边界（

A）、内部（A

）和补（A-）构成整个拓扑空间，只有把补纳入拓扑空间关系描述框架，才可能得到完备的拓扑空间关系描述。

9元组表达式用空间物体A的边界（

A）、内部（A

）、补（A-）与空间物体B的边界（

B）、内部（B

）、补（B-）两两之间的交集，构成下式所示的空间关系描述的9元组框架：

9元组描述框架的特点与4元组相比：9元组增加了

A∩B-，A

∩B-，A-∩

B，A-∩B

和A-∩B-5个与“补”有关的交集

9元组所区分的面\面拓扑关系的数目与4元组一样

在描述两组线\线目标、线、面目标时，其描述能力比4元组要强，9元组区分出33种不同的线\线关系

9元组比4元组能区分更多线\线关系

ABABABABABR4I(A,B)R9I(A,B)补在区分线\线关系中的特点

当两个简单线状目标具有相离、相接、穿越（cross）和部分重叠关系时，与“补”有关的5个交集均为非空当一个线状目标落入另一个线状目标的内部（如equal，cover）时，与“补”有关的某些元素会为非空值，与“补”有关的交集发挥作用

补在区分线\线关系中的作用

9员组模型区分了33种线\线目标之间的空间拓扑关系

在4元组下不能区分、在9元组下可以区分的线与线关系示例ABABABABABAB编号图示4元组取值9元组取值简单语意解释1A的两个边界点与B的两个边界点重合

A的一个边界点在B的一个边界点上

2

A的两个边界点在B的内部

A的一个边界点在B的内部

3

B的两个边界点在A的内部

B的一个边界点在A的内部补在区分面状目标间空间关系的作用

当两个面状目标之间的拓扑关系由相离（disjoint）、相接（meet）逐步地转化为部分重叠（partiallyoverlap）时，与“补”有关的5个交集均为非空

补在区分线\面关系中的作用

9员组模型区分了19种线\面目标之间的空间拓扑关系

9元组模型存在的若干问题1两个目标的“补”高度重叠

无法区分不同的空间相离关系

A的“补”是C及其自身的线性函数

当C为常量时，A的外部（定义为补）与其自身线性相关.这就解释了为什么在一些情况下9元组与4元组效果相同（Chenetal.,2000）。

线目标的内部与其外部相接一维空间中线目标的边界将其内部与外部隔离开；

根据点集拓扑的定义，一个空间目标的边界将其内部与外部隔离开来，这意味着二维空间中的线目标只有边界，内部应为空，且其边界为线目标本身，而不是其两个边界点

。边界（端点）内部（线）外部（晕渲部分）线目标的内部与其外部相接简单空间目标的限制

9元组框架将所研究的空间目标限定为：简单点（无大小、无形状）、简单线（不能够自交，有且有两个不重合的边界点）、简单面（区域边界必须连通）

9元组不能区分含空洞目标间的空间关系

空间目标的“补”难以计算难以计算与“补”有关的5个交集

A∩B-，A0∩B-，A-∩

B，A-∩B0和A-∩B-。难以根据空间目标的几何数据直接计算两个目标间的交集难以根据9元组值去检索那些具有某种空间关系的目标这给基于9元组的空间关系操作带来了较大困难

基于Voronoi图的9元组描述框架

用每一空间目标的“势力范围”作为其外部[Chen,Li,Li,.Gold,1997]。在给定空间边界的情况，空间目标的Voronoi势力范围一般是有限的，每一个目标的Voronoi势力范围与有限个目标的Voronoi势力范围相邻

平面普通Voronoi图的定义对P={p1,p2,...pi,pj,...pn}，(2≤n<∞,

，i≠j，i，j

In)，由

给出的区域称为生长点pi

的Voronoi多边形,而所有生长点p1,p2,...,pn

的Voronoi多边形的集

构成了P的Voronoi图。离散生长点的Voronoi图

若用形象的比喻来说，可看作是这组生长点以等同速度向四周扩张，直到相遇为止，扩张过程全部结束

点状生长目标的Voronoi图及其基本元素

Voronoi图的若干重要性质

势力范围特性（influenceregion）侧向邻近特性（lateraladjacency）线性特性（linearbehaviour）

局域动态特性（localdynamization）与Delaunay三角网对偶(DualofDelaunaytriangulation)

势力范围特性对一个空间生长目标而言，凡落在其Voronoi多边形范围内的空间点均距其最近。因此，该Voronoi多边形在一定程度上反映了其影响范围，或称势力范围

Voronoi势力范围的定义点目标：指点的Voronoi区域自身；线目标：指线的Voronoi区域自身；不含空洞的实心面目标：指面的Voronoi区域自身；含有空洞的面目标（环状目标）：指环的Voronoi区域自身及环的空洞区域的并集。

点、线、面的Voronoi势力范围

侧向邻近特性房屋Voronoi边道路线性特性Voronoi图是具有n个多边形和至少三个节点的平面图(planargraph)

nv≤2n-5这表明Voronoi图的size随空间生长目标个数n成线性比例增加，具有并不复杂的结构。这种线性特性是Voronoi图得以广泛应用的主要原因之一。最大空圆

对Voronoi图中的每一个节点（vertex）qi

Q{q1,…,qnv}来说,至少有三条Voronoi边通过。换言之，若过qi作一圆Ci，则Ci将通过三个或更多的生长点。而Ci是过qi的最大空圆（thelargestemptycircle）

局域动态特性

每一个Voronoi多边形的平均边数不超过6。这表明删除或增加一个空间生长目标，一般只影响6个左右的相邻空间生长目标。换言之，对Voronoi图的修改只影响局部范围。

与Delaunay三角网对偶

Delaunay三角形的边数和Voronoi图的边数是相同的。若将Delaunay边的端点称为Delaunay结点，其实际上就是对应的Voronoi图的生长点。基于Voronoi图的9元组（V9I）Av、Bv分别为A、B的

Voronoi区域

V9I区分相离关系

V9I区分其余几种区域空间关系

abcBAABABABdefg基于Voronoi距离的k阶邻近

设任意两个空间目标Pi，Pj之间的Voronoi区域的最少个数k为其间的Voronoi距离，记为vd(Pi,Pj)，一般地vd(Pi,Pj)≥0，当Pi=Pj时，vd(Pi,Pj)=0；我们规定当Pi

Pj

或Pi

Pj时，vd(Pi,Pj)=0。对于图3–30来说，vd(A，A)=0，vd（A，B）=1，vd（A，C）=1，vd（A，D）=2，vd（A，G）=3。当Voronoi距离值为0时，两目标最邻近，值为1时两目标较邻近，值越大说明邻近程度越弱。

面状目标的Voronoi距离图

ACDEFGBvd(A，A)=0vd（A，B）=1vd（A，C）=1vd（A，D）=2vd（A，G）=3。当Voronoi距离值为0时，两目标最邻近，值为1时两目标较邻近，值越大说明邻近程度越弱。

k阶邻近关系

设Pi,Pj

是空间目标集合P中的任意两个目标，如果其Voronoi区域V（Pi），V（Pj）存在，且vd(Pi,Pj)为k，则称Pi与Pj之间存在k阶邻近关系。<Pi,

kAdj,

Pj><=>vd(Pi,Pj)=k空间拓扑关系描述存在的问题

包含空洞等复杂对象的空间拓扑关系的描述问题；对线状目标间空间拓扑关系的描述方法；对体状目标间空间拓扑关系的描述方法；BABABA一个连续边界区域与一非连续边界区域之间的三种拓扑关系Threetopologicallydistinctrelationsbetweentwo-dimensionalobjectswithholes体状目标间空间拓扑关系的描述(郭薇,陈军,1997）现有方法无法区分地块间的三种相邻关系BAab四元组模型无法区分地块间的三种相邻关系BAabBAab（1）（2）（3）

BB0A0

相邻（meet）

A

空间拓扑关系的表达陈军,2002,Voronoi动态空间数据模型

龚健雅，2001，地理信息系统基础传统GIS中拓扑关系的显式表达

拓扑关系的表达拓扑关系的表达方法：全显式部分显式隐式表达全全显式表达一般包括：结点—弧段关系表弧段—面域关系表面域—弧段关系表弧段—结点关系表弧段—结点--面域关系表面域—弧段关系表弧段—结点关系表结点—弧段关系表弧段—面块关系表弧段—结点--面块关系表ARC/INFO图层下的点、弧段和多边形数据组织

空间数据文件LAB点文件ARC弧段文件PAL多边形文件PAXPAL的索引属性数据文件ARX弧段索引AAT弧段属性PAT多边形属性TIC配准点文件BND边界文件Coverage图层文件ARCINFO的拓扑数据结构ARC/INFO软件记录空间数据及其拓扑关系的文件主要有LAB、ARC、PAL、AAT、NAT、PAT等组成.

(1)

点文件LAB-LAB文件用来记录点要素(如井位、电线杆和水塔等)的信息

点文件LAB-LAB文件用来记录点要素(如井位、电线杆和水塔等)的信息用户标识码内部标识码XY坐标弧段文件ARC弧段内部标识码标志信息弧段用户标识码起始结点码终止结点码左多边形右多边形点数坐标串

ARC文件用来表示线状要素、多边形的边界或二者同时表示.一个线状要素可以由许多弧段组成-每个弧段都分配一个用户标识码,其位置和形状则由一系列(X,Y)坐标对来表示.

多边形信息文件PAL/AAT

一个多边形信息由一组拓扑上组成多边形的弧段及于多边形内的一个标识点来定义.用标识点给多边形指定一个用户标识码,并通过标识码与多边形属性文件中的相应记录建立联系.多边形拓扑信息主要存在PAL文件中,其存贮结构为:

多边形内部标识码标志信息组成多边形的弧段数n弧段1内部标识码始(终)结点码左(右)多边形内部标识码……弧段n内部标识码始(终)结点码左(右)多边形内部标识码属性数据的表达空间目标的属性特征分类：类别特征：即该对象是什么一般用类别编码来表达说明信息：解决两个同类目标的不同特征问题：如道路的宽度、等级、路面质量等用属性数据结构和表格说明来表达Geostar的空间数据及拓扑关系表达Geostar的属性数据及与空间数据的联接1Geostar的属性数据及与空间数据的联接2拓扑数据组织与维护的问题

开销大拓扑关系的数据组织较为复杂GIS拓扑数据模型的数据结构非常复杂，与拓扑关系相关的数据在总数据量中占有较大比重

在Arc/Info的13种数据文件中，有5类与拓扑关系表达有关

拓扑关系的数据生成耗时费力

仅表达了部分空间关系

拓扑数据的动态维护任重道远

空间拓扑关系的计算与查询赵仁亮,2002,基于Voronoi图的空间关系计算研究，中南大学博士论文部分空间拓扑关系可通过查询获得对于显式地存储了点、线、面目标间的一些拓扑关系的情况，其拓扑关系可通过查询操作而获得，实现简单的空间分析，避免对空间目标具体位置的度量和计算

基于V4T的拓扑关系计算的逻辑流程时空拓扑关系及其应用基于INTERAL的13种时态关系[Allen1983]IntervalRelationEquivalentRelationsEndpointst<st+<s-t=s(t-=s-)&(t+=s+)toverlapss(t-<s-)&(l+<s+)tmeetsst+=s-tdurings((t->s-)&(t+=<s+))or((t->=s-)&(t+<s+))基于INTERAL的13种时态关系基于INTERAL的13种时态关系图形表达Allen，1991基于时态区间8种时态拓扑关系[舒红，1997]在4I框架的16种拓扑关系基础上剔除其中的8种得出有效的8种时态拓扑关系，图形描述如下：

两时态目标间的时态拓扑关系

时态关系与时态拓扑关系对照表[舒红，1997]将有效的8种时态拓扑关系与ALLEN提出的13种时态关系的比较

9I框架和4I框架的等价性8种时空拓扑关系CHRISTOPHECLARAMUNTandBINJIANG[2000]，提出8种时空拓扑关系。

空间对象的104种时空关系CHRISTOPHECLARAMUNTandBINJIANG[2000]提出104种时空关系（不考虑时态方向为71种）。宗地间父子关系的查询

子宗地-父宗地关系表

父宗地子宗地变更时间其他变更属性P1P2t1……P1P3t1……P2P5t2……P4P5t2…………………………王康弘，中国科学院地理科学与资源研究所2000年博士学位论文

地块间的时空拓扑关系常征[1997]，父子地块间的时空拓扑关系：1、空间上的交叉性；2、时间上的邻接性。两地块在时态区间上的拓扑关系时空拓扑关系问题讨论时态问题的讨论ALLEN在提出两个时态区间的13种时态关系时没有证明其完整性；将点集拓扑理论用于时态描述的意义值得怀疑，9I框架与4I框架等价只能描述8种所谓时态拓扑关系，不能完全的、唯一的描述ALLEN的13种时态关系。空间方向关系的描述曹菡,2002，空间关系推理的知识表示与推理机制研究,武汉大学博士学位论文

方向关系描述方向关系表示了两个空间实体间的一种空间顺序，如东、南、西、北、东南等方向关系的定性表示模型:基于锥形的方向关系表示模型基于投影的方向关系表示模型将空间目标的表示限制为一个抽象点，忽略了目标的大小和形状对方向关系表示的影响而最小外接矩形表示法使用目标的最小外接矩形代表目标本身，对目标间方向关系的表示欠准确，也容易产生错误的查询结果方向关系