董軼群 劉建東 徐文星 王淑鴻

(北京石油化工學(xué)院信息工程學(xué)院 北京 102617)

定性空間推理是人工智能的重要組成部分[1-4]，在基于內(nèi)容的圖像檢索[5]、生物信息學(xué)[6]、地理信息系統(tǒng)[7]、智能交通[8-9]、空間數(shù)據(jù)庫(kù)[10]等領(lǐng)域中有著廣泛應(yīng)用.面向拓?fù)鋄10-14]、方向[15-24]、距離[25]等單一方面空間關(guān)系的定性表示與推理研究已經(jīng)非常深入.然而采用單一空間關(guān)系難以對(duì)復(fù)雜的空間信息進(jìn)行有效處理.例如在智能交通領(lǐng)域中通常需要綜合路網(wǎng)拓?fù)湫畔?、交通?duì)象的移動(dòng)方向以及彼此間的距離信息展開相關(guān)應(yīng)用.因此結(jié)合2種以及2種以上空間關(guān)系的表示與推理成為近年來(lái)的研究熱點(diǎn)[26-36].

空間位置信息的有效表示與推理通常需要結(jié)合方向和距離關(guān)系.在定性方向與距離關(guān)系的結(jié)合研究方面已取得一些研究成果.Clementini等人[26]面向點(diǎn)對(duì)象，以參考對(duì)象為圓心，用若干個(gè)同心圓對(duì)二維平面空間進(jìn)行不同粒度地劃分，通過(guò)主對(duì)象在參照框架中的分布情況來(lái)描述其相對(duì)于參照對(duì)象的定性距離關(guān)系，進(jìn)而給出了距離系統(tǒng)的形式化定義；在該模型的基礎(chǔ)上，將定性方向與距離關(guān)系相結(jié)合用于描述空間對(duì)象間的相對(duì)位置關(guān)系，并研究了該位置關(guān)系上的復(fù)合運(yùn)算.Frank[32]提出了一種能夠統(tǒng)一描述點(diǎn)對(duì)象間“東”、“南”、“西”、“北”方向關(guān)系與“遠(yuǎn)”、“近”距離關(guān)系的定性表示模型，并研究了該模型上的復(fù)合運(yùn)算與逆運(yùn)算性質(zhì).王中輝等人[33]面向簡(jiǎn)單區(qū)域?qū)ο?，?方向錐形模型與距離關(guān)系相結(jié)合，提出一種能夠同時(shí)描述定性方向與距離關(guān)系的表示模型；并在該模型基礎(chǔ)上利用四叉樹索引與最小邊界矩形提出一種基于方向與距離關(guān)系的復(fù)合空間查詢算法.許小艷[34]面向點(diǎn)對(duì)象提出一種基于錐形與距離劃分相結(jié)合的表示模型，該模型能夠統(tǒng)一描述定性方向與距離關(guān)系；利用定性三角形推理方法，通過(guò)三角形的邊—角關(guān)系劃分定性角度值和距離值，在此基礎(chǔ)上研究了方向與距離關(guān)系的組合推理規(guī)則.Weghe等人[37]綜合考慮時(shí)間屬性、定性距離關(guān)系與十字方向關(guān)系，提出了定性軌跡演算(qualitative trajectory calculus, QTC).文獻(xiàn)[38-40]通過(guò)擴(kuò)展QTC提出了定性直線投影演算(qualitative rectilinear projection calculus, QRPC)、點(diǎn)-軌跡定性軌跡演算(point-trajectory QTC, P-tQTC)等一系列面向平面軌跡對(duì)象的時(shí)空關(guān)系模型，然而此類模型中方向與距離的定性域多為{0,+,-}，難以描述復(fù)雜的實(shí)際問(wèn)題.

