一种基于OPRA4方向关系推理定性距离变化的方法

董轶群 刘建东 徐文星 王淑鸿

(北京石油化工学院信息工程学院 北京 102617)

定性空间推理是人工智能的重要组成部分[1-4]，在基于内容的图像检索[5]、生物信息学[6]、地理信息系统[7]、智能交通[8-9]、空间数据库[10]等领域中有着广泛应用.面向拓扑[10-14]、方向[15-24]、距离[25]等单一方面空间关系的定性表示与推理研究已经非常深入.然而采用单一空间关系难以对复杂的空间信息进行有效处理.例如在智能交通领域中通常需要综合路网拓扑信息、交通对象的移动方向以及彼此间的距离信息展开相关应用.因此结合2种以及2种以上空间关系的表示与推理成为近年来的研究热点[26-36].

空间位置信息的有效表示与推理通常需要结合方向和距离关系.在定性方向与距离关系的结合研究方面已取得一些研究成果.Clementini等人[26]面向点对象，以参考对象为圆心，用若干个同心圆对二维平面空间进行不同粒度地划分，通过主对象在参照框架中的分布情况来描述其相对于参照对象的定性距离关系，进而给出了距离系统的形式化定义；在该模型的基础上，将定性方向与距离关系相结合用于描述空间对象间的相对位置关系，并研究了该位置关系上的复合运算.Frank[32]提出了一种能够统一描述点对象间“东”、“南”、“西”、“北”方向关系与“远”、“近”距离关系的定性表示模型，并研究了该模型上的复合运算与逆运算性质.王中辉等人[33]面向简单区域对象，将8方向锥形模型与距离关系相结合，提出一种能够同时描述定性方向与距离关系的表示模型；并在该模型基础上利用四叉树索引与最小边界矩形提出一种基于方向与距离关系的复合空间查询算法.许小艳[34]面向点对象提出一种基于锥形与距离划分相结合的表示模型，该模型能够统一描述定性方向与距离关系；利用定性三角形推理方法，通过三角形的边—角关系划分定性角度值和距离值，在此基础上研究了方向与距离关系的组合推理规则.Weghe等人[37]综合考虑时间属性、定性距离关系与十字方向关系，提出了定性轨迹演算(qualitative trajectory calculus, QTC).文献[38-40]通过扩展QTC提出了定性直线投影演算(qualitative rectilinear projection calculus, QRPC)、点-轨迹定性轨迹演算(point-trajectory QTC, P-tQTC)等一系列面向平面轨迹对象的时空关系模型，然而此类模型中方向与距离的定性域多为{0,+,-}，难以描述复杂的实际问题.

现有定性方向与距离关系的结合研究多是面向静态空间对象；侧重2种关系的组合表示方法，通常利用方向关系对当前状态下的距离关系进行推理，难以对后续的定性距离变化做出有效推断.然而在众多领域中，定性距离变化的分析与预测至关重要，是开展轨迹相似性分析、交通流量预测、时空数据库连续查询等空间位置相关理论与应用研究的重要基础.例如在“连续查询路网中距离某个用户最近的k个移动对象”、“实时分析预测某一区域内的交通流量”等应用中，大规模的交通对象和连续的查询请求对相关理论模型与应用系统提出了挑战.利用方向关系首先筛选出“将接近”或“将远离”用户和区域的交通对象，然后再有针对性地进行定量距离计算，是提高算法性能、缓解系统计算压力的一种有效途径.然而这种基于移动对象间方向关系推理定性距离变化的研究尚不多见.

1 背景知识

在少数针对移动对象的方向关系模型中，OPRAm不仅表达能力强，同时还具备良好的复合运算与逆运算性质[17]，因此本文研究工作基于该模型展开.

1.1 OPRAm模型

OPRAm忽略空间对象的尺寸与维度，将一个移动的空间对象抽象为一个带方向的点，称为有向点，可以用一个序对进行表示：

S=(PS,φS),

(1)

其中，PS为S的位置，用S的坐标表示，即PS=(xS,yS);φS是从x轴正向逆时针旋转到PS所形成的旋转角，用以表示S的移动方向.该旋转角取值区间是[0,2)上的循环群，例如-3与53相等.

