《1 前言》
1 前言
在基于拓扑结构的传统地理信息系统(GIS)中,如ARC/INFO,定义了3类拓扑关系,即拓扑包含、拓扑邻接和拓扑关联。拓扑包含是指线包括端点和节点,面包括构成它的线。拓扑邻接是指有公共点的线,有公共边的面。拓扑关联是指线与面之间、线与线之间的联接关系[1] 。然而,两个空间实体之间的拓扑关系远不止如此,这种理解至少是不全面、不系统的。为此,自 20 世纪 80 年代以来,力求从语义层次上完整、准确地理解拓扑关系一直是 GIS理论界研究的热点内容之一。高度概括这些研究工作可以将其分为两类,一类是Interaction-based 方法,直接用形式化的语言给出严密定义,但是关系与关系之间的交叉、覆盖和是否覆盖整个拓扑关系空间一般不予以讨论。另一类是 Intersectionbased方法,该方法是将空间实体分成几个“部件”,通过比较“部件”之间的交集情况,从而确定空间实体之间的关系。如果“部件”的选择的确是一个相对独立的拓扑不变量,由此形式化表达的空间关系满足空间关系的唯一性和完备性[2,3] 。
《2 拓扑关系的完备、形式化表达》
2 拓扑关系的完备、形式化表达
基于点集拓扑空间关系描述方案隶属于 Intersection-based 方法,它的基本思想是将空间实体看成由点构成的集合,空间实体的关系就可以通过借助点集拓扑理论,通过比较两个点集之间的情况,得出空间实体之间的拓扑关系。1991年,Egenhofer 等[4] 把每一个空间实体剖分为3个“部件”,即内部、边界和外部3个拓扑不变量。然而,由于“补”作为空间实体的外部不合适,使得3个拓扑不变量线性相关,引发了一系列问题,较为典型的有:a. 不能区分Disjoint关系;b. 不能形式化表达空间邻近关系; c. 不能处理复杂的空间目标;d. 可操作性差。鉴于此,提出将与空间实体有关的局部空间分为内部、边界和Voronoi多边形凸包[5,6] 。如果两个空间实体用符号A、B 表示,其“部件”分别表示为:∂A 、A°、AV 和 ∂B 、B°、BV ,基于Voronoi多边形的9-Intersection 模型简记为 NIV,A 和 B 之间的拓扑关系可以形式化表达为
式(1)中,∂A 、∂B 表示A、B 的边界;A°、B° 表示A、B 的内部;AV 、BV 表示A、B 的Voronoi多边形凸包。
假定A、B 为两个面实体,利用NIV模型可以将A、B 之间的拓扑关系形式化表达为唯一、完备的 9 类(其唯一、完备性证明见另文),如果“ ”表示 “and”即“并”关系,“ ”表示等价关系,(A,R,B)代表A、B 具有关系R,为了下文论述方便起见,将规定的规范化记法和符号列入表1。
《表1》
表1 空间关系规范化名称
Table 1 Standard concepts of spatial relationship
采用表1中规范化符号约定,9种拓扑空间关系可以分别形式化表达为如下9种:
1)Relation 1(关系 1):严格分离关系(Sdisjoint),见式(2);
2)Relation 2(关系2):Voronoi邻近关系(Vadjacent),见式(3);
3)Relation 3(关系3):包围关系(Bound),见式(4);
4)Relation 4(关系 4):包围且相接(Intouch),见式(5);
5)Relation 5(关系 5):包含关系(Include),见式(6);
6)Relation 6(关系 6):包含于关系(Cover),见式(7);
7)Relation 7(关系7):相接关系(Touch),见式(8);
8)Relation 8(关系 8):相等关系(Equal),见式(9);
9)Relation 9(关系 9):覆盖关系(Overlap),见式(10)。
《3 拓扑性质》
3 拓扑性质
根据空间关系理论,空间关系主要包含3种基本特性,即对称性、互逆性和传递性,这些基本特性是空间关系符号的理论基础。
《3.1 对称性》
3.1 对称性
如果A、B 的关系与B、A 的关系等价,即(A,X, B)⇔(B,X,A),称A、B 具有等价关系X,关系X 具有对称性,或者说基于NIV的关系矩阵R(A,B)等于关系矩阵 R(B,A)。对于 A 和 B 两个空间实体,由于具有(A,Sdisjoint,B)⇔(B,Sdisjoint,A)、(A,Touch,B)⇔(B,Touch,A)、(A,Overlap,B)⇔ (B,Overlap,A)、(A,Equal,B)⇔(B,Equal,A),故上述关系具有对称性。
《3.2 互逆性》
3.2 互逆性
如果A、B 基于NIV的关系矩阵为R(A,B),B、 A 基于NIV的关系矩阵为R(B,A),两者互为转置,即 R(A,B)T =R(B,A),则 A、B 之间的关系为逆关系。由于具有(A,Bound,B)T =(B,Bound,A)、(A,Intouch,B)T =(B,Intouch,A)、(A,Include,B)T =(B,Include,A)、(A,Cover,B)T =(B,Cover,A),故包围、包围且相接、包含、包含于具有互逆性。
《3.3 传递性》
3.3 传递性
如果有A、B、C 三个空间实体,A、B 具有空间关系X,B、C 具有空间关系X,则A、C 也具有空间关系 X,那么X 具有传递性,关系Bound和关系Include具有传递性。
《3.4 空间关系复合》
3.4 空间关系复合
空间关系复合是指根据空间关系的基本特性,由已知空间关系推求未知空间关系的过程,若用形式化的语言可以表述为:假定A、B 之间关系和B、C 之间关系已知,待求A、C 之间的关系。如果把空间实体用椭圆体表示,空间实体之间的关系用实线表示,待求关系用虚线表示,上述过程可以用图 1 形象、直观地表达。
《图1》
图1 空间关系复合示意图
Fig.1 The example of composite spatial relationships
图1中,如果A、B 之间的关系为X,B、C 之间的关系为Y,待推求的A、C 之间的关系为Z,其中关系 X、Y、Z 为上述9类关系中的一种。从图1可以看出,空间关系复合类似于已知三角形的两条边,解求第三条边。有些情况X、Y 确定后,Z 值唯一确定,也有些情况 X、Y 确定后,Z 有多种可能的取值情况。如果9类关系分别做表的横栏和纵栏,确定的值用符号表示,不确定的值用“—”表示,表1就可以转化为表2。
《表2》
表2 复合空间关系推理结果
Table 2 The results of composite spatial relationships
《4 拓扑空间关系性质在空间推理中的应用》
4 拓扑空间关系性质在空间推理中的应用
从广义上讲,空间推理是指从已知空间信息推求未知空间信息的理论和方法,定性空间推理是空间推理的一种,它是从定性的空间关系出发推导定性空间信息的理论与技术实现手段。一般包括知识的表达、匹配和推理3个过程。知识表达隶属知识工程、人工智能领域,主要的方法有如果—则(IF—THEN)规则表示、框架表示、语义表示、一阶谓词逻辑表示方法等,采用形式化的表达方法将知识表达之后,就可以构成知识库,作为空间推理的基础和前提。推理机制在空间推理中也具有十分重要的意义,有正向推理机制、反向推理机制、正反向结合的推理机制。正向推理机制是从已知的条件出发,得出结论。而反向推理机制是从结论出发,寻找得到该结论的条件是否满足。此外,也可以采用不确定性推理、模糊推理。匹配是指给定的条件与知识库中知识比较的过程。结合上述知识工程中的一般思想与空间推理的具体情况,定性空间推理的框架可以表示为图2。
《图2》
图2 定性空间推理过程
Fig.2 The process of qualitative spatial reasoning
假定“ → ”表示导出,“R - ”表示R的逆关系,A、 B 表示两个空间实体,R(A,B)代表A 与B 具有关系R 。上述拓扑关系的性质可以一阶谓词逻辑表示为:
1)Sdisjoint(A,B)→ Sdisjoint(B,A);
2)Vadjacent(A,B)→ Vadjacent(B,A);
3)Touch(A,B)→ Touch(B,A);
4)Equal(A,B)→ Equal(B,A);
5)Overlap(A,B)→ Overlap(B,A);
6)Bound(A,B)→ Bound-(B,A);
7)Cover(A,B)→ Cover-(B,A);
8)Include(A,B)→ Include-(B,A);
9)Intouch(A,B)→ Intouch-(B,A);
10)Include(A,B)Include(B,C)→Include(A,C);
11)Bound(A,B) Bound(B,C)→Bound(A,C)。
上述拓扑关系的复合性质可以一阶谓词逻辑表示为:
1)Sdisjoint(A,B)Bound(B,C)→ Sdisjoint (A,C);
2)Sdisjoint(A,B)Include(B,C)→ Sdisjoint (A,C);
3)Sdisjoint(A,B)Cover(B,C)→ Sdisjoint (A,C);
4)Sdisjoint(A,B) Intouch(B,C)→ Sdisjoint(A,C);
5)X(A,B)Equal(B,C)→ X(A,B);
6)Equal(A,B)Y(B,C)→ Y(A,B);
7)Vadjacent(A,B)Bound(B,C)→ Vadjacent(A,C);
8)Vadjacent(A,B)Include(B,C)→ Vadjacent(A,C);
9)Vadjacent(A,B)Cover(B,C)→Vadjacent (A,C);
10)Vadjacent(A,B)Intouch(B,C)→Vadjacent(A,C);
11)Bound(A,B)Vadjacent(B,C)→Bound (A,C);
12)Bound(A,B)Bound(B,C)→Bound(A,C);
13)Bound(A,B) Include(B,C)→Bound (A,C);
14)Bound(A,B)Cover(B,C)→Bound(A,C);
15)Bound(A,B) Intouch(B,C)→Bound (A,C);
16)Include(A,B) Bound(B,C)→Include (A,C);
17)Include(A,B)Include(B,C)→Include (A,C);
18)Include(A,B)Intouch(B,C)→Include (A,C);
19)Cover(A,B)Bound(B,C)→Include(A,C);
20)Cover(A,B)Include(B,C)→Include(A,C);
21)Cover(A,B)Intouch(B,C)→Cover(A,C);
22)Intouch(A,B) Bound(B,C)→Bound (A,C);
23)Intouch(A,B) Include(B,C)→Bound (A,C);
24) Intouch(A,B)Cover(B,C)→Bound(A,C);
25)Touch(A,B) Bound(B,C)→Sdisjoint (A,C);
26)Touch(A,B)Include(B,C)→Sdisjoint (A,C);
27)Touch(A,B) Cover(B,C)→Sdisjoint (A,C);
28)Touch(A,B)Intouch(B,C)→Sdisjoint (A,C)。
如果把空间关系、空间关系性质和复合规则看成一个近似的代数系统,由已知空间信息推求未知空间信息的过程可以近似转变为求解代数方程的问题,相对传统的方程组、未知数及其常数项都是空间信息。求解未知数的过程就是利用空间关系性质和复合规则推导新空间信息的过程。这种基于求解代数方程方法的空间推理称作代数推理,一般情况可分为直接解算和间接解算两类。对于在形如
的式子中推求 F3(A,C )=(A,X,C ) 中关系X,称为直接解算。利用拓扑关系的传递性,显然可以得到 X =Include。对于在形如
的式子中待求X 为何种关系(在这种情况下,利用拓扑关系性质和空间关系复合准则,在已知条件驱动下可以反求得到X=Sdisjoint)称为间接推理。无论间接推理还是直接推理,其推理的基础都是拓扑关系的基本性质和空间复合准则。
《5 结语》
5 结语
通过拓扑关系及其性质和在空间推理中应用分析,系统论述了如下几点:a. 拓扑关系在语义层次上利用NIV模型,完备、唯一、形式化表达了空间实体之间的9类拓扑关系;b. 在9类关系的基础上,分析了其中存在的传递性、互逆性、对称性;c. 根据空间关系的基本特性,得出了空间复合的结果;d. 给出了空间复合与拓扑关系基本特性的一阶谓词表达,及其在代数推理和空间推理中的应用方法和策略。