現(xiàn)有定性方向與距離關(guān)系的結(jié)合研究多是面向靜態(tài)空間對(duì)象；側(cè)重2種關(guān)系的組合表示方法，通常利用方向關(guān)系對(duì)當(dāng)前狀態(tài)下的距離關(guān)系進(jìn)行推理，難以對(duì)后續(xù)的定性距離變化做出有效推斷.然而在眾多領(lǐng)域中，定性距離變化的分析與預(yù)測(cè)至關(guān)重要，是開展軌跡相似性分析、交通流量預(yù)測(cè)、時(shí)空數(shù)據(jù)庫(kù)連續(xù)查詢等空間位置相關(guān)理論與應(yīng)用研究的重要基礎(chǔ).例如在“連續(xù)查詢路網(wǎng)中距離某個(gè)用戶最近的k個(gè)移動(dòng)對(duì)象”、“實(shí)時(shí)分析預(yù)測(cè)某一區(qū)域內(nèi)的交通流量”等應(yīng)用中，大規(guī)模的交通對(duì)象和連續(xù)的查詢請(qǐng)求對(duì)相關(guān)理論模型與應(yīng)用系統(tǒng)提出了挑戰(zhàn).利用方向關(guān)系首先篩選出“將接近”或“將遠(yuǎn)離”用戶和區(qū)域的交通對(duì)象，然后再有針對(duì)性地進(jìn)行定量距離計(jì)算，是提高算法性能、緩解系統(tǒng)計(jì)算壓力的一種有效途徑.然而這種基于移動(dòng)對(duì)象間方向關(guān)系推理定性距離變化的研究尚不多見.

1 背景知識(shí)

在少數(shù)針對(duì)移動(dòng)對(duì)象的方向關(guān)系模型中，OPRAm不僅表達(dá)能力強(qiáng)，同時(shí)還具備良好的復(fù)合運(yùn)算與逆運(yùn)算性質(zhì)[17]，因此本文研究工作基于該模型展開.

1.1 OPRAm模型

OPRAm忽略空間對(duì)象的尺寸與維度，將一個(gè)移動(dòng)的空間對(duì)象抽象為一個(gè)帶方向的點(diǎn)，稱為有向點(diǎn)，可以用一個(gè)序?qū)M(jìn)行表示：

S=(PS,φS),

(1)

其中，PS為S的位置，用S的坐標(biāo)表示，即PS=(xS,yS);φS是從x軸正向逆時(shí)針旋轉(zhuǎn)到PS所形成的旋轉(zhuǎn)角，用以表示S的移動(dòng)方向.該旋轉(zhuǎn)角取值區(qū)間是[0,2)上的循環(huán)群，例如-3與53相等.

定義1.給定粒度參數(shù)m∈+,有向點(diǎn)A,B之間的OPRAm關(guān)系ROPRAm(A,B)定義為

(2)

(3)

圖

由定義1,對(duì)于任意2個(gè)有向點(diǎn)A,B,在用OPRA4模型(即OPRAm的粒度參數(shù)m=4)描述二者方向關(guān)系時(shí)，首先將A視為參照對(duì)象，根據(jù)A的移動(dòng)方向，采用4條以A為交點(diǎn)的直線對(duì)二維平面進(jìn)行等分，確定A所對(duì)應(yīng)的參照系統(tǒng)，其中包含了8個(gè)扇形區(qū)域、8條射線以及一個(gè)中心點(diǎn)，共17個(gè)部分；在此基礎(chǔ)上，將B作為主對(duì)象，根據(jù)B在A所確定的參照系統(tǒng)中的分布情況來(lái)描述B相對(duì)于A的方向.反之，采用同樣的方式可確定A相對(duì)于B的方向；最后綜合二者之間的相對(duì)方向，得到A,B之間的基本OPRA4方向關(guān)系.按照上述方式，若PA≠PB,則A,B間存在256種基本OPRA4方向關(guān)系；特殊地，若PA=PB,則A,B間存在16種基本OPRA4方向關(guān)系，因此共有272種基本OPRA4方向關(guān)系.若干基本OPRA4方向關(guān)系構(gòu)成的一個(gè)非空集合稱為OPRA4方向關(guān)系.

1.2 定性距離變化

距離是一種重要的空間信息，常見的有歐氏距離、閔可夫斯基距離和曼哈頓距離等，這些都是對(duì)距離的定量度量方式.然而精準(zhǔn)的定量距離信息通常難以甚至無(wú)法獲得；而且在許多應(yīng)用場(chǎng)景中，尤其是一些具有流式計(jì)算或?qū)崟r(shí)性需求的場(chǎng)景中，通常需要定性距離或定性距離變化作為后續(xù)數(shù)據(jù)分析與處理的依據(jù).