定义1.给定粒度参数m∈+,有向点A,B之间的OPRAm关系ROPRAm(A,B)定义为

(2)

(3)

图

由定义1,对于任意2个有向点A,B,在用OPRA4模型(即OPRAm的粒度参数m=4)描述二者方向关系时，首先将A视为参照对象，根据A的移动方向，采用4条以A为交点的直线对二维平面进行等分，确定A所对应的参照系统，其中包含了8个扇形区域、8条射线以及一个中心点，共17个部分；在此基础上，将B作为主对象，根据B在A所确定的参照系统中的分布情况来描述B相对于A的方向.反之，采用同样的方式可确定A相对于B的方向；最后综合二者之间的相对方向，得到A,B之间的基本OPRA4方向关系.按照上述方式，若PA≠PB,则A,B间存在256种基本OPRA4方向关系；特殊地，若PA=PB,则A,B间存在16种基本OPRA4方向关系，因此共有272种基本OPRA4方向关系.若干基本OPRA4方向关系构成的一个非空集合称为OPRA4方向关系.

1.2 定性距离变化

距离是一种重要的空间信息，常见的有欧氏距离、闵可夫斯基距离和曼哈顿距离等，这些都是对距离的定量度量方式.然而精准的定量距离信息通常难以甚至无法获得；而且在许多应用场景中，尤其是一些具有流式计算或实时性需求的场景中，通常需要定性距离或定性距离变化作为后续数据分析与处理的依据.

以“连续查询路网中距离用户A最近的3辆出租车”应用场景为例，在此连续查询过程中，若每一次查询时对所有出租车到用户A的距离进行计算后排序，那么随着出租车数量与查询频率的增加，系统将面临巨大的计算压力，很难满足实时性需求.若每一次查询前，首先基于方向关系对出租车与用户A之间的定性距离变化进行推理，筛选出距离“将变小”的出租车组成候选集合，然后再对候选集合内的出租车计算路网距离并排序，将有助于提高模型的有效性与系统的执行效率.

本文面向二维平面空间中移动的点对象，考虑对象间的欧氏距离，将定性距离变化分为“变大”、“变小”、“不变”和“不确定”共4种情况.本文着重研究OPRA4方向关系对这4种定性距离变化的约束作用.

2 OPRA4对定性距离变化的约束

2.1 移动对象间的相对位置关系Rpos-pair

Fig. 2 The spatial positions of A and CBA,B and CAB图2 A与CBA，B与CAB的空间位置示例图

对于有向点A=(PA,φA)与B=(PB,φB),用A,B分别表示以A,B为起点的射线；用AB表示以A为起点、B为终点的一条有向线段；用CAB表示以A为圆心，以A与B之间的欧氏距离(|AB|)为半径的圆.不难发现，在A,B移动过程中，A与CBA以及B与CAB的空间位置在一定程度上能够反映出二者之间距离的变化趋势.例如在图2中，若不考虑静止情况，A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将变小.

为了系统研究这种空间位置与定性距离变化的约束作用，首先参照直线与圆的位置关系，根据A到B的投影情况来定义B与CAB之间的位置关系.

定义2.对于有向点A=(PA,φA)与B=(PB,φB),PA≠PB,将A向B所在直线投影得投影点Proj(A),若|AProj(A)|=|AB|,即Proj(A)=B,则称B与CAB相切，记为q(B,CAB).

Fig. 3 The possible position relations between B and CAB图3 B与CAB之间可能的位置关系

定义3.对于有向点A=(PA,φA)与B=(PB,φB),PA≠PB,将A向B所在直线投影得投影点Proj(A),若|AProj(A)|<|AB|且Proj(A)∈B,则称B与CAB相割，记为g(B,CAB).

定义4.对于有向点A=(PA,φA)与B=(PB,φB),PA≠PB,将A向B所在直线投影得投影点Proj(A),若|AProj(A)|<|AB|且Proj(A)B,则称B与CAB相离，记为l(B,CAB).

特殊地，当PA=PB时，即有向点A,B坐标重合，有|AB|=0,此时圆CAB相当于一点，用定义5来描述这种特殊情况.

定义5.对于有向点A=(PA,φA)与B=(PB,φB),若PA=PB,则称B与CAB同置，记为t(B,CAB).

