基于MBR的主方向关系一致性检验

定性的空间推理在地理信息系统、人工智能、数据库及多媒体等领域中的应用越来越引起人们的注意.空间推理的基础理论以及相应算法也在不断地创新和发展.方向关系推理是空间推理研究领域的重要分支,利用区间代数及矩形代数理论,以物体的极小边界盒(minimum bounding rectangle,简称MBR)为模型,提出了一种基于MBR的主方向关系与矩形代数关系相结合的推理方法.利用该方法,可以将矩形代数良好的计算性质应用于空间方向关系推理中,实现了矩形代数与基于MBR主方向关系的相互转换方法、主方向关系合成及求反方法、主方向关系中凸(convex)关系判定方法及方向关系一致性检验算法.  

基本主方向关系的反关系推理

在深入研究了基于MBR的主方向关系的反关系推理的基础上,提出了一种基于区域对象本身的基本主方向关系的反关系推理算法。在理论上对该算法的正确性和完备性进行了证明,并通过与实际情形逐一对比验证了该算法的正确性。  

RCC5与主方位关系结合的定性空间推理

解决实际问题需要将多方面空间信息结合进行推理,仅考虑单方面空间信息是不够的.多方面空间信息结合推理已成为定性空间推理的一个研究热点.现有拓扑与方位结合推理工作主要集中在与基于最小外包矩形或单片方位模型的结合.方位信息描述是近似的,不适于精确推理;因此分别采用主方位模型和RCC5描述方位、拓扑信息.根据定义给出基本RCC5和主方位关系间的相互依赖及异质复合表;讨论了其上约束满足问题,得到一个路径相容算法,并分析了推理复性问题.  

On the consistency of cardinal direction constraints

We present a formal model for qualitative spatial reasoning with cardinal directions utilizing a co-ordinate system. Then, we study the problem of checking the consistency of a set of cardinal direction constraints. We introduce the first algorithm for this problem, prove its correctness and analyze its computational complexity. Utilizing the above algorithm, we prove that the consistency checking of a set of basic (i.e., non-disjunctive) cardinal direction constraints can be performed in O(n⁵) time. We also show that the consistency checking of a set of unrestricted (i.e., disjunctive and non-disjunctive) cardinal direction constraints is NP-complete. Finally, we briefly discuss an extension to the basic model and outline an algorithm for the consistency checking problem of this extension.  

Composing cardinal direction relations

We study the recent proposal of Goyal and Egenhofer who presented a model for qualitative spatial reasoning about cardinal directions. Our approach is formal and complements the presentation of Goyal and Egenhofer. We focus our efforts on the composition operator for two cardinal direction relations. We consider two interpretations of the composition operator: consistency-based and existential composition. We point out that the only published method to compute the consistency-based composition does not always work correctly. Then, we consider progressively more expressive classes of cardinal direction relations and give consistency-based composition algorithms for these classes. Our theoretical framework allows us to prove formally that our algorithms are correct. When we consider existential composition, we demonstrate that the binary relation resulting from the composition of two cardinal direction relations cannot be expressed using the relations defined by Goyal and Egenhofer. Finally, we discuss some extensions to the basic model and consider the composition problem for these extensions.  

多空间尺度下顾及不确定性的投影模型研究

空间方向关系理论直接影响着GIS系统的设计、开发和应用,因而受到国际GIS及相关学术界的高度重视,因此进行其模型的研究意义重大。当空间尺度发生变化时,空间数据的不确定性随之变化,从而影响到空间关系的准确描述。考虑了由尺度变化带来的空间数据不确定性变化,在投影模型中添加了扩展不确定度的参数,对多尺度下顾及不确定性的空间方向关系进行形式化描述,来适应多尺度性带来的空间数据不确定性变化,同时还能判定方向间的临界值,可以弥补9元交方向矩阵等模型的缺陷。该模型使得方向关系的划分上有个平滑的过渡区,在方向概念的表达上更符合人的认知。  

A model for describing and composing direction relations between overlapping and contained regions

Current models of direction relations are not designed to describe direction information inside the Minimum Bounding Rectangle (MBR) of a reference region. Thus, the direction relations between overlapping and contained regions cannot be effectively described and derived. To resolve this problem, a new model of direction relations, namely interior-boundary direction relations, is proposed in this study to describe direction concepts relative to the interior or boundary of a region, such as “east part of a region”, “west border of a region”, “a line goes through east part of a region”, and etc. By combining the interior and exterior direction relations, three types of compositions of direction relations are investigated: (1) composing two interior direction relations which can be used to derive the interior or exterior direction relations between two regions with the same parent region; (2) composing an interior direction relation with an exterior direction relation; and (3) composing an interior with an exterior direction relation. The results indicate that the new interior-boundary direction relations and its compositions with exterior direction relations are powerful in describing and deriving direction relations between overlapped and contained regions.  

一种基于真实物体的主方向关系的合成算法

使用基于真实物体的方向关系模型,通过一系列的定义和定理,研究了一种基于真实物体的主方向关系的合成方法。在此基础上,提出了一种新的合成算法,该算法能够更有效地合成真实物体间更为复杂的主方向关系。