以“連續(xù)查詢路網(wǎng)中距離用戶A最近的3輛出租車”應(yīng)用場(chǎng)景為例，在此連續(xù)查詢過(guò)程中，若每一次查詢時(shí)對(duì)所有出租車到用戶A的距離進(jìn)行計(jì)算后排序，那么隨著出租車數(shù)量與查詢頻率的增加，系統(tǒng)將面臨巨大的計(jì)算壓力，很難滿足實(shí)時(shí)性需求.若每一次查詢前，首先基于方向關(guān)系對(duì)出租車與用戶A之間的定性距離變化進(jìn)行推理，篩選出距離“將變小”的出租車組成候選集合，然后再對(duì)候選集合內(nèi)的出租車計(jì)算路網(wǎng)距離并排序，將有助于提高模型的有效性與系統(tǒng)的執(zhí)行效率.

本文面向二維平面空間中移動(dòng)的點(diǎn)對(duì)象，考慮對(duì)象間的歐氏距離，將定性距離變化分為“變大”、“變小”、“不變”和“不確定”共4種情況.本文著重研究OPRA4方向關(guān)系對(duì)這4種定性距離變化的約束作用.

2 OPRA4對(duì)定性距離變化的約束

2.1 移動(dòng)對(duì)象間的相對(duì)位置關(guān)系Rpos-pair

Fig. 2 The spatial positions of A and CBA,B and CAB圖2 A與CBA，B與CAB的空間位置示例圖

對(duì)于有向點(diǎn)A=(PA,φA)與B=(PB,φB),用A,B分別表示以A,B為起點(diǎn)的射線；用AB表示以A為起點(diǎn)、B為終點(diǎn)的一條有向線段；用CAB表示以A為圓心，以A與B之間的歐氏距離(|AB|)為半徑的圓.不難發(fā)現(xiàn)，在A,B移動(dòng)過(guò)程中，A與CBA以及B與CAB的空間位置在一定程度上能夠反映出二者之間距離的變化趨勢(shì).例如在圖2中，若不考慮靜止情況，A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將變小.

為了系統(tǒng)研究這種空間位置與定性距離變化的約束作用，首先參照直線與圓的位置關(guān)系，根據(jù)A到B的投影情況來(lái)定義B與CAB之間的位置關(guān)系.

定義2.對(duì)于有向點(diǎn)A=(PA,φA)與B=(PB,φB),PA≠PB,將A向B所在直線投影得投影點(diǎn)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之間可能的位置關(guān)系

定義3.對(duì)于有向點(diǎn)A=(PA,φA)與B=(PB,φB),PA≠PB,將A向B所在直線投影得投影點(diǎn)Proj(A),若|AProj(A)|<|AB|且Proj(A)∈B,則稱B與CAB相割，記為g(B,CAB).

定義4.對(duì)于有向點(diǎn)A=(PA,φA)與B=(PB,φB),PA≠PB,將A向B所在直線投影得投影點(diǎn)Proj(A),若|AProj(A)|<|AB|且Proj(A)B,則稱B與CAB相離，記為l(B,CAB).

特殊地，當(dāng)PA=PB時(shí)，即有向點(diǎn)A,B坐標(biāo)重合，有|AB|=0,此時(shí)圓CAB相當(dāng)于一點(diǎn)，用定義5來(lái)描述這種特殊情況.

定義5.對(duì)于有向點(diǎn)A=(PA,φA)與B=(PB,φB),若PA=PB,則稱B與CAB同置，記為t(B,CAB).

很顯然，若t(B,CAB)則必然有t(A,CBA).

定義2～5對(duì)應(yīng)的4種關(guān)系分別如圖3(a)～(d)所示.

定義6.對(duì)于任意2個(gè)有向點(diǎn)A,B,由B與CAB之間的位置關(guān)系所構(gòu)成的集合記為Rpos,則有：

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

(4)

稱Rpos中的每一個(gè)元素為一個(gè)基本Rpos關(guān)系.

定理1.關(guān)系集合Rpos是完備互斥的.

證明. 對(duì)于二維平面中任意2個(gè)有向點(diǎn)A,B,若二者坐標(biāo)不同，則Proj(A)與射線B必定滿足3種可能的位置關(guān)系(Proj(A)=B,|AProj(A)|<|AB|且Proj(A)∈B,|AProj(A)|<|AB|且Proj(A)B)中的一種，由上述定義2～4可知，對(duì)應(yīng)的B與CAB之間必定滿足3種關(guān)系q,g,l中的一種；若A,B坐標(biāo)相同，則由定義5可知對(duì)應(yīng)的B與CAB之間滿足關(guān)系t.因此任意2個(gè)有向點(diǎn)A,B之間必定滿足一種基本Rpos關(guān)系且僅滿足一種，即關(guān)系集合Rpos是完備互斥的.