很显然，若t(B,CAB)则必然有t(A,CBA).

定义2～5对应的4种关系分别如图3(a)～(d)所示.

定义6.对于任意2个有向点A,B,由B与CAB之间的位置关系所构成的集合记为Rpos,则有：

Rpos={q,g,l,t},

(4)

称Rpos中的每一个元素为一个基本Rpos关系.

定理1.关系集合Rpos是完备互斥的.

证明. 对于二维平面中任意2个有向点A,B,若二者坐标不同，则Proj(A)与射线B必定满足3种可能的位置关系(Proj(A)=B,|AProj(A)|<|AB|且Proj(A)∈B,|AProj(A)|<|AB|且Proj(A)B)中的一种，由上述定义2～4可知，对应的B与CAB之间必定满足3种关系q,g,l中的一种；若A,B坐标相同，则由定义5可知对应的B与CAB之间满足关系t.因此任意2个有向点A,B之间必定满足一种基本Rpos关系且仅满足一种，即关系集合Rpos是完备互斥的.

证毕.

为了更加全面准确地描述任意2个有向点A,B之间的空间信息，不仅要明确B与CAB之间的位置关系，还要明确A与CBA之间的位置关系.

定义7.Rpos-pair为Rpos上的一个有序二元关系，定义为

Rpos-pair={g,g,g,q,g,l,q,g,q,q,
q,l,l,g,l,q,l,l,t,t}，

(5)

称Rpos-pair中每一个元素为一个基本Rpos-pair关系.

利用Rpos-pair可描述有向点间的相对位置关系.对于任意2个有向点A,B,二者满足一种基本Rpos-pair关系，其语义如表1所示：

Table 1 The Semantic of Basic Rpos-pair Relations表1 基本Rpos-pair关系语义表

推论1.关系集合Rpos-pair是完备互斥的.

证明.Rpos上的二元关系最多包含16个元素，由定义5可知对于任意2个有向点A,B,若t(B,CAB)则t(A,CBA),即二者不存在6种相对位置关系：t,g,t,q,t,l,g,t,q,t,l,t;且定理1已证明集合Rpos是完备互斥的，因此A,B必定满足Rpos-pair中10个关系中的一种且仅一种，即Rpos-pair也是完备互斥的.

证毕.

2.2 Rpos-pair对定性距离变化的约束

对于任意2个有向点A=(PA,φA)与B=(PB,φB),在不同基本Rpos关系下，φB与φAB之间满足命题1～3.

命题1.对于任意2个有向点A=(PA,φA)与B=(PB,φB),若l(B,CAB),φAB∈[0,2π),则有φB∈(φAB-π2,φAB+π2).

证明. 当φAB∈[0,π2)时，如图4所示，若l(B,CAB),由定义4可知Proj(A)应位于CAB上过B点切线的下方，基于平面几何中角度间的关系易知φB∈(φAB-π2,φAB+π2).

Fig. 4 The range of φBwhen l(B,CAB) and φAB∈[0,π2)图4 l(B,CAB)且φAB∈[0,π2)时φB取值示例图

类似地，若l(B,CAB),分别当φAB∈[π2,π),φAB∈[π,3π2),φAB∈[3π2,2π)时，均有φB∈(φAB-π2,φAB+π2).

证毕.

同理可证命题2与命题3成立.

命题2.对于任意2个有向点A=(PA,φA)与B=(PB,φB),若g(B,CAB),φAB∈[0,2π),则有φB∈(φAB+π2,φAB+3π2).

命题3.对于任意2个有向点A=(PA,φA)与B=(PB,φB),若q(B,CAB),φAB∈[0,2π),则有φB=φAB+(2k+1)π2,k∈.

不难发现，有向点A,B的移动方向、在各自方向上的移动距离、AB与x轴的夹角等因素均影响着二者之间后续的定性距离变化.下面通过定理2给出上述因素与定性距离变化之间的关系.

定理2.任意2个有向点A=(PA,φA)与B=(PB,φB),分别沿着各自方向移动LA,LB后到达A′=(PA′,φA),B′=(PB′,φB),若PA≠PB且A与CBA以及B与CAB之间不存在相切关系，当LA=LB=0时|A′B′|2的增量z满足：

