郝晓红，李 松，郝忠孝,2

1.哈尔滨理工大学计算机科学与技术学院，哈尔滨150080

2.哈尔滨工业大学计算机科学与技术学院，哈尔滨150001

1 引言

随着信息技术的快速发展，空间数据对象信息的海量性、复杂性、不确定性和多态性对空间方向关系的表示和处理技术提出了越来越高的要求。

近些年，2D空间中的方向关系的研究工作已经较为深入，研究成果主要有锥形模型、投影模型、最小外接矩形模型、四半区域模型和2D字符串关系模型、2D不确定方向关系模型等。在基于MBR（minimum bounding rectangle）模型的2D主方向关系的表示和推理及路径一致性检验[1]、不确定方向关系[2-3]、凹边形地标参照的主方向关系推理[4]、群组目标空间方向关系[5]和复杂定性方向关系表示和推理[6-7]等领域也取得了一些重要的研究成果。

目前，对3D空间方向关系的研究尚处于起步阶段，在一些关键问题方面留有许多空白。文献[8]将二维双十字模型扩展到3D空间以描述3D空间点对象间的方向关系，但该方法忽略了空间对象的形状与大小，与现实中的空间对象具有很大差别，在实际应用中具有局限性。文献[9]将2D主方向关系拓展到3D空间，建立了一种新的3D方向关系模型。基于所建立的模型进一步研究了组合关系、反向关系和一致性检验等重要内容。文献[10]研究了基本主方向关系的反关系。文献[11]扩展了2D空间中开放区域模型的抽象基类，基于对象方位的27个方向关系描述模型提出了3D空间中的开放区域模型。文献[12]基于对象相交立方体矩阵来描述3D空间中的主方向关系。为了表示三维空间中的方位关系，文献[13]基于点集拓扑学对三维方向关系进行了定义，并研究了在3D空间语言中的应用。文献[14]考虑相对方向和粒度，提出了新的三维空间中的方位关系模型。文献[15]对3D空间的主方向关系及推理技术进行了研究。文献[16]提出了一种新的用于三维空间中具有块间主方向关系的定性空间推理的方法。但文献[8-16]所建立的方向关系模型不能有效表示与区分大量复杂的3D方向关系，没有给出动态方向关系的表示与处理方法，无法对3D空间中的反向方向关系进行有效分析和处理。文献[17]将定性距离关系和3DR39方向关系模型相结合，提出了一种新的能处理和分析方向和位置的关系模型。但该模型对三维空间中一些精细方向关系的表示和推理方面的能力显不足，无法处理一些较为复杂的三维方向关系的表示和推理问题。

为了对复杂的3D方向关系进行更为精细化的表示和推理，本文提出了一种新的3D空间方向关系模型，即3DR46方向关系模型，3DR46方向关系模型可表示和区分246种3D方向关系；基于3DR46方向关系模型进一步对动态3D方向关系和模型的双向映射关系进行了系统研究。

2 3DR46方向关系模型

由于3D空间对象的复杂性，3D空间对象的方向关系变得更为复杂多样，方位空间划分和空间对象的不同均能导致大量方向关系在表示和推理方面具有较大的误差，已有的3D方向关系模型仅能表示一部分方向关系，对一些非常重要的方向关系却无法表示和分析。例如，3DR44模型可区分图1中的MO5和MO4相对于QO的方向关系，却无法区分MO6和MO7相对于参照对象QO的方向关系。因此，本章提出3DR46方向关系模型。