證畢.

為了更加全面準(zhǔn)確地描述任意2個(gè)有向點(diǎn)A,B之間的空間信息，不僅要明確B與CAB之間的位置關(guān)系，還要明確A與CBA之間的位置關(guān)系.

定義7.Rpos-pair為Rpos上的一個(gè)有序二元關(guān)系，定義為

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中每一個(gè)元素為一個(gè)基本Rpos-pair關(guān)系.

利用Rpos-pair可描述有向點(diǎn)間的相對(duì)位置關(guān)系.對(duì)于任意2個(gè)有向點(diǎn)A,B,二者滿足一種基本Rpos-pair關(guān)系，其語(yǔ)義如表1所示：

Table 1 The Semantic of Basic Rpos-pair Relations表1 基本Rpos-pair關(guān)系語(yǔ)義表

推論1.關(guān)系集合Rpos-pair是完備互斥的.

證明.Rpos上的二元關(guān)系最多包含16個(gè)元素，由定義5可知對(duì)于任意2個(gè)有向點(diǎn)A,B,若t(B,CAB)則t(A,CBA),即二者不存在6種相對(duì)位置關(guān)系：t,g,t,q,t,l,g,t,q,t,l,t;且定理1已證明集合Rpos是完備互斥的，因此A,B必定滿足Rpos-pair中10個(gè)關(guān)系中的一種且僅一種，即Rpos-pair也是完備互斥的.

證畢.

2.2 Rpos-pair對(duì)定性距離變化的約束

對(duì)于任意2個(gè)有向點(diǎn)A=(PA,φA)與B=(PB,φB),在不同基本Rpos關(guān)系下，φB與φAB之間滿足命題1～3.

命題1.對(duì)于任意2個(gè)有向點(diǎn)A=(PA,φA)與B=(PB,φB),若l(B,CAB),φAB∈[0,2π),則有φB∈(φAB-π2,φAB+π2).

證明. 當(dāng)φAB∈[0,π2)時(shí)，如圖4所示，若l(B,CAB),由定義4可知Proj(A)應(yīng)位于CAB上過(guò)B點(diǎn)切線的下方，基于平面幾何中角度間的關(guān)系易知φ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)時(shí)φB取值示例圖

類似地，若l(B,CAB),分別當(dāng)φAB∈[π2,π),φAB∈[π,3π2),φAB∈[3π2,2π)時(shí)，均有φB∈(φAB-π2,φAB+π2).

證畢.

同理可證命題2與命題3成立.

命題2.對(duì)于任意2個(gè)有向點(diǎn)A=(PA,φA)與B=(PB,φB),若g(B,CAB),φAB∈[0,2π),則有φB∈(φAB+π2,φAB+3π2).

命題3.對(duì)于任意2個(gè)有向點(diǎn)A=(PA,φA)與B=(PB,φB),若q(B,CAB),φAB∈[0,2π),則有φB=φAB+(2k+1)π2,k∈.

不難發(fā)現(xiàn)，有向點(diǎn)A,B的移動(dòng)方向、在各自方向上的移動(dòng)距離、AB與x軸的夾角等因素均影響著二者之間后續(xù)的定性距離變化.下面通過(guò)定理2給出上述因素與定性距離變化之間的關(guān)系.

定理2.任意2個(gè)有向點(diǎn)A=(PA,φA)與B=(PB,φB),分別沿著各自方向移動(dòng)LA,LB后到達(dá)A′=(PA′,φA),B′=(PB′,φB),若PA≠PB且A與CBA以及B與CAB之間不存在相切關(guān)系，當(dāng)LA=LB=0時(shí)|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分別為一微小時(shí)間間隔內(nèi)LA,LB的增量.

證明. 由2點(diǎn)間距離公式可知:

(7)

構(gòu)造二元函數(shù)

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 有向點(diǎn)A,B相關(guān)坐標(biāo)、夾角、移動(dòng)距離示例圖

因此有:

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)

函數(shù)f(LA,LB)描述了有向點(diǎn)A,B沿著各自方向移動(dòng)的距離(分別為L(zhǎng)A,LB)與A,B移動(dòng)后二者間距離(即|A′B′|)之間的關(guān)系.對(duì)f(LA,LB)求一階偏導(dǎo)數(shù)有:

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,此時(shí)無(wú)論φA,φB,LA與LB如何取值，式(14)中z恒為0.這意味著在微小時(shí)間間隔內(nèi)，z無(wú)法準(zhǔn)確表示有向點(diǎn)A,B間的距離增量.