z≈-2((xB-xA)cosφA+
(yB-yA) sinφA)LA+2((xB-xA)cosφB+
(yB-yA)sinφB)LB,

(6)

其中,φA,φB,φAB∈[0,2π),PA=(xA,yA),PB=(xB,yB),PA′=(xA′,yA′),PB′=(xB′,yB′),LA≥0与LB≥0分别为一微小时间间隔内LA,LB的增量.

证明. 由2点间距离公式可知:

(7)

构造二元函数

z=f(LA,LB)=|A′B′|2,

(8)

将式(7)带入式(8)有:

f(LA,LB)=(xB′-xA′)2+(yB′-yA′)2,

(9)

由于xB′=LBcosφB+xB,yB′=LBsinφB+yB,xA′=LAcosφA+xA,yA′=LAsinφA+yA,例如图5所示:

Fig. 5 The corresponding coordinates, angle and distances of A and B图5 有向点A,B相关坐标、夹角、移动距离示例图

因此有:

f(LA,LB)=(LBcosφB+xB-
LAcosφA-xA)2+
(LBsinφB+yB-LAsinφA-yA)2,

(10)

整理后有:

f(LA,LB)=(LBcosφB-LAcosφA)2+
(LBsinφB-LAsinφA)2+
2(LBcosφB-LAcosφA)(xB-xA)+
2(LBsinφB-LAsinφA)(yB-yA)+
(xB-xA)2+(yB-yA)2.

(11)

函数f(LA,LB)描述了有向点A,B沿着各自方向移动的距离(分别为LA,LB)与A,B移动后二者间距离(即|A′B′|)之间的关系.对f(LA,LB)求一阶偏导数有:

fLA=2(LA-LBcos(φA-φB)-
(xB-xA)cosφA-(yB-yA)sinφA),

(12)

fLB=2(LB-LAcos(φA-φB)+
(xB-xA)cosφB+(yB-yA)sinφB),

(13)

因此f(LA,LB)在LA=LB=0处的全增量z满足:

z≈dz=-2((xB-xA)cosφA+
(yB-yA)sinφA)LA+2((xB-xA)cosφB+
(yB-yA)sinφB)LB.

(14)

若PA=PB,则xB=xA,yB=yA,此时无论φA,φB,LA与LB如何取值，式(14)中z恒为0.这意味着在微小时间间隔内，z无法准确表示有向点A,B间的距离增量.

若PA≠PB且xB=xA,则yB≠yA.当q(A,CBA)时,必有φA=k,k∈Z,因此sinφA=0,使得无论LA如何取值，式(14)中LA系数恒为0.这意味着无论有向点A如何移动，式(14)中z无法准确描述LA对A,B间距离增量的约束作用.

若PA≠PB且xB≠xA,式(14)可进一步整理为

z≈-2(cosφA+tanφABsinφA)(xB-xA)LA+
2(cosφB+tanφABsinφB)(xB-xA)LB.

(15)

当q(A,CBA)时,由命题3可知φA=φBA+(2k+1)π2,k∈Z,由于φBA=φAB+π,因此φAB-φA=-(2k+3)π2,k∈Z,即cos(φAB-φA)=0.根据三角函数和差公式可知cosφABcosφA+sinφABsinφA=0,即cosφA=-tanφABsinφA,使得无论LA如何取值，式(15)中LA系数恒为0,即式(15)中z无法准确描述LA对A,B间距离增量的约束作用.同理，q(B,CAB)时情况类似.

证毕.

本文将利用定理2研究任意2个有向点在不同基本Rpos-pair关系下的定性距离变化.

推论2.对于任意2个有向点A,B,若Ag,gB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将不变或变小.

证明. 设A,B分别沿着各自当前方向移动了LA,LB到达A′,B′,经过某一微小时间间隔后到达A″,B″,期间LA,LB的增量分别为LA≥0与LB≥0.已知Ag,gB,当LA=LB=0时基于定理2中式(6)对LA,LB分情况讨论：

Fig. 6 Ag,gB and LA=LB=0图6 Ag,gB且LA=LB=0示例图

综上所述，若Ag,gB,在一微小时间间隔内A,B沿着当前方向移动，若至少一方移动的距离不为0，则二者之间距离将变小；若二者移动距离均为0，则二者之间距离将不变.

