空间方向关系推理计算的NP完全性研究

空间方向关系推理问题的NP完全性证明是基于两个重要的变换基础之上的,其中一个变换是把空间方向关系推理问题变换为一个限定满足问题,基于这种变换,空间方向关系推理问题中的变量和值域相应地变换为限定满足问题中的空间目标和方向关系限制;另一个变换是从不全等3可满足问题到方向关系限定满足问题,基于这种变换,3可满足问题实例中的变量可以变换为两个方向关系限制.为此,一个满足所有目标方向关系限制的空间结构可以建立,从而可以证明空间方向关系推理问题的NP完全性性质.

采用定性坐标的位置表达及主方向关系推理

针对现有的位置关系表达模型均面向点对象,提出了定性直角坐标的概念,基于此概念提出了一种平面区域对象位置关系表达模型,该模型通过记录主对象与参考对象的定性位置区域的交集是否为空,由此构造位置矩阵来表达区域对象间的位置关系,从而较好地反映了对象的形状及对象间的空间布局,可有效地表达区域对象间的位置关系,并通过定性坐标将方向和距离关系有机地结合在一起形成统一的表达和推理模型.为了提高主方向关系推理的精度,基于该模型又提出了一个主方向关系推理算法,并对其正确性进行了验证.理论分析和实例验证的结果表明,该算法降低了推理的不确定性,提高了推理的精度.

3D-GIS中方向关系描述及其推理

方向关系是描述一个物体与另一个物体的相对位置关系。现有文献主要研究二维空间方向关系的描述和定性推理,二维空间中方向关系的描述和推理相对比较完善。本文采用投影方法给出三维空间方向关系描述模型,研究了单方向关系的推理,在此基础之上给出了单方向与多方向关系的定性推理,以及多方向关系与多方向关系间的定性推理。最后研究单方向关系定性推理的一些规律。

3D-GIS中方向关系定性推理研究

方向关系描述GIS中对象之间的空间关系。3D-GIS中单方向关系间定性推理共有27×27=729结果,方向关系定性推理的规律性研究是研究单方向关系定性推理的提升。本文采用单纯形数据模型,用基于投影的27方向关系描述模型,详细研究3D-GIS中方向关系间定性推理的规律,最后得出一些重要结论。

基于坐标映射模型的方向关系一致性检验

为处理复杂三维空间物体间的方向关系,基于单纯形数据模型,利用投影方法及区间运算简单的特性,提出三维空间物体方向关系的坐标映射模型。在此基础上,讨论三维空间方向关系的基本推理运算、凸关系判断方法及路径一致性检验算法,给出方向关系网络一致性检验算法及其正确性证明。