若PA≠PB且xB=xA,則yB≠yA.當(dāng)q(A,CBA)時(shí),必有φA=k,k∈Z,因此sinφA=0,使得無(wú)論LA如何取值，式(14)中LA系數(shù)恒為0.這意味著無(wú)論有向點(diǎn)A如何移動(dòng)，式(14)中z無(wú)法準(zhǔn)確描述LA對(duì)A,B間距離增量的約束作用.

若PA≠PB且xB≠xA,式(14)可進(jìn)一步整理為

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

(15)

當(dāng)q(A,CBA)時(shí),由命題3可知φA=φBA+(2k+1)π2,k∈Z,由于φBA=φAB+π,因此φAB-φA=-(2k+3)π2,k∈Z,即cos(φAB-φA)=0.根據(jù)三角函數(shù)和差公式可知cosφABcosφA+sinφABsinφA=0,即cosφA=-tanφABsinφA,使得無(wú)論LA如何取值，式(15)中LA系數(shù)恒為0,即式(15)中z無(wú)法準(zhǔn)確描述LA對(duì)A,B間距離增量的約束作用.同理，q(B,CAB)時(shí)情況類似.

證畢.

本文將利用定理2研究任意2個(gè)有向點(diǎn)在不同基本Rpos-pair關(guān)系下的定性距離變化.

推論2.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Ag,gB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將不變或變小.

證明. 設(shè)A,B分別沿著各自當(dāng)前方向移動(dòng)了LA,LB到達(dá)A′,B′,經(jīng)過(guò)某一微小時(shí)間間隔后到達(dá)A″,B″,期間LA,LB的增量分別為L(zhǎng)A≥0與LB≥0.已知Ag,gB,當(dāng)LA=LB=0時(shí)基于定理2中式(6)對(duì)LA,LB分情況討論：

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

綜上所述，若Ag,gB,在一微小時(shí)間間隔內(nèi)A,B沿著當(dāng)前方向移動(dòng)，若至少一方移動(dòng)的距離不為0，則二者之間距離將變?。蝗舳咭苿?dòng)距離均為0，則二者之間距離將不變.

證畢.

推論3.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Al,lB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將不變或變大.

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

綜上所述，若Al,lB,在一微小時(shí)間間隔內(nèi)A,B沿著當(dāng)前方向移動(dòng)，若至少一方移動(dòng)的距離不為0,則二者之間距離將變大；若二者移動(dòng)距離均為0,則二者之間距離將不變.

證畢.

在Rpos描述的位置關(guān)系中，相切作為相割、相離之間的鄰接關(guān)系，其情況比較特殊.對(duì)于有向點(diǎn)A,B,若A與CBA或B與CAB之間存在相切關(guān)系，那么二者移動(dòng)過(guò)程中的距離變化更加復(fù)雜，無(wú)法完全適用定理2,一些情況需要單獨(dú)討論.

推論4.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Ag,qB或Aq,gB,則在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離變化不確定.

證明. 當(dāng)Ag,qB時(shí)，設(shè)A,B分別沿著各自當(dāng)前方向移動(dòng)了LA,LB到達(dá)A′,B′,經(jīng)過(guò)某一微小時(shí)間間隔后到達(dá)A″,B″,期間LA,LB的增量分別為L(zhǎng)A≥0與LB≥0.對(duì)LA,LB分情況討論：

1) 與定理2中式(14)之前的證明部分相同，已知Ag,qB,因此有PA≠PB,g(B,CAB).若limLA=0,limLB≠0,此時(shí)與推論2中的情況1證明相同，可知二者之間距離將變小.

2) 已知q(A,CBA),在證明定理2時(shí)已說(shuō)明，此時(shí)cos(φAB-φA)=0,使得式(14)中LA的系數(shù)恒為0,無(wú)法用式(14)討論距離變化.當(dāng)PA≠PB,LA=LB=0時(shí)，可知B′=B,A′=A,|A′B′|=|AB|;當(dāng)limLB=0,limLA≠0時(shí)，可知B″與B′近似相等，如圖8所示，因此有|A″B″|≈|A″B′|.根據(jù)致直角三角形斜邊大于直角邊可知|A″B″|>|A′B′|,進(jìn)而有|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在微小時(shí)間間隔內(nèi)A,B分別沿著各自當(dāng)前方向移動(dòng)距離的不同情況可能導(dǎo)致二者之間的距離變小、變大或者是不變，因此無(wú)法確定二者之間的距離變化.

