《1 前言》
1 前言
地理信息系统(GIS)源于19世纪60年代,经过近40年的发展已经取得了长足进步。目前,GIS正以迅猛、不可逆转的势头同新兴技术如遥感(RS)、人工智能(AI)等融合,朝着地理信息科学甚至空间信息科学迈进,逐步成为多种信息集成分析的基础平台。
GIS 处理分析的数据大致可以分为 3 类:一是空间位置信息,二是空间目标之间的关系,三是属性信息。其中,空间目标之间的关系是空间分析的基础。而空间分析又是GIS的主要特征,也是评价一个GIS功能的主要指标之一。
空间关系(即空间目标之间的关系)比较复杂,其原因主要有两个方面[1,2] 。首先,从语义层次上看,对空间关系语义的理解尚不统一,即空间目标之间究竟有多少种关系?怎样分类?采用何种形式化系统才能完备地描述它们?其次,从数据结构层次上看,如何在数据结构中表达,并且在而后的应用中便捷提取也是空间关系处理中的“瓶颈”。尽管如此,我们仍不得不面对它,因为它直接决定了GIS分析功能的强弱。
假设从语义层次上限定我们所研究的空间关系是指GIS中最重要的拓扑关系,那么它在数据结构层次上的表达形式存在3种思路:一是全部显示表达,二是半显示表达,三是隐含表达。全部显示表达通常被认为是不可行的,这是由于空间关系语义理解的不统一,即使统一了,空间目标之间的关系数据也是“海量”的。因此,半显示表达和隐含表达是GIS仅有的两种选择。目前大多数GIS软件采用的是半显示表达,从目前和发展的角度来看,这不是最佳策略。
《2 隐含表达空间关系的面条模型》
2 隐含表达空间关系的面条模型
半显示表达是将部分空间关系以显示的形式在GIS的概念模型、逻辑模型和物理存储结构(即数据结构)中表达[3] 。这类系统有ARC/INFO和MGE 等,其中显示表达了空间目标的构成关系。利用这种关系可以便捷地获取空间目标之间的包含、联结和关联关系。这种基于拓扑结构的半显示表达曾经一度成为判断一种图形软件是否为GIS软件的重要指标。
然而,随着GIS理论研究和应用实践的深入,这种基于拓扑结构的半显示表达体系的结构问题也暴露得比较明显,主要体现在以下几个方面:首先,由于数据结构复杂导致数据检索查询效率低下;其次,需要时常进行拓扑一致性检验,这是由于当空间位置变化时,其拓扑结构不能随之自动更新;再次,这种体系是整体操作而非局部操作,即一旦局部发生了位置变化,整个拓扑结构就需要重新构建;最后,通过拓扑结构能够便捷获取的空间关系有限,仅仅是包含、联结和关联 3 种。因此,从发展的趋势看,基于拓扑结构的 GIS 不是处理空间关系的最佳选择。相反,不存储空间关系,而仅存储空间目标的位置和属性,通过位置和属性动态生成空间关系的思路,因其数据结构简洁、查询检索高效和不存在拓扑不一致性等优点,逐渐被人们看好。
国际上所谓的面条模型正符合隐含表达空间关系的思想。其本质是每一个独立的、有物理意义的空间物体都可以作为一个面条目标,面条目标是现实世界中空间物体的计算机表示。面条目标与面条目标之间不存在任何依赖和构造关系,彼此是相互独立的。用传统的基于拓扑结构的观点看,面条目标可能是点型的、线型的、面型的或者三者的复合,它唯一对应一组空间位置集和多种属性。显然,基于拓扑结构的 GIS 中的 4 个问题在面条模型中不复存在。从某种意义上讲,面条模型克服了基于拓扑结构的GIS中的问题,但要明确这是牺牲了部分拓扑分析功能换取的。如果不能通过面条目标的空间位置动态获取面条目标之间的空间关系,面条模型就会退化为机助成图系统或地理数据库。因此,动态推断面条模型之间的关系是面条模型中十分重要的内容。图1给出了面条模型体系结构,其中虚线部分是需要动态生成的结果。
《图1》
图1 面条模型的体系结构
Fig.1 The architecture of spattio model
下面笔者提出一种动态计算面条模型中面条目标之间关系的有效策略,即基于 Voronoi 图的四邻近数学模型(4-adj模型)。
《3 4-adj模型》
3 4-adj模型
Voronoi图是平面的一种剖分,每一个面条目标都对应唯一一个属于自己的区域(即 Voronoi 区域),在该区域内部的点到该面条目标的距离比到其他面条目标的距离都要短。进而,由所有面条目标的 Voronoi 区域就构成了一个空间剖分,通常称为面条目标的Voronoi图。而面条目标的Voronoi图具有下列优点:a. Voronoi图可以动态建立,也可以局部更新;b. 面条目标的 Voronoi 图可以显示表达面条目标之间的邻近关系;c. 基于Voronoi图推断空间关系是在二维空间解决二维空间的问题,从理论上讲其结论是准确、可信的。
《3.1 基于面条目标Voronoi图判断空间关系的基础》
3.1 基于面条目标Voronoi图判断空间关系的基础
面条目标分为点、线和面(带空洞和不带空洞的面)。当它们分离时,可以利用空间实体的Voronoi 多边形的邻接性判断空间邻近;但是当它们不分离时,就要对Voronoi多边形进行处理。点和线的Voronoi 多边形不变,见图2。
《图2》
图2 点实体和线的Voronoi图
Fig.2 The Voronoi diagram of point entities and lines
而对于面,如果Voronoi多边形保持不变,根据上面的分析显然可以知道,以面条目标的 Voronoi 多边形为基础,要么Voronoi多边形邻接,即两个空间实体邻近,要么两个Voronoi多边形不邻接,即两者所对应的面条目标不邻近,如图2所示。因此,要想以 Voronoi 多边形为基础推求更多的空间关系,显然要修正原Voronoi多边形。
《3.2 面条目标Voronoi图的修正》
3.2 面条目标Voronoi图的修正
点与线及其之间的关系比较简单也易于计算,其 Voronoi 多边形保持不变,而面较复杂。在基于 Voronoi图的数据结构中,由于仅仅考虑面条目标的边界,所以首先对其进行一次缩小相似变换,生成 “内边界”,如图3所示。
《图3》
图3 X的外边界和内边界示意图
Fig.3 The schematic for the external boundary and inner boundary of X
根据外边界和内边界可以定义内Voronoi多边形和外Voronoi多边形,如图4所示。对于点和线的 Voronoi图,其内Voronoi多边形为空。
《图4》
图4 面Voronoi多边形分离图
Fig.4 The split graph of the surface Voronoi polygon
《3.3 空间关系推求的4-adj模型》
3.3 空间关系推求的4-adj模型
一个面条目标和另一个面条目标之间的关系(不分离时)可以通过两个实体的内Voronoi多边形和外Voronoi多边形相互之间的邻接性来判断。
设 A、B 是两个面条目标,EAV 、EBV表示 A、B 的外 Voronoi 图,IAV、IBV 表示 A、B 的内 Voronoi 图, “.adj.”表示Voronoi多边形邻接,A、B之间的空间关系可以由这三者形成的四元组形式化框架表达。
令 x= EAV .adj. EBV ,y= EAV .adj. IBV ,z= IAV .adj. EBV ,w= IAV .adj. IBV 。当“.adj.”为TRUE时,简记为 T;当“.adj.”为FALSE时,简记为F。当x,y,z,w 取不同值时,总共会产生16种情况,见表1。
《表1》
表1 基于4-adj模型的x,y,z,w 取值情况
Table 1 The values of x,y,z and w based on 4-adj model
根据表1,可以得到如下的准则。
If x=False,y=False,z=False,w=False,then A and B are disjoint
If x=False,y=False,z=True,w=False,then A include B
If x=False,y=False,z=True,w=True,then A covers B
If x=False,y=True,z=False,w=False,then B include A
If x=False,y=False,z=True,w=False,then A include B
If x=False,y=True,z=False,w=True,then A cover by B
If x=True,y=False,z=False,w=False,then A and B are neighborhood
If x=True,y=True,z=True,w=True,then A over laps B
上述8种情形见图5。
《图5》
图5 面/面情形
Fig.5 The situation of surface/surface
对于线和面(见图 6),线的 Voronoi 图为 VL,面的内Voronoi图为IAV ,外Voronoi图为EAV 。
If VL .adj. IAV =True,VL .adj. EAV =True,then the relation is cross
If VL .adj. IAV =False,VL .adj. EAV =True,then the relation is Nei
If VL.adj. IAV =True,VL .adj. EAV =False,then the relation is In
If VL .adj. IAV =False,VL .adj. EAV =False,then the relation is disjoint
《图6》
图6 面/线情形
Fig.6 The situation of surface/line
对于点和面(见图 7),点的 Voronoi 图为 Vp,面的内Voronoi图为IAV ,外Voronoi图为EAV 。
If Vp .adj. IAV =True,VL .adj. EAV =False,then the relation is In
If VL .adj. IAV =False,VL .adj. EAV =True,then the relation is Nei
If VL .adj. IAV =False,VL .adj. EAV =False,then the relation is disjoint
《图7》
图7 点/面情形
Fig.7 The situation of point/surface
《4 结语》
4 结语
本文从 GIS 作为传统地图的延续和发展的角度,阐述了它应当具备处理几何信息、空间信息和属性信息的能力,而三者之中空间关系的处理又是极其复杂和重要的。GIS处理空间关系有全显示表达、半显示表达和隐含表达3种形式。目前,GIS主要采用半隐含表达,但存在结构复杂、查询效率低下、非局部操作和需要进行拓扑一致性检验等问题。因此,隐含表达是GIS发展的趋势和潮流。然而,由于隐含表达中不存放空间关系,而后面的空间分析、推理、查询和检索又需要利用空间关系,故动态生成空间关系就变得十分重要。
本文首先从理论上提出了4-adj模型,旨在利用它在面条模型中动态生成面条目标之间的空间关系,给面条模型中空间关系的动态生成提供了一条新思路。其次,给出了几类空间关系推断的具体规则,并通过面/面情形、面/线情形和点/面情形实验证实了规则的可行和有效。