3DR46方向关系模型共包含46个方向空间元素，其中8个方向空间元素是封闭空间，该8个方向空间元素可组成一个大的封闭空间，参照对象即处于该封闭空间中；其他38个方向元素是开放空间。3D目标对象可处于任何一个或几个方向空间元素中。3DR46模型中的方向空间元素符号集合为{CNLm,CNRm,CEDm,CEUm,CSRm,CSLm,CWDm,CWUm,Wu,Wd,WNWd,WNNd,WSWd,Nd,Ed,WSSd,ENNd,ESEd,ENEd,ESSd,Cd,Sd,Wm,WNNm,WSWm,WNWm,WSSm,Em,Nm,ENNm,ESEm,ENEm,Sm,WNNu,ESSm,WSWu,WNWu,Nu,Eu,ENNu,WSSu,ESEu,Cu,ENEu,Su,ESSu}。该集合在本文中表示为DR，DR中方向空间元素具有严格的先后顺序。

Fig.1 3DR46 relational model and plane projection graphics of some 3D objects图1 3DR46关系模型及部分3D对象平面投影图

定义1（3DR46模型的方向关系）设2DR表示集合DR的幂集，则3D空间对象MO（目标对象）与QO（参照对象）的方向关系可表示为二元函数3DR46(QO,MO)，3DR46(QO,MO)∈2DR。

本文将每个方向空间元素简称为方向块，每个方向块简记为DRi，1 ≤i≤46。若目标对象MO处于DRi中，则简记为MO□DRi。3DR46方向关系模型及部分空间对象的平面投影如图1所示。

定义2（3DR46模型的方向关系交集序列）基于定义1，3D空间对象MO（目标对象）与QO（参照对象）的方向关系交集序列集合为：

L-QOMO＝{MO∩DRi|DRi∈DR},1 ≤i≤46

交集序列L-QOMO中，若目标对象MO的全部或一部分处于某个方向块中，则MO和该方向块的交集为1，否则为0。利用3DR46方向关系模型和交集序列即可表示和区分已有方向关系模型无法区分的方向关系。

3 3DR46模型的动态方向关系

3D方向关系的动态变化性主要分为两类：目标对象的动态性所导致的方向关系的动态变化；参照对象的动态性所引起的方向关系的动态变化。

3.1 目标对象运动的动态方向关系

通常，3D目标对象针对参照对象的空间方向关系随时间经常会发生动态改变，例如，飞行物和地面指挥塔间的方向关系，营救人员和遇险者间的方向关系等。利用本文提出的3DR46方向关系模型对各时刻的方向关系可表示和描述，计算机依据获得的各交集序列即可动态处理3D方向关系。

在3DR46方向关系模型下分析基于目标对象运动的动态方向关系时，最重要的一个问题是在两个时刻获得动态目标对象相对参照对象的两个不同的方向关系，判定这两个方向关系是否具有连续性。即后一时刻的方向关系是否能由前一时刻的方向关系连续转变得到而不需要经历其他方向关系。该问题还可扩展到多个时刻的多个方向关系的连续判定问题。例如，图1中，MO5由CWUm方向块移动到CWDm方向块，其相对QO的方向关系即是连续的；若MO5由CWUm方向块移动到CNRm方向块，则其相对QO的方向关系变化不具有连续性，必须经过中间方向块。若因为部分原始数据信息的缺失或计算误差，计算机对目标对象下一时刻的方位关系的判断将会发生错误，即遗漏了关键的中间方位关系，将会导致错误决策。对方向关系的连续性进行有效校验可较好提高判定预测的准确性。此类问题广泛存在于现实应用中，例如，在某时刻已获得战机相对于目标基地的方位信息，根据战机的动态信息尚需要计算机系统智能预测下一时刻战机最有可能出现的方位信息，同时还需要对两个时刻的方位信息进行有效校验，判断是否出现纰漏。若因为部分原始数据信息的缺失或计算误差，计算机对战机下一时刻的方位关系的判断发生错误，即遗漏了关键的中间方位关系，将会误导决策。对方向关系的连续性进行有效校验可较好提高判定预测的准确性。

基于3DR46方向关系模型，定义3给出了动态邻接方向块和动态邻接关系的概念。