同理可證，當(dāng)Aq,gB時(shí)，A,B之間距離變化不確定.

證畢.

類似地，基于定理2可證明推論5～7成立.

推論5.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Ag,lB或Al,gB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離變化不確定.

推論6.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Al,qB或Aq,lB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將不變或變大.

推論7.對(duì)于任意2個(gè)有向點(diǎn)A,B,若Aq,qB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將不變或變大.

特殊地，當(dāng)2個(gè)有向點(diǎn)對(duì)應(yīng)的射線與圓存在同置關(guān)系時(shí)，二者之間的距離變化如定理3所述.

定理3.對(duì)于任意2個(gè)有向點(diǎn)A,B,若At,tB,在A,B分別沿著各自當(dāng)前方向移動(dòng)某一微小時(shí)間間隔后，二者之間距離將不變或變大.

證明. 當(dāng)有向點(diǎn)A,B對(duì)應(yīng)的射線與圓存在同置關(guān)系時(shí)，根據(jù)定義5有PA=PB,如圖3(d)所示，若二者的移動(dòng)方向與速度均相同，則二者之間距離保持不變；若二者移動(dòng)方向或速度不同，則二者之間距離必將變大.

證畢.

在證明定理2、定理3以及推論2～7的過(guò)程中，將微小時(shí)間間隔內(nèi)有向點(diǎn)的靜止?fàn)顟B(tài)視為移動(dòng)過(guò)程中的一種特殊狀態(tài)，因此本文面向移動(dòng)對(duì)象提出的理論模型同樣適用于靜止對(duì)象間、靜止對(duì)象與移動(dòng)對(duì)象間的方向與距離關(guān)系結(jié)合推理.

2.3 Rpos-pair與OPRA4的對(duì)應(yīng)關(guān)系

首先通過(guò)命題4～7研究基本Rpos關(guān)系與OPRA4方向關(guān)系之間的對(duì)應(yīng)關(guān)系；然后給出基本Rpos-pair關(guān)系與OPRA4方向關(guān)系之間的對(duì)應(yīng)關(guān)系.

證明. 由命題1可知，對(duì)任意2個(gè)有向點(diǎn)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的證明過(guò)程類似，可證命題5與命題6成立.

