空间关系
周 晓 光
Zxg@mail.csu.edu.cn
测绘与国土信息工程系
内 容
? 空间拓扑关系的描述
– 四元交模型（ 4I模型 ）
– 九元交模型（ 9I模型 ）
– 基于 Voronoi图的九元交模型（ V9I模型 ）
? 空间拓扑关系 的 表达
? 空间拓扑关系 的 计算与查询
? 时空拓扑关系 及 其应用
? 空间方向关系 的 描述
空间关系的概念
? 空间关系是数字环境下空间认知, 空间分析, 空
间推理的前提和基础 。 空间关系包括
– 由空间物体的几何特性 （ 如空间物体的地理位置与形
状 ） 引起的空间关系, 如：距离, 方位, 邻近, 包含,
连通性, 相似性等；
– 由空间对象的几何和非几何属性共同引起的空间关系，
如空间分布现象中的统计相关、空间自相关、空间相
互作用、空间依赖等。
– 时间上的先后关系；
– 成因上的因果关系等。
空间拓扑关系描述
陈军,2002,Voronoi动态空间数据
模型
空间拓扑关系描述
? 交互模型：是运用空间目标的整体, 而不是将目
标分解为更细的组成部分, 去区分和定义空间关
系, 最具代表性的是 Randell等人提出的空间逻
辑 （ spatial logic） 。
– 缺点：需要预先假设目标间的可能的关系, 不可能保
证完备性, 但对每一种可能的关系, 描述结果是唯一
的 。
? 交叉模型,
– 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的边界和内部。
?
?
?
?
?
?
??
??
ooo
o
BABA
BABA
?
???
4元组区分的简单面域间的 8种空间拓扑关系
A B
A B
A B
B A
A B
A B
A B
B A
?????? ?? ??
?????? ?? ???
?????? ??? ???
?????? ??? ???
?????? ???? ??
?????? ??? ????
?????? ???? ???
?????? ???? ????
序号
图例 语义解释 4元组值
1
A,B相离 （ 不相交 ）
2
A,B相接
3
A,B相等
4
A包含于 B,且两者边
界不交
5 A包含 B,且两者边界不交
6 A包含于 B,且两者边界相交
7 A包含 B,且两者边界相交
8 A,B部分重叠
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
四元组模型对线目标的内部、边界的定义
外部 A-1
内部 A?
边界 ?A
简单线状目标应满足以下条件,
(a) 有且仅有两个端点, ?A={pa,pb},且 pa≠p b
(b) 边界 ?A与内部 A?不相交, 即 ?A∩A ?=?。
(c) 内部 A?与 A?不相交, 即 A?∩A ?=?。
非简单线性目标举例
16种简单线状目标间的拓扑空间关系 1
序
号
图例
语义解释
4元组值
其它 4元组值等
价图例
1 A与 B相离 （ 不相交 ）
2
A的两边界点分别与 B的两
边界点相接
3 A的一个边界点与 B的内部相接
4 B的一个边界点与 A的内部相接
5 A的内部与 B的内部相交
6
A的一个边界点与 B的一个
边界点相接, 且 A的另一
个边界点与 B的内部相接
7
B的一个边界点与 A的一个
边界点相接, 且 B的另一
个边界点与 A的内部相接
A B
A B
A
B
A
B
A B
B A
A
B
A
B
A
B
A B
A B
?????? ?? ??
?????? ?? ???
?????? ?? ???
?????? ??? ??
?????? ??? ??
?????? ?? ????
?????? ??? ???
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
16种简单线状目标间的拓扑空间关系 2
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
A
B
A
B
A
B
A
B
B
A
A
B
A
A
B
A B
B
A
B
A
B
A
B
A
B
A
B
A
B
A
B
A
B
?????? ??? ???
?????? ??? ???
?????? ??? ???
?????? ???? ??
?????? ??? ????
?????? ??? ????
?????? ???? ???
?????? ???? ???
?????? ???? ????
8
A的一个边界点与 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元组框架,
?
?
?
?
?
?
?
?
?
?
???
???
???
?
????
?
?
BABABA
BABABA
BABABA
BAR
o
oooo
o
I
?
?
????
),(9
9元组描述框架的特点
? 与 4元组相比,
– 9元组增加了 ?A∩B -,A?∩B -,A-∩ ?B,A-∩B ?
和 A-∩B - 5个与, 补, 有关的交集
– 9元组所区分的面 \面拓扑关系的数目与 4元组
一样
– 在描述两组线 \线目标、线、面目标时，其描
述能力比 4元组要强, 9元组区分出 33种不同
的线 \线关系
9元组比 4元组能区分更多线 \线关系
A
B A B A
B A B A
B
??
?
??
?
??
??? ?
?
?
??
?
???
??? R4I(A,B)
R9I(A,B)
?
?
?
?
?
?
?
?
?
?
?
?
??????
?????
?????
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?????
?????
????
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
?????
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
????
补在区分线 \线关系中的特点
? 当两个简单线状目标具有相离、相接、穿
越（ cross） 和部分重叠关系时，与, 补,
有关的 5个交集均为非空
? 当一个线状目标落入另一个线状目标的内
部（如 equal,cover） 时，与, 补, 有关
的某些元素会为非空值,
– 与, 补, 有关的交集发挥作用
补在区分线 \线关系中的作用
A B
A A B
A
B A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ?? ??
? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
? ? ??
?
?
?
?
?
?
?
?
?
?
d i s j o i n t
? ?? ??
?? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
o v e r l a pm e e t ( 2 )
B
? ? ??
? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
c r o s s e q u a l
c o v e r
? ?? ??
?? ?? ??
? ??
?
?
?
?
?
?
?
?
?
??
A B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
m e e t ( 1 )
9员组模型区分了 33种线 \线目标之间的空间拓扑关系
在 4元组下不能区分、在 9元组下可以区分的线与线关系示例
A
B
A
B
A
B
A
B
A
B
A
B
?????? ?? ???
??
??
?
?
??
?
?
?
????? ????
????
??
?
?
?
??
?
?
?
??????
????
?????
?????? ?? ???
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
????
?????
?????? ??? ??
??
?
?
?
??
?
?
?
?????
?????
????
??
?
?
?
??
?
?
?
?????? ?????
????
编
号
图示
4 元组取
值
9元组取值
简单语意解释
1
A的两个边界点与 B的两个
边界点重合
A的一个边界点在 B的一个
边界点上
2
A的两个边界点在 B的内部
A的一个边界点在 B的内部
3
B的两个边界点在 A的内部
B的一个边界点在 A的内部
?????? ?? ???
??
?
?
?
??
?
?
?
??????
?????
????
?
?
?
?
?
?
?
?
?
?
?
?
?????
????
????
补在区分面状目标间空间关系的作用
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
?? ?? ??
?? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
? ? ??
?
?
?
?
?
?
?
?
?
?
A B B A
?? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
?
A
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
B
d i s j o i n t m e e t o v e r l a p e q u a l c o v e r - b y c o v e r
BA
? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
BA
? ?? ?
? ? ? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
c o n t a i n s i n s i d e
当两个面状目标之间的拓扑关系由相离（ disjoint）,相接（ meet）
逐步地转化为部分重叠（ partially overlap） 时，与, 补, 有关的 5
个交集均为非空
补在区分线 \面关系中的作用
A
B
A
B
A
B
A
B
A
B
A
B
A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
? ??
? ?? ??
?? ?? ??
?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
d i s j o i n t m e e t ( 1 ) m e e t ( 2 ) c o v e r ( 3 )o v e r l a p c o v e r ( 2 )c o v e r ( 1 )
9员组模型区分了 19种线 \面目标之间的空间拓扑关系
9元组模型存在的若干问题 1
? 两个目标的, 补, 高度重叠
B
C
D
A
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
R
AB R AC R
AD
A
- B -
无法区分不同的空间相离关系
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
C
B
A
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A的, 补, 是 C及其自身的线性函数
? 当 C为常量时,A的外部（定义为补）与其自身线
性相关,这就解释了为什么在一些情况下 9元组与
4元组效果相同（ Chen et al.,2000）。
( )
( )
( ) ( ) ( ) ( ) ??
?
?
?
?
?
?
?
?
?
?
????????????????
???????
??????????
?
BBCAACBAACBAAC
BBCABABA
BBCABABA
)B,A(R
00000
00000
00
9
线目标的内部与其外部相接
? 一维空间中线目标 的 边界将其内部与外部隔离开 ；
? 根据点集拓扑的定义，一个空间目标的边界将其
内部与外部隔离开来,这意味着二维空间中的线
目标只有边界, 内部应为空, 且其边界为线目标
本身，而不是其两个边界点 。
边界 （ 端点 ） 内部 （ 线 ）
外部 （ 晕渲部分 ）
线目标的内部与其外部相接
简单空间目标的限制
? 9元组框架将所研究的空间目标限定为,
– 简单点（无大小、无形状）,
– 简单线（不能够自交，有且有两个不重合的
边界点）,
– 简单面（区域边界必须连通）
9元组不能区分含空洞目标间的空间关系
AB
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
AB A
?? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
?
A
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
AB
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
A
B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
空间目标的, 补, 难以计算
? 难以计算与, 补, 有关的 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图 。
? ?nj IjijppdippdpipV ????,),,(),()(
? ?)(),.,,,3(),2(),1( npVpVpVpVV ?
离散生长点的 Voronoi图
若用形象的比喻来说，可看作是这组生长点以等同速
度向四周扩张，直到相遇为止，扩张过程全部结束
点状生长目标的 Voronoi图及其基本元素
p
i
p
k
p
j
v (p
i
)
V o r o n o i 边
V o r o n o i 结点
相邻生长点
同心圆
B ( p
i
,p
j
)
由 B( p
i
,p
j
) 所围的半平面
Voronoi 图的若干重要性质
? 势力范围特性（ influence region）
? 侧向邻近特性（ lateral adjacency）
? 线性特性 （ linear behaviour）
? 局域动态特性（ local dynamization）
? 与 Delaunay 三角网对偶 (Dual of
Delaunay triangulation)
势力范围特性
? 对一个空间生长目标而言，凡落在其
Voronoi多边形范围内的空间点均距其最
近。因此，该 Voronoi多边形在一定程度
上反映了其影响范围，或称势力范围
Voronoi势力范围 的定义
? 点目标：指点的 Voronoi区域自身；
? 线目标：指线的 Voronoi区域自身；
? 不含空洞的实心面目标：指面的 Voronoi
区域自身；
? 含有空洞的面目标（环状目标）：指环的
Voronoi区域自身及环的空洞区域的并集。
点、线、面的 Voronoi势力范围
侧向邻近特性
房屋
Voronoi边
道路
线性特性
? Voronoi 图是具有 n个多边形和至少三个
节点的平面图 (planar graph)
nv≤ 2n-5
这表明 Voronoi 图的 size 随空间生长目
标个数 n成线性比例增加, 具有并不复杂的
结构 。 这种线性特性是 Voronoi 图得以广
泛应用的主要原因之一 。
最大空圆
? 对 Voronoi 图中的每一
个节点（ vertex）
qi?Q{q1,…,qnv}来说,
至少有三条 Voronoi边通
过。换言之，若过 qi作
一圆 Ci,则 Ci将通过三个
或更多的生长点。而 Ci
是过 qi的最大空圆（ the
largest empty circle）
局域动态特性
? 每一个 Voronoi 多边形的平均边数不超过
6。这表明删除或增加一个空间生长目标，
一般只影响 6个左右的相邻空间生长目标。
换言之，对 Voronoi图的修改只影响局部
范围。
与 Delaunay 三角网对偶
? Delaunay三角形
的 边 数 和
Voronoi 图 的 边
数是相同的 。 若
将 Delaunay边的
端 点 称 为
Delaunay结点,
其实际上就是对
应的 Voronoi 图
的生长点 。
基于 Voronoi 图的 9元组 （ V9I）
? Av,Bv分别 为 A,B的 Voronoi区域
?
?
?
?
?
?
?
???
???
???
VVVV
V
V
BA
o
BABA
B
o
A
o
B
o
AB
o
A
BA
o
BABA
?
?
????
B)( A,R
V 9 I
V9I区分相离关系
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
A B
A
B
C
V9I区分其余几种区域空间关系
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
?? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
A B ABA B
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
a b c
B A A B
A B A
B
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
???
???
??
?
?
?
??
?
?
?
????
????
????
??
?
?
?
??
?
?
?
??????
?????
????
??
?
?
?
??
?
?
?
??????
?????
????
??
?
?
?
??
?
?
?
?????
?????
???
??
?
?
?
??
?
?
?
?????
?????
????
d e f g
基于 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距离图
A
C
D
E
F
G
B
vd(A,A)=0
vd（ A,B） =1
vd（ A,C） =1
vd（ A,D） =2
vd（ 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
空间拓扑关系描述存在的问题
? 包含空洞等复杂对象的空间拓扑关系的描
述问题；
? 对线状目标间空间拓扑关系的描述方法；
? 对体状目标间空间拓扑关系的描述方法；
B
A
B
A
B
A
一个连续边界区域与一非连续边界区域之间的三种拓扑关系
Three topologically distinct relations between two-dimensional objects with holes
体状目标间空间拓扑关系的描述
(郭薇,陈军,1997）
现有方法 无法区分地块间的三种相邻关系
B A
a
b
四 元组模型无法区分地块间的三种相邻关系
B A
a
b
B A
a
b
（ 1） （ 2） （ 3）
?B B0
A0 ? ?
相邻 （ meet ）
?A ?? ?
空间拓扑关系的表达
陈军,2002,Voronoi动态空间数据模型
龚健雅, 2001,地理信息系统基础
传统 GIS中拓扑关系的显式表达
空 间 对 象
G I S
－ 数 据 输 入 － 数 据 存 储
－ 数 据 编 辑 － 数 据 输 出
－ 数 据 检 索 － 空 间 分 析
图 形 数 据 库
－ 矢 量 数 据
－ 珊 格 数 据
拓 扑 关 系 集
－连通
－相交
－包含
属 性 数 据 库
－ 纯 属 性 数 据
－ 关 联 数 据
－ 管 理 数 据
图
形
数
据
提
取
属
性
数
据
提
取
拓扑
关系
建立
拓扑
关系
维护
拓扑关系的表达
? 拓扑关系的表达方法,
– 全显式
– 部分显式
– 隐式表达
? 全全显式表达一般包括,
– 结点 —弧段关系表
– 弧段 —面域关系表
– 面域 —弧段关系表
– 弧段 —结点关系表
– 弧段 —结点 --面域关系表
面域 —弧段关系表
弧段 —结点关系表
结点 —弧段关系表
弧段 —面块关系表
弧段 —结点 --面块关系表
ARC/INFO图层下的点、弧段和多边形数据组织
空间数据文件
LAB
点文件
ARC
弧段文件
PAL
多边形文件
PAX
PAL的索引
属性数据文件
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 的属性数据及与空间数据的联接 1
Geostar 的属性数据及与空间数据的联接 2
拓扑数据组织与维护的问题
? 开销大
? 拓扑关系的数据组织较为复杂
– GIS拓扑数据模型的数据结构非常复杂,
– 与拓扑关系相关的数据在总数据量中占有较大比重
? 在 Arc/Info的 13种数据文件中，有 5 类与拓扑关系表达有关
? 拓扑关系的数据生成耗时费力
? 仅表达了部分空间关系
? 拓扑数据的动态维护任重道远
空间拓扑关系的计算与查询
赵仁亮,2002,基于 Voronoi图的 空间
关系计算研究，中南大学博士论文
部分空间拓扑关系可通过查询获得
? 对于显式地存储了点、线、面目标间的一
些拓扑关系的情况，其拓扑关系可通过查
询操作而获得，实现简单的空间分析，避
免对空间目标具体位置的度量和计算
基于 V4T的拓扑关系计算的逻辑流程
时空拓扑关系及其应用
基于 INTERAL的 13种时态关系
? [Allen 1983]
Interval Relation Equivalent Relations
Endpoints
t<s t+ < s-
t=s (t- = s- ) & (t+ = s+)
t overlaps s (t- < s-)&(l+ < s+)
t meets s t+ = s-
t during s ((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框架的等价性
9 4
0
0
0 0 0 0
0
0
0 0 0
1 1
I I
I J I J I J
I J I J I J
I J I J I J
I J I J
I J I J
Co e n s i o n IR I D i m IR D i m I
框架 框架
? ? ? ?
?
?
? ? ?
?
? ? ?
? ? ?
? ? ?
? ?
? ?
?
?
? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ? ?d i m (,) ( ) ( )
8种时空拓扑关系
? CHRISTOPHE CLARAMUNT and BIN JIANG [2000],提出 8种时空拓扑关系。
空间对象的 104 种时空关系
? CHRISTOPHE CLARAMUNT and BIN JIANG [2000]提出 104 种时
空关系（不考虑时态方向为 71种）。
宗地间父子关系的查询
子宗地 -父宗地关系表
父宗地
子宗地
变更时
间
其他变
更属性
P1 P2 t1 ……
P1
P3
t1
……
P2
P5
t2
……
P4
P5
t2
……
……
……
……
……
王康弘，中国科学院地理科学与资源研究所 2000年博士学位论文
地块间的时空拓扑关系
? 常征 [1997]，父子地块间的时空拓扑关系,
1、空间上的交叉性；
2、时间上的邻接性。
两地块在时态区间上的拓扑关系
时空拓扑关系问题讨论
? 时态问题的讨论
? ALLEN 在提出两个时态区间的 13种时态关
系时没有证明其完整性；
? 将点集拓扑理论用于时态描述的意义值得
怀疑,9I框架与 4I框架等价只能描述 8种所
谓时态拓扑关系，不能完全的、唯一的描
述 ALLEN的 13种时态关系。
空间方向关系的描述
曹 菡,2002,空间关系推理的知识表示与推理机制研究,
武 汉 大 学博 士 学 位 论 文
方向关系描述
? 方向关系表示了两个空间实体间的一种空间顺序，
如东、南、西、北、东南等
? 方向关系的定性表示模型,
– 基于锥形的方向关系表示模型
– 基于投影的方向关系表示模型
– 将空间目标的表示限制为一个抽象点，忽略了目标的
大小和形状对方向关系表示的影响
– 而最小外接矩形表示法使用目标的最小外接矩形代表
目标本身，对目标间方向关系的表示欠准确，也容易
产生错误的查询结果
方向关系的主方向关系
? 两方向关系,E（ 东）,W（ 西）,S（ 南）,N
（ 北）；
? 四方向关系,E,S,W,N ；
? 八方向关系 E,S,W,N, SE（ 东南）,NE
（ 东北）,SW（ 西南）,NW（ 西北）；
? 十六方向关系,E,S,W,N, SE（ 东南）、
NE（ 东北）,SW（ 西南）,NW（ 西北）、
SSE（ 东南南）,NNE（ 东北北）,ENE（ 东北
东）,ESE（ 东南东）,SSW（ 西南南）、
WSW（ 西南西）,WNW（ 西北西）,NNW
（ 西北北）等
主方向关系
N
W E
S
O
S
O W E
N
NE N NW
W E
SW S SE
O O W E
SW S SE
N NW NE
O
S
N
O W E
以面目标为参照目标的基于投影的 8方向关系描述模型
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
B
基于格网阵列表达具有实际意义的 218种方向关系
Allen的基于区间的方向关系（ 169）
以点目标为参照目标的 8方向关系表示模型
NE N NW
W E
SW S SE O
O W E
SW S SE
N NW NE NE N NW
W E
SW S SE O
O W E
SW S SE
N NW NE NW
W E
SW S SE O
N NE
O W E
SW S SE
N NW NE
以线目标为参照目标的 8方向关系表示模型
O W E
SW S SE
N NW NE
V2 V1 O
W E
SW S SE
N NW NE
V2 V1 O
W E
SW S SE
N NW NE
V3
V4
O W
SW SE
N NW NE
V3
V4
E
S
O W E
SW SE
N NW NE
V3
V4
S
O W
SW S SE
N NW NE
V2 V1
E
O W E
SW S SE
N NW NE
O W E
SW S SE
N NW NE
O W E
SW S SE
N NW NE
O
NE N NW
W E
SW S SE
NE N NW
W E
SW S SE
O
NE N NW
W E
SW S SE
O
周 晓 光
Zxg@mail.csu.edu.cn
测绘与国土信息工程系
内 容
? 空间拓扑关系的描述
– 四元交模型（ 4I模型 ）
– 九元交模型（ 9I模型 ）
– 基于 Voronoi图的九元交模型（ V9I模型 ）
? 空间拓扑关系 的 表达
? 空间拓扑关系 的 计算与查询
? 时空拓扑关系 及 其应用
? 空间方向关系 的 描述
空间关系的概念
? 空间关系是数字环境下空间认知, 空间分析, 空
间推理的前提和基础 。 空间关系包括
– 由空间物体的几何特性 （ 如空间物体的地理位置与形
状 ） 引起的空间关系, 如：距离, 方位, 邻近, 包含,
连通性, 相似性等；
– 由空间对象的几何和非几何属性共同引起的空间关系，
如空间分布现象中的统计相关、空间自相关、空间相
互作用、空间依赖等。
– 时间上的先后关系；
– 成因上的因果关系等。
空间拓扑关系描述
陈军,2002,Voronoi动态空间数据
模型
空间拓扑关系描述
? 交互模型：是运用空间目标的整体, 而不是将目
标分解为更细的组成部分, 去区分和定义空间关
系, 最具代表性的是 Randell等人提出的空间逻
辑 （ spatial logic） 。
– 缺点：需要预先假设目标间的可能的关系, 不可能保
证完备性, 但对每一种可能的关系, 描述结果是唯一
的 。
? 交叉模型,
– 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的边界和内部。
?
?
?
?
?
?
??
??
ooo
o
BABA
BABA
?
???
4元组区分的简单面域间的 8种空间拓扑关系
A B
A B
A B
B A
A B
A B
A B
B A
?????? ?? ??
?????? ?? ???
?????? ??? ???
?????? ??? ???
?????? ???? ??
?????? ??? ????
?????? ???? ???
?????? ???? ????
序号
图例 语义解释 4元组值
1
A,B相离 （ 不相交 ）
2
A,B相接
3
A,B相等
4
A包含于 B,且两者边
界不交
5 A包含 B,且两者边界不交
6 A包含于 B,且两者边界相交
7 A包含 B,且两者边界相交
8 A,B部分重叠
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
四元组模型对线目标的内部、边界的定义
外部 A-1
内部 A?
边界 ?A
简单线状目标应满足以下条件,
(a) 有且仅有两个端点, ?A={pa,pb},且 pa≠p b
(b) 边界 ?A与内部 A?不相交, 即 ?A∩A ?=?。
(c) 内部 A?与 A?不相交, 即 A?∩A ?=?。
非简单线性目标举例
16种简单线状目标间的拓扑空间关系 1
序
号
图例
语义解释
4元组值
其它 4元组值等
价图例
1 A与 B相离 （ 不相交 ）
2
A的两边界点分别与 B的两
边界点相接
3 A的一个边界点与 B的内部相接
4 B的一个边界点与 A的内部相接
5 A的内部与 B的内部相交
6
A的一个边界点与 B的一个
边界点相接, 且 A的另一
个边界点与 B的内部相接
7
B的一个边界点与 A的一个
边界点相接, 且 B的另一
个边界点与 A的内部相接
A B
A B
A
B
A
B
A B
B A
A
B
A
B
A
B
A B
A B
?????? ?? ??
?????? ?? ???
?????? ?? ???
?????? ??? ??
?????? ??? ??
?????? ?? ????
?????? ??? ???
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
16种简单线状目标间的拓扑空间关系 2
??
?
??
?
??
??
ooo
o
BABA
BABA
?
???
A
B
A
B
A
B
A
B
B
A
A
B
A
A
B
A B
B
A
B
A
B
A
B
A
B
A
B
A
B
A
B
A
B
?????? ??? ???
?????? ??? ???
?????? ??? ???
?????? ???? ??
?????? ??? ????
?????? ??? ????
?????? ???? ???
?????? ???? ???
?????? ???? ????
8
A的一个边界点与 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元组框架,
?
?
?
?
?
?
?
?
?
?
???
???
???
?
????
?
?
BABABA
BABABA
BABABA
BAR
o
oooo
o
I
?
?
????
),(9
9元组描述框架的特点
? 与 4元组相比,
– 9元组增加了 ?A∩B -,A?∩B -,A-∩ ?B,A-∩B ?
和 A-∩B - 5个与, 补, 有关的交集
– 9元组所区分的面 \面拓扑关系的数目与 4元组
一样
– 在描述两组线 \线目标、线、面目标时，其描
述能力比 4元组要强, 9元组区分出 33种不同
的线 \线关系
9元组比 4元组能区分更多线 \线关系
A
B A B A
B A B A
B
??
?
??
?
??
??? ?
?
?
??
?
???
??? R4I(A,B)
R9I(A,B)
?
?
?
?
?
?
?
?
?
?
?
?
??????
?????
?????
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?????
?????
????
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
?????
?
?
?
?
?
?
?
?
?
?
?
?
??????
????
????
补在区分线 \线关系中的特点
? 当两个简单线状目标具有相离、相接、穿
越（ cross） 和部分重叠关系时，与, 补,
有关的 5个交集均为非空
? 当一个线状目标落入另一个线状目标的内
部（如 equal,cover） 时，与, 补, 有关
的某些元素会为非空值,
– 与, 补, 有关的交集发挥作用
补在区分线 \线关系中的作用
A B
A A B
A
B A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ?? ??
? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
? ? ??
?
?
?
?
?
?
?
?
?
?
d i s j o i n t
? ?? ??
?? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
o v e r l a pm e e t ( 2 )
B
? ? ??
? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
c r o s s e q u a l
c o v e r
? ?? ??
?? ?? ??
? ??
?
?
?
?
?
?
?
?
?
??
A B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
m e e t ( 1 )
9员组模型区分了 33种线 \线目标之间的空间拓扑关系
在 4元组下不能区分、在 9元组下可以区分的线与线关系示例
A
B
A
B
A
B
A
B
A
B
A
B
?????? ?? ???
??
??
?
?
??
?
?
?
????? ????
????
??
?
?
?
??
?
?
?
??????
????
?????
?????? ?? ???
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
????
?????
?????? ??? ??
??
?
?
?
??
?
?
?
?????
?????
????
??
?
?
?
??
?
?
?
?????? ?????
????
编
号
图示
4 元组取
值
9元组取值
简单语意解释
1
A的两个边界点与 B的两个
边界点重合
A的一个边界点在 B的一个
边界点上
2
A的两个边界点在 B的内部
A的一个边界点在 B的内部
3
B的两个边界点在 A的内部
B的一个边界点在 A的内部
?????? ?? ???
??
?
?
?
??
?
?
?
??????
?????
????
?
?
?
?
?
?
?
?
?
?
?
?
?????
????
????
补在区分面状目标间空间关系的作用
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
?? ?? ??
?? ?? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
? ? ??
?
?
?
?
?
?
?
?
?
?
A B B A
?? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
?
A
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
B
d i s j o i n t m e e t o v e r l a p e q u a l c o v e r - b y c o v e r
BA
? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
BA
? ?? ?
? ? ? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
c o n t a i n s i n s i d e
当两个面状目标之间的拓扑关系由相离（ disjoint）,相接（ meet）
逐步地转化为部分重叠（ partially overlap） 时，与, 补, 有关的 5
个交集均为非空
补在区分线 \面关系中的作用
A
B
A
B
A
B
A
B
A
B
A
B
A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
? ??
? ?? ??
?? ?? ??
?? ??
?
?
?
?
?
?
?
?
?
?
?? ? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
d i s j o i n t m e e t ( 1 ) m e e t ( 2 ) c o v e r ( 3 )o v e r l a p c o v e r ( 2 )c o v e r ( 1 )
9员组模型区分了 19种线 \面目标之间的空间拓扑关系
9元组模型存在的若干问题 1
? 两个目标的, 补, 高度重叠
B
C
D
A
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
R
AB R AC R
AD
A
- B -
无法区分不同的空间相离关系
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
C
B
A
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A的, 补, 是 C及其自身的线性函数
? 当 C为常量时,A的外部（定义为补）与其自身线
性相关,这就解释了为什么在一些情况下 9元组与
4元组效果相同（ Chen et al.,2000）。
( )
( )
( ) ( ) ( ) ( ) ??
?
?
?
?
?
?
?
?
?
?
????????????????
???????
??????????
?
BBCAACBAACBAAC
BBCABABA
BBCABABA
)B,A(R
00000
00000
00
9
线目标的内部与其外部相接
? 一维空间中线目标 的 边界将其内部与外部隔离开 ；
? 根据点集拓扑的定义，一个空间目标的边界将其
内部与外部隔离开来,这意味着二维空间中的线
目标只有边界, 内部应为空, 且其边界为线目标
本身，而不是其两个边界点 。
边界 （ 端点 ） 内部 （ 线 ）
外部 （ 晕渲部分 ）
线目标的内部与其外部相接
简单空间目标的限制
? 9元组框架将所研究的空间目标限定为,
– 简单点（无大小、无形状）,
– 简单线（不能够自交，有且有两个不重合的
边界点）,
– 简单面（区域边界必须连通）
9元组不能区分含空洞目标间的空间关系
AB
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
AB A
?? ? ??
?? ?? ??
? ? ??
?
?
?
?
?
?
?
?
?
?
A
?? ?? ?
? ?? ?
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
AB
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
?? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
A
B
A
B
?? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
空间目标的, 补, 难以计算
? 难以计算与, 补, 有关的 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图 。
? ?nj IjijppdippdpipV ????,),,(),()(
? ?)(),.,,,3(),2(),1( npVpVpVpVV ?
离散生长点的 Voronoi图
若用形象的比喻来说，可看作是这组生长点以等同速
度向四周扩张，直到相遇为止，扩张过程全部结束
点状生长目标的 Voronoi图及其基本元素
p
i
p
k
p
j
v (p
i
)
V o r o n o i 边
V o r o n o i 结点
相邻生长点
同心圆
B ( p
i
,p
j
)
由 B( p
i
,p
j
) 所围的半平面
Voronoi 图的若干重要性质
? 势力范围特性（ influence region）
? 侧向邻近特性（ lateral adjacency）
? 线性特性 （ linear behaviour）
? 局域动态特性（ local dynamization）
? 与 Delaunay 三角网对偶 (Dual of
Delaunay triangulation)
势力范围特性
? 对一个空间生长目标而言，凡落在其
Voronoi多边形范围内的空间点均距其最
近。因此，该 Voronoi多边形在一定程度
上反映了其影响范围，或称势力范围
Voronoi势力范围 的定义
? 点目标：指点的 Voronoi区域自身；
? 线目标：指线的 Voronoi区域自身；
? 不含空洞的实心面目标：指面的 Voronoi
区域自身；
? 含有空洞的面目标（环状目标）：指环的
Voronoi区域自身及环的空洞区域的并集。
点、线、面的 Voronoi势力范围
侧向邻近特性
房屋
Voronoi边
道路
线性特性
? Voronoi 图是具有 n个多边形和至少三个
节点的平面图 (planar graph)
nv≤ 2n-5
这表明 Voronoi 图的 size 随空间生长目
标个数 n成线性比例增加, 具有并不复杂的
结构 。 这种线性特性是 Voronoi 图得以广
泛应用的主要原因之一 。
最大空圆
? 对 Voronoi 图中的每一
个节点（ vertex）
qi?Q{q1,…,qnv}来说,
至少有三条 Voronoi边通
过。换言之，若过 qi作
一圆 Ci,则 Ci将通过三个
或更多的生长点。而 Ci
是过 qi的最大空圆（ the
largest empty circle）
局域动态特性
? 每一个 Voronoi 多边形的平均边数不超过
6。这表明删除或增加一个空间生长目标，
一般只影响 6个左右的相邻空间生长目标。
换言之，对 Voronoi图的修改只影响局部
范围。
与 Delaunay 三角网对偶
? Delaunay三角形
的 边 数 和
Voronoi 图 的 边
数是相同的 。 若
将 Delaunay边的
端 点 称 为
Delaunay结点,
其实际上就是对
应的 Voronoi 图
的生长点 。
基于 Voronoi 图的 9元组 （ V9I）
? Av,Bv分别 为 A,B的 Voronoi区域
?
?
?
?
?
?
?
???
???
???
VVVV
V
V
BA
o
BABA
B
o
A
o
B
o
AB
o
A
BA
o
BABA
?
?
????
B)( A,R
V 9 I
V9I区分相离关系
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ??
?? ?? ??
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
A B
A
B
C
V9I区分其余几种区域空间关系
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
?? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ??
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
A B ABA B
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?
?
?
?
?
?
?
?
a b c
B A A B
A B A
B
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
????
????
??
?
?
?
??
?
?
?
??????
???
???
??
?
?
?
??
?
?
?
????
????
????
??
?
?
?
??
?
?
?
??????
?????
????
??
?
?
?
??
?
?
?
??????
?????
????
??
?
?
?
??
?
?
?
?????
?????
???
??
?
?
?
??
?
?
?
?????
?????
????
d e f g
基于 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距离图
A
C
D
E
F
G
B
vd(A,A)=0
vd（ A,B） =1
vd（ A,C） =1
vd（ A,D） =2
vd（ 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
空间拓扑关系描述存在的问题
? 包含空洞等复杂对象的空间拓扑关系的描
述问题；
? 对线状目标间空间拓扑关系的描述方法；
? 对体状目标间空间拓扑关系的描述方法；
B
A
B
A
B
A
一个连续边界区域与一非连续边界区域之间的三种拓扑关系
Three topologically distinct relations between two-dimensional objects with holes
体状目标间空间拓扑关系的描述
(郭薇,陈军,1997）
现有方法 无法区分地块间的三种相邻关系
B A
a
b
四 元组模型无法区分地块间的三种相邻关系
B A
a
b
B A
a
b
（ 1） （ 2） （ 3）
?B B0
A0 ? ?
相邻 （ meet ）
?A ?? ?
空间拓扑关系的表达
陈军,2002,Voronoi动态空间数据模型
龚健雅, 2001,地理信息系统基础
传统 GIS中拓扑关系的显式表达
空 间 对 象
G I S
－ 数 据 输 入 － 数 据 存 储
－ 数 据 编 辑 － 数 据 输 出
－ 数 据 检 索 － 空 间 分 析
图 形 数 据 库
－ 矢 量 数 据
－ 珊 格 数 据
拓 扑 关 系 集
－连通
－相交
－包含
属 性 数 据 库
－ 纯 属 性 数 据
－ 关 联 数 据
－ 管 理 数 据
图
形
数
据
提
取
属
性
数
据
提
取
拓扑
关系
建立
拓扑
关系
维护
拓扑关系的表达
? 拓扑关系的表达方法,
– 全显式
– 部分显式
– 隐式表达
? 全全显式表达一般包括,
– 结点 —弧段关系表
– 弧段 —面域关系表
– 面域 —弧段关系表
– 弧段 —结点关系表
– 弧段 —结点 --面域关系表
面域 —弧段关系表
弧段 —结点关系表
结点 —弧段关系表
弧段 —面块关系表
弧段 —结点 --面块关系表
ARC/INFO图层下的点、弧段和多边形数据组织
空间数据文件
LAB
点文件
ARC
弧段文件
PAL
多边形文件
PAX
PAL的索引
属性数据文件
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 的属性数据及与空间数据的联接 1
Geostar 的属性数据及与空间数据的联接 2
拓扑数据组织与维护的问题
? 开销大
? 拓扑关系的数据组织较为复杂
– GIS拓扑数据模型的数据结构非常复杂,
– 与拓扑关系相关的数据在总数据量中占有较大比重
? 在 Arc/Info的 13种数据文件中，有 5 类与拓扑关系表达有关
? 拓扑关系的数据生成耗时费力
? 仅表达了部分空间关系
? 拓扑数据的动态维护任重道远
空间拓扑关系的计算与查询
赵仁亮,2002,基于 Voronoi图的 空间
关系计算研究，中南大学博士论文
部分空间拓扑关系可通过查询获得
? 对于显式地存储了点、线、面目标间的一
些拓扑关系的情况，其拓扑关系可通过查
询操作而获得，实现简单的空间分析，避
免对空间目标具体位置的度量和计算
基于 V4T的拓扑关系计算的逻辑流程
时空拓扑关系及其应用
基于 INTERAL的 13种时态关系
? [Allen 1983]
Interval Relation Equivalent Relations
Endpoints
t<s t+ < s-
t=s (t- = s- ) & (t+ = s+)
t overlaps s (t- < s-)&(l+ < s+)
t meets s t+ = s-
t during s ((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框架的等价性
9 4
0
0
0 0 0 0
0
0
0 0 0
1 1
I I
I J I J I J
I J I J I J
I J I J I J
I J I J
I J I J
Co e n s i o n IR I D i m IR D i m I
框架 框架
? ? ? ?
?
?
? ? ?
?
? ? ?
? ? ?
? ? ?
? ?
? ?
?
?
? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
? ? ?d i m (,) ( ) ( )
8种时空拓扑关系
? CHRISTOPHE CLARAMUNT and BIN JIANG [2000],提出 8种时空拓扑关系。
空间对象的 104 种时空关系
? CHRISTOPHE CLARAMUNT and BIN JIANG [2000]提出 104 种时
空关系（不考虑时态方向为 71种）。
宗地间父子关系的查询
子宗地 -父宗地关系表
父宗地
子宗地
变更时
间
其他变
更属性
P1 P2 t1 ……
P1
P3
t1
……
P2
P5
t2
……
P4
P5
t2
……
……
……
……
……
王康弘，中国科学院地理科学与资源研究所 2000年博士学位论文
地块间的时空拓扑关系
? 常征 [1997]，父子地块间的时空拓扑关系,
1、空间上的交叉性；
2、时间上的邻接性。
两地块在时态区间上的拓扑关系
时空拓扑关系问题讨论
? 时态问题的讨论
? ALLEN 在提出两个时态区间的 13种时态关
系时没有证明其完整性；
? 将点集拓扑理论用于时态描述的意义值得
怀疑,9I框架与 4I框架等价只能描述 8种所
谓时态拓扑关系，不能完全的、唯一的描
述 ALLEN的 13种时态关系。
空间方向关系的描述
曹 菡,2002,空间关系推理的知识表示与推理机制研究,
武 汉 大 学博 士 学 位 论 文
方向关系描述
? 方向关系表示了两个空间实体间的一种空间顺序，
如东、南、西、北、东南等
? 方向关系的定性表示模型,
– 基于锥形的方向关系表示模型
– 基于投影的方向关系表示模型
– 将空间目标的表示限制为一个抽象点，忽略了目标的
大小和形状对方向关系表示的影响
– 而最小外接矩形表示法使用目标的最小外接矩形代表
目标本身，对目标间方向关系的表示欠准确，也容易
产生错误的查询结果
方向关系的主方向关系
? 两方向关系,E（ 东）,W（ 西）,S（ 南）,N
（ 北）；
? 四方向关系,E,S,W,N ；
? 八方向关系 E,S,W,N, SE（ 东南）,NE
（ 东北）,SW（ 西南）,NW（ 西北）；
? 十六方向关系,E,S,W,N, SE（ 东南）、
NE（ 东北）,SW（ 西南）,NW（ 西北）、
SSE（ 东南南）,NNE（ 东北北）,ENE（ 东北
东）,ESE（ 东南东）,SSW（ 西南南）、
WSW（ 西南西）,WNW（ 西北西）,NNW
（ 西北北）等
主方向关系
N
W E
S
O
S
O W E
N
NE N NW
W E
SW S SE
O O W E
SW S SE
N NW NE
O
S
N
O W E
以面目标为参照目标的基于投影的 8方向关系描述模型
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
NA
WA
NWA
SWA SEA
EA
NEA
SA
OA
B
基于格网阵列表达具有实际意义的 218种方向关系
Allen的基于区间的方向关系（ 169）
以点目标为参照目标的 8方向关系表示模型
NE N NW
W E
SW S SE O
O W E
SW S SE
N NW NE NE N NW
W E
SW S SE O
O W E
SW S SE
N NW NE NW
W E
SW S SE O
N NE
O W E
SW S SE
N NW NE
以线目标为参照目标的 8方向关系表示模型
O W E
SW S SE
N NW NE
V2 V1 O
W E
SW S SE
N NW NE
V2 V1 O
W E
SW S SE
N NW NE
V3
V4
O W
SW SE
N NW NE
V3
V4
E
S
O W E
SW SE
N NW NE
V3
V4
S
O W
SW S SE
N NW NE
V2 V1
E
O W E
SW S SE
N NW NE
O W E
SW S SE
N NW NE
O W E
SW S SE
N NW NE
O
NE N NW
W E
SW S SE
NE N NW
W E
SW S SE
O
NE N NW
W E
SW S SE
O