定义3（动态邻接方向块和动态邻接关系）在3DR46方向关系模型中，设有目标对象MO，两个不同的方向块DRj、DRi，1 ≤i≤46，1 ≤j≤46，i≠j，MO□DRi。若MO可沿某条路径由DRi运动到DRj而不经过DRk，i≠j≠k，即MO∩DRk=∅，则称DRj为DRi的动态邻接方向块，DRj和DRi具有动态邻接关系。一个方向块DRj的所有动态邻接方向块的集合称为DRj的动态邻接方向块集，本文表示为DAJ(DRj)。

针对3DR46方向关系模型，首先可根据定义3确定每个方向块的动态邻接方向块，再依据动态邻接方向块，针对获得的大量交集序列进行连续性的判定。利用这些动态邻接方向块，大量复杂的3D动态方向关系即可进行较好的表示、预测与分析。本节进一步给出了方向块Cu、CNLm、CNRm、CEDm、CEUm、CSRm、CSLm、CWDm、CWUm、Em、Wm、Nm、Sm的动态邻接方向块集，其他方向块的动态邻接方向块集可类似给出。

对于位置频繁发生变化的3D目标对象MO，针对特定的3D参照对象QO，表示和确定MO与各个方向块的位置关系是进行连续性校验的一个关键点。MO在某个时间段（即一些连续的时刻）内的运动可能完全处于一个方向块，也可能跨越不同方向块移动。方向关系的变化情况将是复杂的。

定义4（主位方向块）在3DR46方向关系模型中，设参照对象为QO，目标对象为MO，方向块为DRi，1 ≤i≤46。若MO∩DRi≠∅，则称DRi为MO相对于QO的主位方向块。由MO的所有主位方向块构成的集合称为MO的主位方向块集，记作CM。

定义5（邻位方向块）在3DR46方向关系模型中，设参照对象为QO，目标对象为MO，MO的主位方向块集为CM。和CM中的主位方向块分别具有动态邻接关系的非主位方向块称为基于MO的邻位方向块。由MO的所有邻位方向块构成的集合称为MO的邻位方向块集，记作PM。

定义6（隔位方向块）在3DR46方向关系模型中，设参照对象为QO，目标对象为MO，MO的邻位方向块集为PM。和邻位方向块具有动态邻接关系的非主位方向块称为1级隔位方向块，由MO的所有1级隔位方向块构成的集合称为MO的1级隔位方向块集，记作SM1。和1级隔位方向块邻接的非邻位和非主位方向块称为2级隔位方向块，由MO的所有2级隔位方向块构成的集合称为MO的2级隔位方向块集，记作SM2。同理，可定义3级、4级、5级和6级隔位方向块及隔位方向块集。

分析3DR46方向关系模型可知，MO的隔位方向块至多分为6级。目标对象所处的方向块不同，其隔位方向块所划分的级数将有所不同。

基于以上分析，对于方向关系连续性的检验思路为：分别确定目标对象MO在时刻t和下一时刻t′的主位方向块集、邻位方向块集和各级别的隔位方向块集；检验时刻t的主位方向块集和时刻t′的邻位方向块集的交集情况；检验时刻t′的主位方向块集和时刻t的隔位方向块集的交集情况。若两次检验的交集均为∅，则t到t′的方向关系的变化具有连续性；若不同时为∅，则t到t′的方向关系的变化不具有连续性，即还存在未发现的中间方向关系。

基于以上讨论，进一步给出动态方向关系连续性判定的检验算法如算法1所示。

算法1DC_DIRECTION(L)

算法DC_DIRECTION()对n个方向关系序列进行连续性判定，若找到不符合连续性的方向关系序列则将其返回，更新后继续进行检验，直到检验完最后一个方向关系序列。由定义6可知，隔位方向块最多为6级，故算法中for循环语句的变量j最大值为6。该算法的效率和方向关系交集序列数、各类方向块的计算量、交集判定复杂度及交集序列更新的代价有密切关系。

3.2 参照对象运动的动态方向关系