命題7.對(duì)于任意2個(gè)有向點(diǎn)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可知，若有向點(diǎn)A,B對(duì)應(yīng)的射線與圓之間存在同置關(guān)系，則有PA=PB,進(jìn)而由定義1可知A4∠kB,其中k∈{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

證畢.

通過(guò)上述命題4～7可歸納出基本Rpos關(guān)系與OPRA4方向關(guān)系之間的對(duì)應(yīng)表，如表2所示；在此基礎(chǔ)上，通過(guò)組合方式可進(jìn)一步得到基本Rpos-pair關(guān)系與OPRA4方向關(guān)系之間的對(duì)應(yīng)關(guān)系，如表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方向關(guān)系對(duì)應(yīng)表

2.4 OPRA4對(duì)定性距離變化的約束

對(duì)于任意2個(gè)有向點(diǎn)A,B,本文2.2節(jié)給出了A,B間基本Rpos-pair關(guān)系對(duì)二者間定性距離變化的約束作用；2.3節(jié)明確了A,B間基本Rpos-pair關(guān)系與二者間OPRA4方向關(guān)系的對(duì)應(yīng)關(guān)系.因此借助于基本Rpos-pair關(guān)系可以建立起OPRA4方向關(guān)系與定性距離變化的內(nèi)在聯(lián)系，如表4所示.

表4相當(dāng)于給出了OPRA4方向關(guān)系全集的一個(gè)劃分：

(16)

Table 4 Corresponding Table of OPRA4 Direction Relations and Qualitative Distance Changes表4 OPRA4方向關(guān)系與定性距離變化對(duì)應(yīng)表

對(duì)于任意2個(gè)有向點(diǎn)A,B,二者滿足的基本OPRA4方向關(guān)系必定屬于該劃分中的某個(gè)子集且僅屬于一個(gè)子集.因此，當(dāng)已知A,B之間的基本OPRA4方向關(guān)系時(shí)，可以參照表4對(duì)二者之間定性距離變化進(jìn)行相應(yīng)的判斷.

3 基于OPRA4推理定性距離變化算法與實(shí)例

為方便形式化表示與說(shuō)明，將二維平面中2個(gè)有向點(diǎn)間的4種定性距離變化“變大”、“變小”、“不變”、“不確定”分別用further,nearer,unchange,uncertain表示，構(gòu)成的集合記為Udis,則有：

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

(17)

下面給出算法1是OPRA4-Distance的偽代碼對(duì)于任意2個(gè)有向點(diǎn)，當(dāng)已知二者當(dāng)前基本OPRA4方向關(guān)系時(shí)，用該算法對(duì)微小時(shí)間間隔內(nèi)二者基于Udis的定性距離變化進(jìn)行推斷.

算法1.OPRA4-Distance.

輸出：有向點(diǎn)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.對(duì)于任意2個(gè)有向點(diǎn)A,B,若已知二者間的基本OPRA4方向關(guān)系,算法OPRA4-Distance能夠正確推斷出后續(xù)微小時(shí)間間隔內(nèi)二者間基于Udis的定性距離變化.

證明. 設(shè)有向點(diǎn)A,B滿足基本OPRA4方向關(guān)系R.

證畢.

以智能交通中的“連續(xù)k近鄰查詢”問(wèn)題為例介紹本文理論模型的具體應(yīng)用.

例1.如圖9所示，時(shí)刻ti與tj路網(wǎng)中有A,B1,B2,B3,B4,B5,B6共7個(gè)移動(dòng)對(duì)象，以A作為查詢對(duì)象，連續(xù)查詢距離A最近的2個(gè)移動(dòng)對(duì)象.路網(wǎng)中移動(dòng)對(duì)象與道路邊交點(diǎn)間的數(shù)值表示距離，tj=ti+t,t為某一微小時(shí)間間隔.

Fig. 9 An example of moving objects in a road network from time tito tj圖9 路網(wǎng)中移動(dòng)對(duì)象距離變化示例

針對(duì)例1，首先將連續(xù)k近鄰查詢轉(zhuǎn)換為以t為周期的周期式查詢.下面通過(guò)算法OPRA4-Distance-Candidate給出基于OPRA4和定性距離變化篩選移動(dòng)對(duì)象候選集的方法，其中q為查詢對(duì)象，R為基本OPRA4方向關(guān)系，Dis∈2Udis為定性距離變化集，Candidate為當(dāng)前查詢過(guò)程中確定的初始移動(dòng)對(duì)象候選集，ResultKNN為上一次查詢結(jié)果，CandidateKNN為當(dāng)前查詢過(guò)程中基于OPRA4和定性距離變化篩選后的移動(dòng)對(duì)象候選集.

算法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.

在智能交通領(lǐng)域中，不同的連續(xù)k近鄰查詢方法在路網(wǎng)與移動(dòng)對(duì)象的建模、索引結(jié)構(gòu)設(shè)計(jì)、地圖匹配策略、對(duì)象間距離的計(jì)算、路段與移動(dòng)對(duì)象候選集的確定等環(huán)節(jié)采用了不同的方法.算法2主要針對(duì)移動(dòng)對(duì)象候選集的確定環(huán)節(jié).在例1中，為方便說(shuō)明，設(shè)時(shí)刻ti查詢確定的CandidateKNN={B1,B2,B3,B4,B5,B6},計(jì)算B1～B6各點(diǎn)到A的路網(wǎng)距離后排序，可知時(shí)刻ti查詢結(jié)果ResultKNN={B1,B2},如圖9(a)所示.經(jīng)過(guò)t后到達(dá)時(shí)刻tj，首先確定時(shí)刻tj查詢的Candidate(不同連續(xù)k近鄰查詢方法中確定移動(dòng)對(duì)象候選集的方式不盡相同，此處不做詳細(xì)討論)，為方便說(shuō)明，設(shè)Candidate={B1,B2,B3,B4,B5,B6}.由圖9(b)和語(yǔ)句①②可知在時(shí)刻tj,Candidate中各移動(dòng)對(duì)象與A之間分別滿足如下基本OPRA4方向關(guān)系：此時(shí)基于語(yǔ)句③可知，B2,B3與A的距離將不變或變?。籅1,B5,B6與A的距離不變或變大；B4與A的距離變化不確定.由于路網(wǎng)中兩點(diǎn)間的歐氏距離小于等于路網(wǎng)距離，因此經(jīng)由語(yǔ)句④⑤篩選后可確定Candidate={B2,B3,B4}.由于以微小時(shí)間間隔為查詢周期，因此上一次的查詢結(jié)果很可能與本次查詢結(jié)果存在交集，應(yīng)將時(shí)刻ti的查詢結(jié)果納入候選集，進(jìn)而由語(yǔ)句⑧可知CandidateKNN={B1,B2,B3,B4}.經(jīng)過(guò)上述篩選過(guò)程，無(wú)需再考慮路網(wǎng)中所有移動(dòng)對(duì)象，僅需計(jì)算CandidateKNN中的4個(gè)移動(dòng)對(duì)象到A的路網(wǎng)距離并排序，得到時(shí)刻tj的查詢結(jié)果ResultKNN={B2,B3},如圖9(b)所示.由此可見，本文提出的推理方法可作為確定移動(dòng)對(duì)象候選集的一項(xiàng)重要依據(jù)，能夠有效地過(guò)濾掉連續(xù)k近鄰查詢過(guò)程中的部分不合格移動(dòng)對(duì)象，從而減少距離計(jì)算與排序的代價(jià).

例1和算法OPRA4-Distance-Candidate僅給出利用本文理論模型優(yōu)化連續(xù)k近鄰查詢問(wèn)題的簡(jiǎn)單示意.由于采用OPRA4模型表示方向關(guān)系，因此與QTC,QRPC中采用的十字方向關(guān)系模相比，本文提出的理論模型對(duì)空間方向信息的描述粒度更精細(xì)、基于方向關(guān)系對(duì)定性距離變化的推理粒度更精細(xì)，更有助于處理復(fù)雜交通網(wǎng)絡(luò)中的問(wèn)題.然而在實(shí)際應(yīng)用中通常還需要綜合考慮時(shí)間、速度、查詢對(duì)象的范圍、路網(wǎng)拓?fù)浣Y(jié)構(gòu)、交通規(guī)則約束等多方面因素對(duì)移動(dòng)對(duì)象進(jìn)行篩選，進(jìn)而得到規(guī)模更小、更準(zhǔn)確的候選集合.