证毕.

推论3.对于任意2个有向点A,B,若Al,lB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将不变或变大.

Fig. 7 Al,lB and LA=LB=0图7 Al,lB且LA=LB=0示例图

综上所述，若Al,lB,在一微小时间间隔内A,B沿着当前方向移动，若至少一方移动的距离不为0,则二者之间距离将变大；若二者移动距离均为0,则二者之间距离将不变.

证毕.

在Rpos描述的位置关系中，相切作为相割、相离之间的邻接关系，其情况比较特殊.对于有向点A,B,若A与CBA或B与CAB之间存在相切关系，那么二者移动过程中的距离变化更加复杂，无法完全适用定理2,一些情况需要单独讨论.

推论4.对于任意2个有向点A,B,若Ag,qB或Aq,gB,则在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离变化不确定.

证明. 当Ag,qB时，设A,B分别沿着各自当前方向移动了LA,LB到达A′,B′,经过某一微小时间间隔后到达A″,B″,期间LA,LB的增量分别为LA≥0与LB≥0.对LA,LB分情况讨论：

1) 与定理2中式(14)之前的证明部分相同，已知Ag,qB,因此有PA≠PB,g(B,CAB).若limLA=0,limLB≠0,此时与推论2中的情况1证明相同，可知二者之间距离将变小.

2) 已知q(A,CBA),在证明定理2时已说明，此时cos(φAB-φA)=0,使得式(14)中LA的系数恒为0,无法用式(14)讨论距离变化.当PA≠PB,LA=LB=0时，可知B′=B,A′=A,|A′B′|=|AB|;当limLB=0,limLA≠0时，可知B″与B′近似相等，如图8所示，因此有|A″B″|≈|A″B′|.根据致直角三角形斜边大于直角边可知|A″B″|>|A′B′|,进而有|A″B″|>|AB|,因此二者之间距离将变大.

Fig. 8 Ag,qB,lim LB=0 and lim LA≠0图8 Ag,qB,lim LB=0且lim LA≠0示例图

综上所述，若Ag,qB在微小时间间隔内A,B分别沿着各自当前方向移动距离的不同情况可能导致二者之间的距离变小、变大或者是不变，因此无法确定二者之间的距离变化.

同理可证，当Aq,gB时，A,B之间距离变化不确定.

证毕.

类似地，基于定理2可证明推论5～7成立.

推论5.对于任意2个有向点A,B,若Ag,lB或Al,gB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离变化不确定.

推论6.对于任意2个有向点A,B,若Al,qB或Aq,lB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将不变或变大.

推论7.对于任意2个有向点A,B,若Aq,qB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将不变或变大.

特殊地，当2个有向点对应的射线与圆存在同置关系时，二者之间的距离变化如定理3所述.

定理3.对于任意2个有向点A,B,若At,tB,在A,B分别沿着各自当前方向移动某一微小时间间隔后，二者之间距离将不变或变大.

证明. 当有向点A,B对应的射线与圆存在同置关系时，根据定义5有PA=PB,如图3(d)所示，若二者的移动方向与速度均相同，则二者之间距离保持不变；若二者移动方向或速度不同，则二者之间距离必将变大.

证毕.

在证明定理2、定理3以及推论2～7的过程中，将微小时间间隔内有向点的静止状态视为移动过程中的一种特殊状态，因此本文面向移动对象提出的理论模型同样适用于静止对象间、静止对象与移动对象间的方向与距离关系结合推理.

2.3 Rpos-pair与OPRA4的对应关系

首先通过命题4～7研究基本Rpos关系与OPRA4方向关系之间的对应关系；然后给出基本Rpos-pair关系与OPRA4方向关系之间的对应关系.

证明. 由命题1可知，对任意2个有向点A,B,若l(B,CAB),则有φB∈(φAB-π2,φAB+π2).令δ=(φBA-φB),由式(2)可知j=Qm(δ);由于φBA=φAB+π,因此δ∈(π2,3π2),由式(3)可知j∈{5,6,7,8,9,10,11}.

证毕.

与命题4的证明过程类似，可证命题5与命题6成立.