现实中，3D参照对象QO往往也会发生动态运动，从而目标对象MO相对于动态参照QO的3D方向关系也会相应发生动态变化。参照对象QO的位置变化使得MO相对QO已有的方向关系信息变得无效，大量方向关系信息需要修正和重新确定。

Fig.2 Example of planar projection of dynamic direction relation of 3D reference object motion图2 3D参照对象运动的动态方向关系平面投影示例

如图2所示，在3DR46方向关系模型下，参照对象QO由初始位置沿着曲线l1进行运动（由ts时刻实线所示的QO运动变化到te时刻虚线所示的QO′），目标对象MO1和MO2相对于QO的方向关系随着QO的位置变化相应也在变化。MO1和MO2在ts时刻和te时刻的方向关系交集序列为：

由以上交集序列可知，参照对象发生动态变化，将会极大影响计算机对方向关系的表示和分析结果。为了在3DR46方向关系模型下处理此类重要的动态方向关系表示与预测问题，首先给出动态连续邻接关系的定义如定义7所示。

定义7（动态连续邻接关系）在3DR46方向关系模型中，基于定义1，设参照对象为QO，目标对象为MO，MO相对于QO的方向关系在t1,t2,…,tn时刻分别表示为3DR46(QO,MO)t1,3DR46(QO,MO)t2,…,3DR46(QO,MO)tn。若3DR46(QO,MO)ti＋1包含的方向块可由3DR46(QO,MO)ti所包含的方向块直接转化而得（其中，1 ≤i＜n），则称3DR46(QO,MO)t1,3DR46(QO,MO)t2,…,3DR46(QO,MO)tn为一组动态连续邻接关系。

由定义7可知，每组动态连续邻接关系均包含不同时刻目标对象MO相对参照对象QO不同的方向关系，方向关系具有严格的顺序性，相邻方向关系之间可动态转换。3D参照对象位置发生动态改变，依据动态连续邻接关系的内在联系和规律即可进一步确定MO相对QO的方向关系的连续变化情况。由定义1和方向关系的交集序列可知，每个复杂的方向关系均可分解成MO和具体方向块的关系。虽然参照对象的运动方向和运动轨迹是任意的，但其运动方向最后均可分解成{Cu,Nm,Em,Sm,Wm,Cd}的子集，又因为Em和Wm,Sm和Nm,Cu和Cd具有高度的对称性，故重点研究参照对象朝Nm、Cd和Wm方向运动的46个方向块的动态连续邻接关系特性。其他运动情况可类似得出。

基于3DR46方向关系模型，图3（a）～（c）分别给出了参照对象运动方向为Nm、Wm和Cd时的详细动态连续邻接关系。

Fig.3 Dynamic continuous adjacency relations of typical principal direction motion图3 典型主方向运动动态连续邻接关系

图3中，“：”表示项和其动态转变关系的对应关系。“*”表示参照对象朝某主方向运动期间，其标注的方向关系不变。例如，图3（a）中的*WSSm即表示参照对象朝Nm方向运动时，目标对象起始时刻若处于WSSm方向块中，在之后的运动时间内，其相对于参照对象的方向关系将保持WSSm不变，除非运动方向发生改变。“→”表示运动过程中方向关系的动态连续转变，例如，图3（c）中WNWm→14W，即随着参照对象进行Wm方向的运动，目标对象相对参照对象的方向关系若发生动态连续变化，则可由WNWm直接转变到14W项所对应的项，14W项所表示的动态连续邻接关系为WNNm→13W，两项合并即可得到WNWm→WNNm→13W，13W项所表示的动态连续邻接关系为Nm→4W,… 。最后，由图3（c）可得出WNWm→WNNm→ENNm→*ENEm。图中“，”表示“或”的意思。根据方向块的动态连续邻接关系即可依据参照对象的运动情况对相关复杂的方向关系进行组合分析与智能预测。

4 3DR46方向关系模型双向映射关系

