空间方向关系模型比较
空间方向关系模型分析
颜芬1* 李精忠1
（1 武汉大学资源与环境科学学院，武汉市珞瑜路129号，430079）
摘要：空间方向关系是空间关系的重要内容，是地理信息系统的基础理论之一。在地图制图、计算机辅助
设计、图像和多媒体数据库以及地理信息系统等领域中有着广泛的应用。本文着重于详细介绍目前主要的
空间方向关系形式化描述模型的原理、优缺点、适用性，分析目前存在的问题以及为未来空间方向关系模
型的研究探讨可行方向。
关键词：方向关系；空间关系；形式化描述模型；地理信息系统；空间分析
1 介绍
空间数据库是一门前沿的交叉学科，也是近年来的热点研究领域[1]。空间数据库中，空间数据的空间关系的表示和处理在地图制图、计算机辅助设计、图像和多媒体数据库以及地理信息系统等领域中有着广泛的应用。空间方向关系作为地理信息系统中最为重要的空间关系之一[2]，在空间数据建模、空间查询、空间分析、空间推理、制图综合和地图解译等研究工作中起着重要作用，空间方向关系模型是计算和表达目标间方向关系的重要工具，是空间方向关系理论研究的重点和难点[3]。
空间方向关系模型考虑的基本问题是如何有效地建立描述空间方向关系的形式化模型[4]。描述空间方向关系的模型主要有锥形模型、基于投影的模型、基于V oronoi图的模型，
统计模型和基于点群分割的模型等。锥形模型主要包括四方向、八方向和三角化等；基于投影的模型主要有MBR(Minimum Boundary Rectangle)模型和方向关系矩阵模型等；基于V oronoi图的模型主要包括基于MBR V oronoi图模型和方向Voronoi图模型等。
描述空间方向关系的方法可分为定性描述和定量描述。目前定性描述的空间方向关系模型主要有锥形模型、MBR模型和基于MBR V oronoi图模型等；定量描述的空间方向关系模型主要有方向关系矩阵模型、方向V oronoi图模型、统计模型和基于点群分割的模型等。用于定性计算的模型是基于对图形的概括进行计算分析，因而存在一定的粗糙性，并且受目标之间距离、自身形状以及人的主观因素影响较大；用于定量计算的模型比用于定性计算的模型对空间目标的空间方向关系描述得更加准确，且受目标之间距离和自身形状等因素小，但往往计算要复杂得多。
本文着重于详细介绍目前主要的空间方向关系形式化描述模型的原理、优点、缺点、适用性，了解空间方向关系模型研究的历程，以及为今后空间方向关系模型的研究探讨可行方向。
第一作者及通讯作者：颜芬，硕士生。Email:896211086@https://www.wendangku.net/doc/fa13542228.html,
2 空间方向关系模型
2.1 锥形模型
锥形模型由Haar[5]提出，其主要思想是将空间目标及其周围的区域分成带有方向性的几个区域，通过各目标本身及方向区域之间的交的结果来描述空间方向关系，具有代表性的是四方向、八方向和三角化模型。锥形模型的优点是原理简单，易于编程实现。其缺点在于对空间目标间距离和自身形状的特定组合会给出不准确的描述[6]。
2.1.1 四方向
四方向锥形模型是以某一空间目标为参考目标，以东西南北方向线为轴将空间目标及周围的区域等分成四个方向区域来定义方向关系，如图1所示，以参考点O为中心，将空间区域分为E、S、W、N四个方向区域，用其他空间目标与这些方向区域间的位置关系来描述空间目标间的方向关系。
如图1所示，四方向锥形模型的局限性在于对于狭长的面状物体A，以其质心为参考点O，源目标B相对于参考目标A的方向关系为：Dir(A，B)=N，而这与现实中人的认知是不相符的，人一般会认为B在A的东方。
图1 四方向锥形模型
Fig. 1 Cone-based Model of four directions
2.1.1 八方向
八方向锥形模型是以某一空间目标为参考目标，以东西南北方向线以及四方向锥形模型边界线为轴将空间目标及周围的区域分成八个方向区域定义方向关系。以参考点O为中心，将空间区域分为E、SE、S、SW、W、NW、N、NE八个方向区域，用其他空间目标与这些方向区域间的位置关系来描述空间目标间的方向关系。
与四方向锥形模型相比，八方向锥形模型能更精确描述空间目标间的方向关系。但八方向锥形模型有与四方向锥形模型相同的局限性，对于狭长的面状物体A，以其质心为参考点O，源目标B相对于参考目标A的方向关系为：Dir(A，B)=NE，而这与现实中人的认知是不相符的，人一般会认为B在A的东方[7]。
图2 八方向锥形模型
Fig. 2 Cone-based Model of eight directions
2.1.3 三角化
三角化模型是四方向锥形模型和八方向锥形模型的扩展。基本思想是从空间目标的某点出发，沿所需要的方向作两条射线形成一个三角形方向区域，从而描述与计算目标间的方向关系。
三角化锥形模型一定程度上顾及了空间目标的形状和大小对空间方向关系的影响，克服了四方向锥形模型和八方向锥形模型的不足，提高了空间目标距离较近的情况下对空间方向关系的区分能力。但对于某些特定形状的面状物体A，如图3所示，根据人的认知原理，源目标B处于参考目标A的东北方，这是三角化模型不能识别出来的。
图3 三角化锥形模型
Fig. 3 Triangulated cone-based Model
2.2 基于投影的模型
基于投影的模型与锥形模型最大的不同之处在于对区域的划分，锥形模型选择参考点来划分区域，而基于投影的模型是指将空间目标投影到特定的坐标轴上，通过各目标投影间的关系去描述与定义方向关系，通过空间目标在水平轴和垂直轴上的投影，可以将空间分为E、S、W、N、O、NE、SE、SW、NW 9个方向区域。现在运用范围比较广且具有代表性的是MBR模型和方向关系矩阵模型。基于投影的模型较好地顾及了参考目标的形状和大小对方向关系的影响，在一定程度上克服了锥形模型存在的缺陷，但对空间目标的空间方向关系的推断仍然受目标间距离的影响。
2.2.1 MBR模型
MBR模型由D.Papadias等提出[8]，主要思想是通过空间目标最小外接矩形之间的方向关系来判定空间目标间的方向关系。该模型在水平方向和垂直方向上各能表达13种空间方向关系，因此能够区分169种空间方向关系。该模型常用来作为空间目标拓扑关系判定的过滤器。当用于方向关系描述的时候，通常用来表达9个主要方向：E、S、W、N、O、NE、SE、SW、NW。
MBR模型在一定程度上减小了空间目标的形状和大小对判断方向关系的影响，但当空间目标的最小外接矩形有重叠部分时，MBR模型不再适用。如图4所示，参考目标A和源目标B的最小外接矩形部分重叠，难以判断A和B的方向关系。
图4 MBR模型
Fig. 4 MBR Model
2.2.2 方向关系矩阵模型
方向关系矩阵模型可以判断具有重叠最小外接矩形区域的目标之间的空间方向关系。该模型由Goyal等提出[9]，主要思想是以空间目标最小外接矩形为参考方向，将空间划分为9个方向区域，以源目标与各方向区域的交叠情况为元素构成一个方向关系矩阵来描述与定义空间目标间的方向关系。在方向关系矩阵模型中，只建立参考目标的最小外接矩形，而源目标还是它的实际形状。
方向关系矩阵可以分为两种，一种是粗略的方向关系矩阵，仅仅记录源目标与参考目标的各方向区域是否相交，如图5所示，源目标B相对于参考目标A的方向关系为：Dir(A，B)={N，NE，E}，另一种是详细的方向关系矩阵，记录源目标落在每个方向区域的面积比率，如图所示，源目标B相对于参考目标A的方向关系为：B的25%在A的北方（N），50%在A的东北方（NE），25%在A的东方（N）。方向关系矩阵的局限性在于描述空间目标的空间方向关系的模糊性过大，且计算较复杂。
图5 方向关系矩阵模型
Fig. 5 Direction relation matrix model
2.3 基于Voronoi 图的模型
基于Voronoi 图的模型的基本思想通过空间目标的V oronoi 图与空间目标的关系来描述和定义空间目标间的方向关系。与锥形模型、基于投影的模型和MBR 模型相比，基于Voronoi 图的模型在方向关系描述准确性方面占有优势，适合于对各种情况下空间目标间方向关系的精确描述。但基于V oronoi 图的模型受可视域限制, 对遮挡部分的图形变化不敏感，角度不能随着可视域外部分的图形变化而发生变化，且基于V oronoi 图的模型的计算相对比较复杂。
2.3.1 基于MBR Voronoi 图模型
李成名等[10]在空间目标MBR 的基础上建立Voronoi 区域，通过空间目标MBR 与V oronoi 区域边界线之间的关系来描述空间目标之间的方向关系。
如图6所示，一个空间实体A 的最小矩形有4条边分别表示为de= eastedge(A )、dw=westedge(A )、dn=northedge(A )和ds = southedge(A )。若将4条边看作4个线(Line)生成元，生成的4个Voronoi 区分别为voronoi(de)、voronoi(dw)、voronoi(dn)和voronoi(ds)。NE 、NW 、SW 和SE 分别为边de 、dn 、dw 和ds 的V oronoi 多边形的边界，空间实体A 的东部E(A )定义为de 、SE 和NE 围成的区域，空间实体A 西部W(A )定义为dw 、SW 、NW 围成的区域，空间实体A 的北部N(A )定义为dn 、NE 、NW 围成的区域，空间实体A 的南部S(A )定义为ds 、SE 、SW 围成的区域。
图5 方向关系矩阵模型
Fig. 5 Direction relation matrix model
空间实体A 和B 之间的方向关系可以利用空间实体的最小矩形边和V oronoi 多边形的边界线构成的5×5矩阵形式化描述表达，矩形的形式如式(1)，在式(1)中，NE A 表示空间实体A 的北-东线，NE B 表示空间实体B 的北-东线，B A 表示空间实体A 的最小矩形的边，其余类似。基于此，基于MBR V oronoi 图模型可以表达目标间的八种主要方向：E 、S 、W 、N 、NE 、SE 、SW 、NW 。
B A B A B A B A B A B A B A B A B A B
A B A B A B A B A B
A B A B A B A B A B
A B A B A B A B A B
A B B SW B SE B NW B NE B B SW SW SW SE SW NW SW NE SW B SE SW SE SE SE NW SE NE SE B NW SW NW SE NW NW NW NE NW B NE SW NE SE NE NW NE NE NE （1）
该模型对目标间的方向关系的描述较为精确，局限性在于不能处理两目标缠绕交叠等复
杂情况。
2.3.2 方向Voronoi图模型
方向Voronoi图模型通过计算用于表示目标间指向线法线的V oronoi图得到目标间精确的方向关系[11]。该模型考虑了两目标之间方向关系的各个侧面，用多个方向的集合（即多条指向线）来描述目标间的方向关系。该模型的构建包括以下四个步骤：1）目标图形的综合；2）可视区域的确定；3）空间方向的定量计算；4）定性描述结论的确定。
如图6a所示，粗实线L1L2是参考目标A与源目标B之间的方向V oronoi图，它所描述的空间方向关系是：B的78%位于A的北面，22%位于A的东北面，或者描述为B位于A 的北面。
与其他模型相比，该模型最大的优势在于受两目标的大小和距离等的影响很小，在绝大多数情况下总能得到精确的计算结果。该模型的局限性在于当不可视部分变化时，难以准确描述空间方向关系的变化[12]。如图6a和图6b所示，源目标B对参考目标A的不可视部分发生变化，但根据该模型，B相对于A的方向关系不变。
图6 方向V oronoi图
Fig. 6 Direction V oronoi model
2.4 统计模型
邓敏等[13]学者提出一种基于分解与组合的思想来分析空间目标间的方向关系。首先，将空间目标分解成更细小的基本单元。如果忽略这些细小单元的大小，那么在计算方向时可视为点来处理。然后，计算这些细小单元之间的方向，得到两个目标的所有基本单元间的方向，即一组方向，或者视为一个分布。最后，对这组方向进行统计描述。具体实现是根据一定的内插方法对源目标进行内插，产生多个内插点，连接参考点和内插点，形成多条方向线，再选择中值方向作为方向关系的分布中心趋势。
如图7所示，将源面状目标B进行栅格化，栅格中心作为内插点，连接参考目标A的质心与多个内插点形成多条方向线，最终选择中值方向度量B相对于A的空间方向，如图7中带箭头实线所示。
图7 统计模型
Fig. 7 Statistical model
与锥形模型相比，统计模型的优点是采用了中值方向作为空间方向，中值方向能够较好地从整体上度量空间目标方向关系分布的中心趋势，并且与人的认知是相一致的；与基于投影的模型相比，统计模型是基于空间目标本身建立的，而不是空间目标的MBR，减少了因对空间目标近似处理引起的不精确性；与基于V oronoi图的模型相比，统计模型对整个源目标进行内插，源目标发生变化，其内插点和中值方向也会发生变化，故统计模型能解决基于V oronoi图的模型具有的源目标不可视部分变化而方向不变的问题。
该模型的局限性在于1）难以保证内插的精度。将面状目标栅格化时，不同的栅格大小产生不一样的结果，栅格越小，精度越高；2）计算过于复杂。插值计算的基本复杂度T(n)=O(n2)，当目标图形较复杂时，插值的计算量太大。
2.5 基于点群分割的模型
文学等学者[14]提出一种基于点群分割的空间方向计算模型。该模型的基本原理是把空间目标看做由点组成的点群，在目标之间建立方向关系参考线，并使参考线左右两侧的点数相等，然后利用参考线计算空间目标间的方向角度。
具体实现如图8所示，图8a为点与线方向角度计算，参考目标为点A，源目标为线B，把线目标B离散成点群，方向参考线L与源目标点群交于B mid，把B分为两个子点群，两个子点群中的点数应当相等。参考线L 的方向角度即为B相对于A的方向。图8b为线与线方向角度计算，参考目标为线A，源目标为线B，首先将A和B离散成点群，计算A和B对应全部离散点的重心M，从通过M的直线中寻找能够平分A与B对应全部离散点的直线作为备选参考线，如果备选直线多于一条，则从中选择将A对应离散点分割最为平均的一条作为最终参考线。当参考目标或者源目标为面时，可以把它的边界看做封闭的线进行点群离散，后续的计算方法则与线计算方法相同。
图8 基于点群分割的模型
Fig. 8 Direction relation model based on point group dividing
基于点群分割的模型与统计模型有着相似的思想，都是将目标分解，形成离散的小目标。基于点群分割的模型的优点与统计模型的优点相似，受目标之间的距离及自身形状影响小；且当计算目标在可视域外部分发生改变时，模型能够对此改变做出反应，输出更加合理的角度结果，表现出良好的适应性。且相比于统计模型，基于点群分割的模型对面状目标的离散化更为合理，计算更简单。
基于点群分割的模型的局限性与统计模型相似，要将目标离散成点群时难以保证精度。一个目标的点群中的点之间的间隔越小，点群中的点的数目越多，其计算结果越精确，但这也意味着计算量越大。为了在结果精确度和计算量之间找到权衡之处，这不得不对目标的离散化处理给予更多的考虑。
2.6 模型适用性分析
基于以上对各个空间方向关系模型的形式化描述、优点和缺点的详细介绍，本文总结了各个空间方向关系模型受空间目标之间的距离及自身形状的影响度、对目标间空间方向关系描述的准确性和模型的计算复杂性，并对各个模型的适用性进行分析，见表1。
空间方向关系形式化描述模型中，锥形模型比较简单适合于表达空间点对象间的方向关系，在表达二维空间对象间的方向关系时，受空间目标形状和大小的影响，有时会出现错误或难以描述，故适合于空间目标形状和大小距离较远的空间目标间方向关系的判定。其中，三角化模型引入了空间目标的MBR，一定程度上顾及了空间目标的形状和大小对空间方向关系的影响，提高了空间目标距离较近的情况下对空间方向关系的区分能力。
基于投影的模型是以目标的MBR代替目标进行空间方向关系的判断。当源目标和参考目标的MBR有重叠区域时，MBR模型不能对空间方向关系作出准确判断，所以只能适用于MBR不相交情况下对空间方向关系进行定性描述。而方向关系矩阵模型是判断参考目标的MBR和源目标的空间方向关系，大大减少了重叠MBR对目标之间的空间方向关系的判断的影响，故适用于一般情况下对空间目标的空间方向关系的精确描述。
基于MBR V oronoi图的模型与MBR模型有着相似的局限性，难以对于两目标缠绕交叠等复杂情况，故适用于于MBR不相交情况下对空间方向关系进行定性描述，但与MBR模型相比，受空间目标之间的距离及自身形状的影响更小，对空间方向关系的描述会更合理。方向V oronoi图模型对目标进行了综合处理，只考虑可视部分的空间方向关系，忽略不可视部分，未考虑空间目标的整体形状和大小，故描述空间目标的方向关系时受目标自身形状影响，总的来说方向V oronoi图模型适用于一般情况下对空间目标的空间方向关系的精确描述。
统计模型和基于点群分割的模型都是基于分解目标的思想，用内插或者离散化的方法将大目标分解为小目标，把线、面目标分解为点目标。统计模型和基于点群分割的模型对空间方向关系的描述几乎不受空间目标之间的距离、自身的形状和大小的影响，且描述的准确性非常高，故适合各种情况下对空间目标的空间方向关系的精确描述。这两种模型的局限性在于计算较复杂，可能会限制模型的推广和应用。
3 总结
目前描述空间方向关系的模型主要有锥形模型、基于投影的模型、基于V oronoi图的模型，统计模型和基于点群分割的模型等。锥形模型比较简单，但对方向关系区分较弱；基于投影的模型和基于V oronoi图的模型对锥形模型有较大的改进，但仍存在对复杂图形之间的空间方向关系描述不准确等问题；统计模型和基于点群分割的模型对空间方向关系的描述几乎不受空间目标之间的距离、自身的形状和大小的影响，且描述的准确性非常高，但计算的复杂度也很高。
目前，空间方向关系形式化描述方法存在的主要问题是：
1）存在模型描述错误或者无法描述的情形；
2）存在计算复杂等应用困难的情形。
故本文认为未来空间方向关系模型的研究主要集中在以下两个方向：
1）结合人类空间认知理论研究。传统的形式化描述对复杂图形之间的空间方向关系的描述与人类认知往往不一样，这就要求用人类空间认知理论来解决这样的问题，比如基于V oronoi图的模型就是一个很好的尝试。
2）模型算法的优化。对于计算复杂度较高的模型进行优化处理，或者针对不同应用领域对空间方向关系描述的精确度要求不同，而对空间方向关系模型进行改进，使之能应用于特定的领域。
参考文献(Reference)
[1].Xia yu, Zhu xinyan, Li deren, et al. Analysis of formal representations of spatial direction relation in GIS[J]. Science of Surveying and Mapping, 2007. 32(5): p. 94-97. (夏宇, 朱欣焰, 李德仁等. GIS空间方向关系形式化描述模型分析[J].测绘科学, 2007. 32(5): p. 94-97.)
[2].Zhang lifeng. Research on direction relationships of grouped point object based on convex hull[J]. Journal of
Gansu Lianhe University (Natural Sciences), 2009(05): p. 39-41.) (张立峰. 基于凸壳的点群目标空间方向关系研究[J].甘肃联合大学学报(自然科学版), 2009(05): p. 39-41.)
[3].He yunbin, Bian jian. Researchs on direction relation models in spatial reasoning[J]. Computer & Digital Engineering, 2010(04): p. 62-65+120. (何云斌, 边健. 空间推理中方向关系模型的研究[J].计算机与数字工程, 2010(04): p. 62-65+120.)
[4].De min, Huang xingyuan, Li junjie, et al. A model for computing spatial direction relations in vector GIS[A]. Chinese Association for Geographic Information Society. The eighth annual meeting of Chinese Association for Geographic Information Society[C]. Chinese Association for Geographic Information Society,2004:9 (邓敏, 黄杏元, 李俊杰等. 矢量GIS空间方向关系的计算模型[A]. 中国地理信息系统协会.中国地理信息系统协会第八届年会论文集[C].中国地理信息系统协会:,2004:9)
[5].Harr, R. Computational Model of Spatial Relations[R]. TR-478, MSC-72-03610, Computer Science, University of Maryland, College Park,M D, 1976.
[6].Qi po. Key technology research of spatial direction relations[D]. Harbin University of Science and Technology, 2014. (齐坡. 空间方向关系的关键技术研究[D]. 哈尔滨理工大学, 2014.)
[7].Wang zhonghui, Yang yanchun. Compound model for describing qualitative direction relations[J]. Journal of image and graphics, 2014(06): p. 979-984. (王中辉, 杨艳春, 描述定性方向关系的复合表达模型. 中国图象图形学报, 2014(06): p. 979-984.)
[8].Paradias D. Relation-based representation of spatial knowledge[D].Department of Electrical and Computer Engineering, National Technical University of Athens, 1994.
[9].Goyal R K. Similarity assement for cardinal direction between extended spatial objects[D].Maine: The University od Maine, 2000.
[10].Li chengming, Zhu yinghao, Chenjun. Directional relationship description and determination based on V oronoi diagram in GIS[J]. Journal of the PLA Institute of Surveying and Mapping. 1998(02): p. 117-120. (李成名, 朱英浩,陈军. 利用V oronoi图形式化描述和判断GIS中的方向关[J]系.解放军测绘学院学报, 1998(02): p. 117-120.)
[11].Yan haowen, Guorenzhong. A formal description model of directional relationships based on V oronoi diagram[J]. Geomatics and Information Science of Wuhan University, 2003(04): p. 468-471+479. (闫浩文, 郭仁忠. 基于V oronoi图的空间方向关系形式化描述模型[J].武汉大学学报(信息科学版), 2003(04): p. 468-471+479.)
[12].Wang zhonghui, Yan haowen. Computation of direction relations between object groups based on direction V oronoi diagram model[J]. Geomatics and Information Science of Wuhan University, 2013(05): p. 584-588. (王中辉, 闫浩文. 基于方向V oronoi图模型的群组目标空间方向关系计算[J].武汉大学学报(信息科学版), 2013(05): p. 584-588.)
[13].De min, Zhang yan, Li jun jie. A statistical model for computing direction relations between spatial objects in GIS[J]. Geomatics World, 2006(05): p. 70-76. (邓敏, 张燕, 李俊杰. GIS空间目标间方向关系的统计表达模型[J].地理信息世界, 2006(05): p. 70-76.)
[14].Wen Xue, et al. A Model of Direction Calculation Based on Point Group Dividing[J].Acta Scientiarum Naturalium Universitatis Pekinensis, 2013(03): p. 485-490. (文学等. 基于点群分割的空间方向计算模型[J].北京大学学报(自然科学版), 2013(03): p. 485-490.)
Analysis of models for describing spatial direction relations
Fen Yan1* JingZhong Li1
(1 School of resources and environmental science, Wuhan University, 129 Luoyu Road, Wuhan, China, 430079 ) Abstract: As a basic theory of GIS, Spatial direction relations is an important part of spatial relations. It is widely applied in lots of domains, such as cartography, CAD(computer-aided design), image, multimedia database, GIS etc. This paper focuses on the introduction and comparison of models for describing spatial direction relations. Main problems, which exist in researches of models for describing spatial direction relations, and advices are summarized to shed light on future research.
Keywords: Directional relations; Spatial relationship; Models of formal representation; GIS; Spatial analysis
First Author and *Corresponding author: Fen Yan, Master. E-mail: 896211086@https://www.wendangku.net/doc/fa13542228.html,