命题7.对于任意2个有向点A,B,若t(B,CAB),则A4∠kB,其中k∈{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

证明. 由定义5可知，若有向点A,B对应的射线与圆之间存在同置关系，则有PA=PB,进而由定义1可知A4∠kB,其中k∈{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

证毕.

通过上述命题4～7可归纳出基本Rpos关系与OPRA4方向关系之间的对应表，如表2所示；在此基础上，通过组合方式可进一步得到基本Rpos-pair关系与OPRA4方向关系之间的对应关系，如表3所示.

Table 2 Corresponding Table of Basic Rpos Relations and OPRA4 Direction Relations

Table 3 Corresponding Table of Basic Rpos-pair Relations and OPRA4 Direction Relations表3 基本Rpos-pai与OPRA4方向关系对应表

2.4 OPRA4对定性距离变化的约束

对于任意2个有向点A,B,本文2.2节给出了A,B间基本Rpos-pair关系对二者间定性距离变化的约束作用；2.3节明确了A,B间基本Rpos-pair关系与二者间OPRA4方向关系的对应关系.因此借助于基本Rpos-pair关系可以建立起OPRA4方向关系与定性距离变化的内在联系，如表4所示.

表4相当于给出了OPRA4方向关系全集的一个划分：

(16)

Table 4 Corresponding Table of OPRA4 Direction Relations and Qualitative Distance Changes表4 OPRA4方向关系与定性距离变化对应表

对于任意2个有向点A,B,二者满足的基本OPRA4方向关系必定属于该划分中的某个子集且仅属于一个子集.因此，当已知A,B之间的基本OPRA4方向关系时，可以参照表4对二者之间定性距离变化进行相应的判断.

3 基于OPRA4推理定性距离变化算法与实例

为方便形式化表示与说明，将二维平面中2个有向点间的4种定性距离变化“变大”、“变小”、“不变”、“不确定”分别用further,nearer,unchange,uncertain表示，构成的集合记为Udis,则有：

Udis={further,nearer,unchange,uncertain}.

(17)

下面给出算法1是OPRA4-Distance的伪代码对于任意2个有向点，当已知二者当前基本OPRA4方向关系时，用该算法对微小时间间隔内二者基于Udis的定性距离变化进行推断.

算法1.OPRA4-Distance.

输出：有向点A,B间的定性距离变化D∈2Udis.

①D←;

③ if(((i≥4 andi≤12) and (j≥5 andj≤11)) or ((i≥4 andi≤12) and (j=4 orj=12)))

④D←{unchange,further};

⑤ end if

⑥ if((((i≥0 andi≤3) or (i≥13 andi≤15)) and (j≥4 andj≤12)) or (((j≥0 andj≤3) or (j≥13 andj≤15)) and (i≥4 andi≤12)))

⑦D←{uncertain};

⑧ end if

⑨ if(((i≥0 andi≤3) or (i≥13 andi≤15)) and ((j≥0 andj≤3) or (j≥13 andj≤15)))

⑩D←{unchange,nearer};

定理4.对于任意2个有向点A,B,若已知二者间的基本OPRA4方向关系,算法OPRA4-Distance能够正确推断出后续微小时间间隔内二者间基于Udis的定性距离变化.

证明. 设有向点A,B满足基本OPRA4方向关系R.

证毕.

以智能交通中的“连续k近邻查询”问题为例介绍本文理论模型的具体应用.

例1.如图9所示，时刻ti与tj路网中有A,B1,B2,B3,B4,B5,B6共7个移动对象，以A作为查询对象，连续查询距离A最近的2个移动对象.路网中移动对象与道路边交点间的数值表示距离，tj=ti+t,t为某一微小时间间隔.

Fig. 9 An example of moving objects in a road network from time tito tj图9 路网中移动对象距离变化示例

针对例1，首先将连续k近邻查询转换为以t为周期的周期式查询.下面通过算法OPRA4-Distance-Candidate给出基于OPRA4和定性距离变化筛选移动对象候选集的方法，其中q为查询对象，R为基本OPRA4方向关系，Dis∈2Udis为定性距离变化集，Candidate为当前查询过程中确定的初始移动对象候选集，ResultKNN为上一次查询结果，CandidateKNN为当前查询过程中基于OPRA4和定性距离变化筛选后的移动对象候选集.

算法2.OPRA4-Distance-Candidate.

输入：Candidate,ResultKNN;

输出：CandidateKNN.

① for eachpinCandidate

③Dis=OPRA4-Distance(R);

④ if (Dis={unchanged,further})

⑤Candidate=Candidate-{p};

⑥ end if

⑦ end for

⑧CandidateKNN=Candidate∪ResultKNN.

在智能交通领域中，不同的连续k近邻查询方法在路网与移动对象的建模、索引结构设计、地图匹配策略、对象间距离的计算、路段与移动对象候选集的确定等环节采用了不同的方法.算法2主要针对移动对象候选集的确定环节.在例1中，为方便说明，设时刻ti查询确定的CandidateKNN={B1,B2,B3,B4,B5,B6},计算B1～B6各点到A的路网距离后排序，可知时刻ti查询结果ResultKNN={B1,B2},如图9(a)所示.经过t后到达时刻tj，首先确定时刻tj查询的Candidate(不同连续k近邻查询方法中确定移动对象候选集的方式不尽相同，此处不做详细讨论)，为方便说明，设Candidate={B1,B2,B3,B4,B5,B6}.由图9(b)和语句①②可知在时刻tj,Candidate中各移动对象与A之间分别满足如下基本OPRA4方向关系：此时基于语句③可知，B2,B3与A的距离将不变或变小；B1,B5,B6与A的距离不变或变大；B4与A的距离变化不确定.由于路网中两点间的欧氏距离小于等于路网距离，因此经由语句④⑤筛选后可确定Candidate={B2,B3,B4}.由于以微小时间间隔为查询周期，因此上一次的查询结果很可能与本次查询结果存在交集，应将时刻ti的查询结果纳入候选集，进而由语句⑧可知CandidateKNN={B1,B2,B3,B4}.经过上述筛选过程，无需再考虑路网中所有移动对象，仅需计算CandidateKNN中的4个移动对象到A的路网距离并排序，得到时刻tj的查询结果ResultKNN={B2,B3},如图9(b)所示.由此可见，本文提出的推理方法可作为确定移动对象候选集的一项重要依据，能够有效地过滤掉连续k近邻查询过程中的部分不合格移动对象，从而减少距离计算与排序的代价.

例1和算法OPRA4-Distance-Candidate仅给出利用本文理论模型优化连续k近邻查询问题的简单示意.由于采用OPRA4模型表示方向关系，因此与QTC,QRPC中采用的十字方向关系模相比，本文提出的理论模型对空间方向信息的描述粒度更精细、基于方向关系对定性距离变化的推理粒度更精细，更有助于处理复杂交通网络中的问题.然而在实际应用中通常还需要综合考虑时间、速度、查询对象的范围、路网拓扑结构、交通规则约束等多方面因素对移动对象进行筛选，进而得到规模更小、更准确的候选集合.

4 结论与展望

面向移动空间对象，针对OPRA4方向关系与定性距离变化的结合推理问题，本文首先通过定义射线与圆之间的Rpos关系描述目标对象相对于参照对象的移动方向；然后通过组合方式定义了Rpos-pair关系，用以描述2个移动对象间的相对Rpos关系；分别研究并证明了基本Rpos-pair关系对定性距离变化的约束作用、基本Rpos-pair关系与OPRA4方向关系之间的对应关系，进而借助于基本Rpos-pair关系建立起OPRA4方向关系与定性距离变化之间的内在联系.在此基础上提出一种基于基本OPRA4方向关系推理定性距离变化的方法，并证明了方法的正确性.最后以智能交通中的“连续k近邻查询”问题为例，进一步说明了本文理论模型的正确性与有效性.

速度是移动对象的一种固有属性，对各种空间关系(尤其是距离关系)有着重要的约束作用.如何在现有模型的基础上进一步结合速度等时空属性，是本文有待于深入研究的一个方面.概念邻域能够处理空间关系的连续变化问题，是进行时空推理的重要工具.然而基于OPRA4方向关系的概念邻域研究较少，这方面工作将有助于深化OPRA4方向关系与其他空间关系的结合推理研究，更加全面准确地对时空信息进行表示与推理.