4 結(jié)論與展望

面向移動(dòng)空間對(duì)象，針對(duì)OPRA4方向關(guān)系與定性距離變化的結(jié)合推理問(wèn)題，本文首先通過(guò)定義射線與圓之間的Rpos關(guān)系描述目標(biāo)對(duì)象相對(duì)于參照對(duì)象的移動(dòng)方向；然后通過(guò)組合方式定義了Rpos-pair關(guān)系，用以描述2個(gè)移動(dòng)對(duì)象間的相對(duì)Rpos關(guān)系；分別研究并證明了基本Rpos-pair關(guān)系對(duì)定性距離變化的約束作用、基本Rpos-pair關(guān)系與OPRA4方向關(guān)系之間的對(duì)應(yīng)關(guān)系，進(jìn)而借助于基本Rpos-pair關(guān)系建立起OPRA4方向關(guān)系與定性距離變化之間的內(nèi)在聯(lián)系.在此基礎(chǔ)上提出一種基于基本OPRA4方向關(guān)系推理定性距離變化的方法，并證明了方法的正確性.最后以智能交通中的“連續(xù)k近鄰查詢”問(wèn)題為例，進(jìn)一步說(shuō)明了本文理論模型的正確性與有效性.

速度是移動(dòng)對(duì)象的一種固有屬性，對(duì)各種空間關(guān)系(尤其是距離關(guān)系)有著重要的約束作用.如何在現(xiàn)有模型的基礎(chǔ)上進(jìn)一步結(jié)合速度等時(shí)空屬性，是本文有待于深入研究的一個(gè)方面.概念鄰域能夠處理空間關(guān)系的連續(xù)變化問(wèn)題，是進(jìn)行時(shí)空推理的重要工具.然而基于OPRA4方向關(guān)系的概念鄰域研究較少，這方面工作將有助于深化OPRA4方向關(guān)系與其他空間關(guān)系的結(jié)合推理研究，更加全面準(zhǔn)確地對(duì)時(shí)空信息進(jìn)行表示與推理.