对于连续的无分离部分的单纯3D目标对象，利用3DR46方向关系模型表示和区分一些重要方向关系时，交集序列中的一些交集信息的计算经常是不必要的，往往具有很大的冗余性。尤其是3D目标对象变异为2D面对象、线对象或点对象时，冗余计算量将更大。针对一些连续的无分离部分的形状规则的3D目标对象，可对3DR46方向关系模型进行“降维”处理。主要思路和步骤如下：

（1）确定3D参照对象QO的3DR46方向关系模型下的46个方向空间块；

（2）确定目标对象MO在3D空间中的位置；

（3）将QO和其3DR46方向关系模型下的方向块分别向垂直相交的两个2D平面进行投影映射，将3DR46方向关系模型分解为两个2D空间中的方向关系模型；

（4）将目标对象MO向第（3）步中的两个2D平面进行投影映射，3D空间中的目标对象MO转化为两个2D平面中的目标对象；

（5）在两个2D空间中进行方向关系的表示与判断，得出相应的交集序列，再利用交集序列的联合来表示和分析目标对象MO和参照对象QO的方向关系。

为了便于投影计算，进行“降维”时，互相垂直的2D平面（投影面）的选择需要遵循一个原则：两个2D平面不能与参照对象和目标对象相交。

在三维坐标空间中，设O为坐标原点，坐标面xoz和xoy互相垂直，x,z,y是两两相互垂直的坐标轴，坐标面xoy和3D参照对象QO的最小包围盒的上、下面平行；坐标面xoz与前、后面相平行。将参照对象QO的3DR46方向元素空间分别向xoy面和xoz面进行映射投影。相应的，将目标对象MO也向坐标面xoy和xoz投影，得到投影像Pxy和Pxz。用BM(DRj)表示一个方向块DRj的投影像的集合。本章进一步给出了方向块Cu、CNLm、CNRm、CEDm、CEUm、CSRm、CSLm、CWDm、CWUm的投影像，其他方向块的投影像集可类似给出。

设参照对象QO的3DR46方向关系模型在xoz坐标面的投影方向集Ψxoz为{WSxz,WNxz,ENxz,CLxz,ESxz,Sxz,Nxz,Exz,Wxz,CRxz}；在xoy坐标面的投影方向集Ψxoy为{ENNxy,Sxy,Wxy,WNWxy,CWUxy,Exy,Nxy,CNLxy,WSWxy,ENExy,CWDxy,WSSxy,ESSxy,CSLxy,CEUxy,WNNxy,CEDxy,ESExy,CNRxy,CSRxy}。基于所得的双向映射关系即可利用2D方向关系模型对一些重要的3D方向关系进行表示和处理。在描述形状复杂的3D目标对象和参照对象的方向关系时，由于经过投影映射这一重要环节，对象的复杂性和细节特性在映射后往往被掩盖了，有时会造成表示误差。

5 实验比较与实例分析

5.1 实验分析

已有的研究成果从不同角度给出了3D方向关系表示与处理方法。虽然文献[8-12,17]的方法都适合表示3D方向关系，但方向关系的表示和区分能力各有差别。本文所提出的3DR46模型可表示和区分246种复杂的方向关系，分别是文献[12,17]所提模型的128倍，是文献[8-11]所提方法的219倍。进一步，和其他研究成果相比，本文方法更适合处理3D动态方向关系，且对3D方向关系序列的连续性推导有较强的处理能力。文献[8-12,17]的方法无法有效处理动态方向关系的连续性检验与分析问题。

为了分析本文所提出的动态方向关系连续性检验方法的效率，在Pentium4，3.2 GHz CPU，16 GB内存，Windows XP环境下进行了实验分析。根据3DR46方向关系模型的特征和实例模型，所开发的方向关系实验模拟器（DR_MOD3.0）生成的大量交集序列数据为本实验提供了有效的实验数据信息。图4给出了实验结果。

Fig.4 Efficiency analysis of sequence continuity testing algorithms图4 序列连续性检验算法效率分析

图4（a）展示了在待检验序列数目递增，不连续序列数分别为1 300、4 100和7 500的情况下的实验结果（如曲线l1、l2和l3所示）。横坐标表示待检验的序列数，纵坐标表示检验和更新的时间耗费。由图4（a）可知，在不连续序列数保持不变的情况下，随着待检验序列数目的递增，耗费的代价将逐渐增加；若待检测的序列集数不变，序列集中的不连续序列数越大，耗费的代价将越大。

在一个规模较大的序列集中，非连续序列的分布情况是多样的。非连续序列分布情况的不同，检验方法的代价将会有很大差别。图4（b）展示了非连续序列不同分布情况下的比较情况，其中横坐标表示非连续序列在序列集中的占比，纵坐标γ表示非连续序列随机分布情况下的检验代价α和正态分布情况下的检验代价β的比值，即γ=α/β。由图4（b）可知，对于规模较大的一个序列集，非连续序列在其中的比重较小时，随机分布和正态分布两种情况下的检验代价较为接近，在占比较大的情况下，随机分布情况下的检验代价将远大于正态分布情况下的代价。

5.2 实例分析

Fig.5 Dynamic direction relation graphics in 3DR46 relational model图5 3DR46关系模型下的动态方向关系图示

基于理论研究成果，本节进一步给出模拟实例模型。如图5所示，在3DR46关系模型下，3D目标对象M1随时间进行运动（位置变化），Q和M2是3D静止对象。图中表示起始时刻的目标对象，等表示中间时刻的目标对象，表示终止时刻的目标对象。曲线l1和l2表示两条运动路径及运动方向。

M1若沿着l1由起始位置运动到终点位置，即由变为，基于3DR46方向关系模型可知其相对于参照对象Q的3D方向关系共经历了18种不同的方向关系。以下给出M1在起始时刻t1到终止时刻t2共18个时刻所处的不同的方向块信息。显然，该18个时刻分别隶属于18个连续时间段，在每个时间段，M1相对于Q的方向关系保持不变。

基于以上方向块信息，进一步得出18个方向关系的交集序列如图6所示。

Fig.6 Intersection sequences of dynamic direction relations图6 动态方向关系的交集序列

根据3DR46模型的方向动态邻接关系和算法1，可检测所得出的交集序列的连续性。根据算法1，M1沿着l1运动时，在紧邻的时刻t6和t7所得的Lt6和Lt7不具有连续性（Lt7在图6中用灰色特别标出）。具体分析Lt6和Lt7可知，在t6时刻，M1的一部分处于CSRm、CEDm、CEUm等方向块中；在紧邻的t7时刻，M1没有任何部分处于CSRm和CEDm方向块中，但M1的一部分尚处于CEUm方向块中。由图5可知，CSRm和CEUm由CEDm分割开；又由3DR46模型的动态邻接关系可知，CSRm的5个邻接方向块为CEDm、CSLm、Sm、Cd和Cu。由此可知，M1沿着l1运动时，M1的一部分不可能由方向块CSRm跳过CEDm而直接运动到CEUm，故Lt6和Lt7不具有连续性。

6 结束语

为了弥补已有方法的不足，本文提出了3DR46方向关系模型。在目标对象的运动情况下详细研究了该模型的动态方向关系，给出了判断3D方向关系动态连续性的检验算法；进一步研究了参照对象的运动情况下方向关系的动态连续邻接关系；在处理一些特殊的3D方向关系时，为了减少计算冗余和充分利用2D空间方向关系表示技术，给出了3DR46方向关系的双向映射关系。理论分析和实验表明，本文的工作增强了空间数据库对空间方向关系的表示精度，提高了对静态和动态的复杂的3D细节方向关系的处理能力。未来的研究重点主要是基于3DR46方向关系模型构建3D方向关系的空间索引树，设计高效的查询算法以增强空间数据库对复杂空间方向关系的查询能力。