摘 要：

為了彌補(bǔ)現(xiàn)有的二維空間對(duì)象方向關(guān)系表達(dá)模型大都利用點(diǎn)、最小外包矩形等近似地代替空間對(duì)象，距離真實(shí)空間對(duì)象間方向關(guān)系的描述與推理仍存在差距的不足，提出了一種基于Voronoi圖的非連通空間對(duì)象方向關(guān)系表達(dá)模型。該模型借助Gestalt心理學(xué)理論，通過(guò)提取非連通空間對(duì)象的特征點(diǎn)、特征鏈，構(gòu)建空間對(duì)象間的可視區(qū)域，生成方向關(guān)系Voronoi圖，實(shí)現(xiàn)了非連通、含洞的參考對(duì)象與目標(biāo)對(duì)象間方向關(guān)系的表達(dá)，該模型較好地顧及了空間對(duì)象形狀、大小等因素帶來(lái)的影響，表達(dá)精度更高、適用范圍更廣。為了提高復(fù)雜空間對(duì)象方向關(guān)系復(fù)合推理的精度，基于該模型提出了一個(gè)非連通對(duì)象間主方向關(guān)系復(fù)合推理算法，該算法借助Tile-union運(yùn)算和Pr運(yùn)算，實(shí)現(xiàn)了該模型下基本主方向關(guān)系的復(fù)合推理，降低推理結(jié)果的不確定性。分析和驗(yàn)證的結(jié)果表明，提出的非連通空間對(duì)象方向關(guān)系模型及復(fù)合推理算法，提高了表達(dá)與推理的精度，完善和提高了對(duì)復(fù)雜空間對(duì)象方位關(guān)系的分析與處理能力。

關(guān)鍵詞：Voronoi圖；Gestalt心理學(xué)理論；非連通空間對(duì)象；主方向關(guān)系；復(fù)合推理

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）09-013-2655-09

doi：10.19734/j.issn.1001-3695.2024.01.0005

Description and reasoning with direction relation of disconnected spatial objects

Wang Miao1， Dong Xingxing2， Gao Jixun1， 2， Fang Zhenxi3， Tang Hao3， Li Song4

（1.Dept. of Computer Science， Henan University of Engineering， Zhengzhou 451191， China; 2.Dept. of Computer Science， Henan Polytechnic University， Jiaozuo Henan 454000， China; 3.Dept. of Computer Science， Zhongyuan University of Technology， Zhengzhou 451191， China; 4.Dept. of Computer Science， Harbin University of Science & Technology， Harbin 150080， China）

Abstract：

In view of the fact that there is still a certain gap in representing and reasoning with the orientation relation between real objects due that the existing models for representing and reasoning with direction relations use a point and minimum bounding rectangle to approximate the spatial object itself， this paper proposed a new model for dealing with the disconnected spatial objects based on Voronoi diagram. With the help of the theory of Gestalt psychological， the proposed model constructed visual regions between spatial objects by extracting the feature points and feature chains of the disconnected spatial objects to generate the direction Voronoi diagram， which realized the representation of directions between the space objects which were disconnected and contain holes. This model fully considered the influence of the shape， size and other factors of the spatial objects， and had higher expression accuracy and wider applicability. In order to improve the precision of reasoning with cardinal directional relations between complex spatial objects， it proposed an algorithm for composing cardinal direction relations defined by the proposed model， which reduced the uncertainty of the results of composition by means of Tile-union operation and Pr operation. The results of analysis and verification show that the proposed model and algorithm reduce the uncertainty of the reasoning results， improve the accuracy of representation and reasoning， and then enhance the ability to analyze and process the direction relations with complex spatial objects.

Key words：Voronoi diagram; theory of Gestalt psychological; disconnected spatial objects; cardinal directional relations; composition

0 引言

空間方向關(guān)系是空間關(guān)系的重要組成部分，反映了空間物體間的序關(guān)系，例如前側(cè)、后側(cè)、左側(cè)、右側(cè)等，廣泛應(yīng)用于空間智能分析處理、城市管網(wǎng)配置、機(jī)器人導(dǎo)航、防災(zāi)減災(zāi)等諸多領(lǐng)域，日益成為數(shù)據(jù)建模、制圖綜合、多媒體設(shè)計(jì)、圖像檢索等領(lǐng)域研究的熱點(diǎn)和難點(diǎn)問(wèn)題［1，2］。

空間方向關(guān)系的表達(dá)與推理是空間方向關(guān)系研究領(lǐng)域的核心內(nèi)容，對(duì)于空間數(shù)據(jù)庫(kù)領(lǐng)域中的空間檢索、空間定位、空間存儲(chǔ)等都是非常重要的［3，4］?？臻g方向關(guān)系形式化描述作為空間方向關(guān)系領(lǐng)域中的一個(gè)基礎(chǔ)性內(nèi)容，為空間方向關(guān)系的具體應(yīng)用奠定了基礎(chǔ)［5］。目前空間方向關(guān)系的研究大多集中在空間方向關(guān)系表達(dá)與推理模型和基于模型的推理工作［6，7］，例如空間方向關(guān)系的復(fù)合推理、反關(guān)系推理、一致性檢驗(yàn)等。

目前，已有一些二維空間區(qū)域?qū)ο蠓较蜿P(guān)系表達(dá)與推理模型被提出，其中代表性的模型包括錐形模型［8］、基于MBR的方向關(guān)系模型［9］、方向關(guān)系矩陣模型［10］、基于Voronoi圖的方向關(guān)系模型［11］等。其中，錐形模型將空間對(duì)象抽象為點(diǎn)，描述精度不高；基于MBR的方向關(guān)系模型利用空間對(duì)象最小外包矩形間的方向關(guān)系確定空間對(duì)象間的方向關(guān)系，在一定程度上考慮了空間對(duì)象自身大小與形狀帶來(lái)的影響，但未考慮空間對(duì)象相交的情況；方向關(guān)系矩陣模型通過(guò)延伸參考對(duì)象的MBR將整個(gè)空間區(qū)域劃分成九個(gè)部分，該模型僅僅描述了參照對(duì)象外接矩形外部的方向關(guān)系，忽略了空間對(duì)象的內(nèi)部細(xì)節(jié)；基于Voronoi圖的方向關(guān)系模型利用空間對(duì)象的特征點(diǎn)代替空間對(duì)象，考慮了空間對(duì)象的自身特性，但上述經(jīng)典模型均未實(shí)現(xiàn)含洞的、非連通的空間對(duì)象間方向關(guān)系的描述，距離真實(shí)物體間的位置關(guān)系描述仍存在差距［12，13］。近年來(lái)，人們相繼提出了一系列改進(jìn)模型，李朋朋等人［14］在2018年改進(jìn)了Goyal［10］提出的方向關(guān)系相似性計(jì)算模型，使方向關(guān)系矩陣的應(yīng)用范圍更廣，相似性計(jì)算的結(jié)果更準(zhǔn)確，但該模型無(wú)法描述空間目標(biāo)相互纏繞的情形；陳超等人［15］在2021年提出了利用方向Voronoi圖模型描述面狀群組目標(biāo)間的方向關(guān)系，較好地顧及了群組目標(biāo)自身形狀、大小等因素帶來(lái)的影響，但無(wú)法較好地同時(shí)考慮諸多因素帶來(lái)的影響；王玉竹等人［16］在2022年在模糊數(shù)學(xué)思路的基礎(chǔ)上，給出了考慮各參考目標(biāo)形狀和相對(duì)大小的空間方向關(guān)系表達(dá)模型，更符合人們的方位認(rèn)知習(xí)慣，但并未考慮非連通、含洞的空間對(duì)象間的空間方向關(guān)系［17］。綜上，單目標(biāo)空間對(duì)象方向關(guān)系模型大多以規(guī)則的、連通的空間對(duì)象為研究目標(biāo)，針對(duì)含洞、非連通空間對(duì)象的深入研究相對(duì)較少，在一定程度上降低了空間方向關(guān)系模型的適用性，與真實(shí)對(duì)象有一定的差距，當(dāng)前缺乏統(tǒng)一的空間關(guān)系模型描述非連通空間對(duì)象間的空間方向關(guān)系。

目前，已有學(xué)者基于點(diǎn)對(duì)象、線對(duì)象、面對(duì)象等對(duì)空間方向關(guān)系推理問(wèn)題展開(kāi)了深入研究，提出了一些推理方法［18～22］。Skiadopoulos等人［23］在2004年采用自然語(yǔ)言描述方向關(guān)系矩陣模型，給出了部分定義、定理的形式化描述，并指出現(xiàn)實(shí)生活中往往存在非連通的空間對(duì)象，但并未給出具體的描述與推理方法。時(shí)玉等人［24］在2008年提出了基于真實(shí)物體的方向關(guān)系模型，但該模型將空間對(duì)象抽象為最小外包矩形，僅適用于目標(biāo)對(duì)象是連通的情形，無(wú)法體現(xiàn)參考對(duì)象的非連通性，并在該模型的基礎(chǔ)上，給出了基本主方向關(guān)系的復(fù)合推理方法，該方法仍依賴手工推理。為處理復(fù)雜三維空間對(duì)象間的方向關(guān)系，劉永山等人［25］在2011年基于單純形數(shù)據(jù)模型利用投影方法及區(qū)間運(yùn)算簡(jiǎn)單的特性，提出三維空間物體方向關(guān)系的坐標(biāo)映射模型，給出了一個(gè)該模型下主方向關(guān)系網(wǎng)絡(luò)一致性檢驗(yàn)算法。為了避免復(fù)雜的手工推理，Wang等人［26］在2022年提出了方向關(guān)矩陣模型下基本主方向關(guān)系的反關(guān)系推理算法，該算法充分發(fā)揮了矩陣運(yùn)算的優(yōu)勢(shì)，實(shí)現(xiàn)了二維基本主方向關(guān)系反關(guān)系的自動(dòng)計(jì)算與推理。綜上，已有的空間方向關(guān)系表達(dá)與推理方法大多針對(duì)連通區(qū)域間的基本主方向關(guān)系展開(kāi)研究，然而現(xiàn)實(shí)生活中空間對(duì)象往往以非連通的形式存在，現(xiàn)有的空間方向關(guān)系研究工作大多針對(duì)規(guī)則的空間對(duì)象，對(duì)非連通空間對(duì)象間方向關(guān)系的表達(dá)與推理的研究甚少。

為此，本文建立了基于Voronoi圖的非連通空間對(duì)象方向關(guān)系模型。稱之為VG-irregular模型，該模型借助Gestalt心理學(xué)理論，將距離相近、特征相似的空間對(duì)象的各部分代替整個(gè)空間對(duì)象，提取特征信息、形成可視區(qū)域，構(gòu)建基于Voronoi圖的非連通空間對(duì)象方向關(guān)系模型，該模型較好地反映了真實(shí)空間對(duì)象間的方向關(guān)系，適用于描述非連通、含洞的空間對(duì)象間的方位關(guān)系，與已有模型相比，該模型描述精度更高，研究對(duì)象更加貼合實(shí)際。為了進(jìn)一步提高空間方向關(guān)系的推理精度，基于該模型給出了一個(gè)復(fù)合推理算法，該算法實(shí)現(xiàn)了非連通對(duì)象主方向關(guān)系的復(fù)合推理。推理結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例，降低了復(fù)合結(jié)果的不確定性，理論分析與對(duì)比驗(yàn)證的結(jié)果表明，該復(fù)合推理方法是正確的、完備的。

1 基礎(chǔ)知識(shí)

Goyal［10］提出的方向關(guān)系矩陣模型是描述二維區(qū)域空間對(duì)象間的方向關(guān)系，適用于規(guī)則的、連通的以及有連通邊界的的封閉單位圓與區(qū)域?qū)ο?。該模型利用參考區(qū)域?qū)ο蟮淖钚⊥獍匦螌⒖臻g劃分成九個(gè)方向區(qū)域，如圖1所示，通過(guò)判斷主對(duì)象與各方向區(qū)域的交疊情況構(gòu)造一個(gè)方向關(guān)系矩陣來(lái)定義與描述空間對(duì)象間的方向關(guān)系。方向關(guān)系矩陣分為粗略和精確方向關(guān)系矩陣，粗略方向關(guān)系矩陣的元素值是0或1，記錄源目標(biāo)與參考目標(biāo)的各方向區(qū)域是否相交，如式（1）所示；精確方向關(guān)系矩陣的元素值是源目標(biāo)與各方向區(qū)域的交疊面積百分比，如式（2）所示。

真實(shí)物體包括同胚的、連通的空間對(duì)象和含洞的、不連通的空間對(duì)象，這些區(qū)域?qū)ο蟮募嫌洖镽EG*，例如，圖2中源目標(biāo)對(duì)象或參考對(duì)象是非連通的空間對(duì)象，非連通空間對(duì)象具有靈活性、多變性、復(fù)雜性等特點(diǎn)，若利用方向關(guān)系矩陣模型描述其方向關(guān)系，可得圖2（a）中目標(biāo)對(duì)象b與參考對(duì)象a的方向關(guān)系是b E：B a，圖2（b）中目標(biāo)對(duì)象b與參考對(duì)象a的方向關(guān)系是b E a，而實(shí)際所感知的圖2（a）的方向關(guān)系是b E：SE：N：NE a，實(shí)際所感知的圖2（b）的方向關(guān)系是b E：NE a，可見(jiàn)方向關(guān)系矩陣模型的描述結(jié)果將與真實(shí)情況存在較大偏差、精度較低，無(wú)法準(zhǔn)確描述非連通空間對(duì)象間的方向關(guān)系。

2 基于Voronoi圖的非連通空間對(duì)象方向關(guān)系表達(dá)模型

現(xiàn)有的方向關(guān)系模型大多利用點(diǎn)、最小外包矩形等近似地代替空間對(duì)象，未考慮非連通空間對(duì)象的自身特征，本文提出了一種基于Voronoi圖的非連通空間對(duì)象方向關(guān)系表達(dá)模型，用于解決含洞的、非連通的空間對(duì)象的建模問(wèn)題。非連通空間對(duì)象間的方向關(guān)系是一個(gè)整體相對(duì)于另一個(gè)整體的方向關(guān)系，該模型利用非連通空間對(duì)象特征鏈間的方向關(guān)系來(lái)描述整體空間對(duì)象間的方向關(guān)系。其主要思想是借助Gestalt心理學(xué)理論，將距離相近、特征相似的空間對(duì)象的各部分代替整個(gè)空間對(duì)象，提取空間對(duì)象具有代表性的特征點(diǎn)、形成特征鏈、構(gòu)建空間對(duì)象間的可視區(qū)域、生成方向關(guān)系Voronoi圖、計(jì)算Voronoi圖各線段的方位角，得到非連通空間對(duì)象方向關(guān)系模型，其中，特征鏈在空間方向關(guān)系判斷的過(guò)程中代表著其對(duì)應(yīng)的整個(gè)空間對(duì)象。

定義12 空間對(duì)象特征點(diǎn)是指能夠表示空間對(duì)象基本結(jié)構(gòu)的點(diǎn)。點(diǎn)目標(biāo)對(duì)象的特征點(diǎn)是點(diǎn)；線目標(biāo)對(duì)象的特征點(diǎn)是起點(diǎn)、中點(diǎn)、終點(diǎn)；面目標(biāo)對(duì)象的特征點(diǎn)是其多邊形可視區(qū)域的頂點(diǎn)。若空間對(duì)象有m、n個(gè)特征點(diǎn)，次序可記為p1，p2，p3，…，pm、q1，q2，q3，…，qn。

定義13 空間對(duì)象特征鏈?zhǔn)怯蓛蓚€(gè)空間對(duì)象間相鄰近的一側(cè)的特征點(diǎn)自然而然連接成的曲線，特征鏈代替空間對(duì)象本身，空間對(duì)象a的特征鏈記為Ca。

定義14 可視區(qū)域是兩個(gè)空間對(duì)象的特征鏈鄰近的兩端連接形成的區(qū)域，可視區(qū)域可看作是三角形的集合，即每個(gè)三角形必須包含兩個(gè)目標(biāo)對(duì)象的特征點(diǎn)。大多數(shù)情況下，可視區(qū)域整體是多邊形，特殊情況下是一條線段，空間對(duì)象a、b可視區(qū)域記為Fab。

構(gòu)造基于Voronoi圖的非連通空間對(duì)象方向關(guān)系表達(dá)模型需要經(jīng)歷以下四個(gè)階段：

a）提取特征點(diǎn)，針對(duì)空間對(duì)象間相鄰的一側(cè)，利用格雷厄姆算法求解特征鏈，夾角序列算法計(jì)算特征鏈直徑，借助偏角衡量空間對(duì)象綜合的幅度。若空間對(duì)象特征鏈邊界上的特征點(diǎn)的偏角小于45°，則舍棄該特征點(diǎn)，保留其余特征點(diǎn)，利用提取的全部特征點(diǎn)代替空間對(duì)象本身，并且應(yīng)保證提取空間對(duì)象特征點(diǎn)前后的空間關(guān)系保持不變。

b）連接特征點(diǎn)形成特征鏈，構(gòu)造空間對(duì)象間的可視區(qū)域，根據(jù)Gestalt心理學(xué)將空間對(duì)象間相鄰近的一側(cè)的特征點(diǎn)自然而然連接成曲線，即代替空間對(duì)象本身的特征鏈。然后將兩條特征鏈?zhǔn)资走B接、尾尾連接形成由多個(gè)三角形構(gòu)成的多邊形可視區(qū)域，其中每個(gè)三角形的三個(gè)頂點(diǎn)中必須既有非連通參考對(duì)象的特征點(diǎn)，又有非連通源目標(biāo)對(duì)象的特征點(diǎn)。

c）生成Voronoi圖，在空間對(duì)象間的多邊形可視區(qū)域的基礎(chǔ)上，依據(jù)各個(gè)三角形底角的度數(shù)范圍不同，將三角形分為三種，即底角都是銳角、一個(gè)底角是直角、一個(gè)底角是鈍角。方向關(guān)系Voronoi圖的連接點(diǎn)由第一、二種三角形腰的中點(diǎn)、第三種三角形一腰中點(diǎn)的垂線和另一腰的中位線、兩相鄰目標(biāo)公共邊界的起訖點(diǎn)和共點(diǎn)相鄰時(shí)的公共點(diǎn)組成，將連接點(diǎn)依次連接得到方向關(guān)系Voronoi圖。

d）計(jì)算Voronoi圖各線段所對(duì)應(yīng)射線的方位角，將方位角信息轉(zhuǎn)換為空間對(duì)象間的方向關(guān)系。計(jì)算射線方位角之前需要計(jì)算源目標(biāo)對(duì)象與參考對(duì)象的方向關(guān)系Voronoi圖的方位角。若源目標(biāo)對(duì)象在參考對(duì)象的上、右、右上、左上，則求解Voronoi圖各線段的方位角時(shí)，以線段的左端點(diǎn)、上端點(diǎn)、左上端點(diǎn)、左下端點(diǎn)為基點(diǎn)，計(jì)算各線段對(duì)應(yīng)的方位角。若源目標(biāo)對(duì)象在參考對(duì)象的下、左、左下、右下，則求解Voronoi圖各線段的方位角時(shí)，以線段的右端點(diǎn)、下端點(diǎn)、右下端點(diǎn)、右上端點(diǎn)為基點(diǎn)，計(jì)算各線段對(duì)應(yīng)的方位角。

射線方位角是指垂直于Voronoi圖各線段、由參考對(duì)象指向源目標(biāo)對(duì)象的射線的方位角，得到Voronoi圖各線段所對(duì)應(yīng)的射線方位角信息后，將射線方位角信息與空間方向關(guān)系對(duì)應(yīng)起來(lái)。計(jì)算射線方位角方法如下，假設(shè)方向關(guān)系Voronoi圖的線段是EF，E點(diǎn)記為（x1，y1），F(xiàn)點(diǎn)記為（x2，y2），E、F兩點(diǎn)的方位角記為βEF，其對(duì)應(yīng)射線方位角β的計(jì)算分為兩種情況。若x1≠x2，則當(dāng)β≥0時(shí)β=βEF-90°、當(dāng)β＜0時(shí)，β=βEF-90°+360°；若x1=x2，源目標(biāo)在參考目標(biāo)的右側(cè)，則β=90°，反之，β=270°。

每個(gè)空間方向關(guān)系對(duì)應(yīng)一個(gè)射線方位角的劃分區(qū)間，利用八方向描述方法將射線的方位角與空間方向關(guān)系對(duì)應(yīng)起來(lái)，北 （337.5°，22.5°］、東北（22.5°，67.5°］、東 （67.5°，112.5°］、東南 （112.5°，157.5°］、南 （157.5°，202.5°］、西南（202.5°，247.5°］、西 （247.5°，292.5°］、西北 （292.5°，337.5°］，由此可得空間對(duì)象間的方向關(guān)系，該模型同樣適用于參考對(duì)象和源目標(biāo)對(duì)象均為非連通空間對(duì)象的情況。

例如，利用上述模型描述如圖4所示的非連通空間對(duì)象a與含洞空間對(duì)象b之間的方向關(guān)系，需提取空間對(duì)象a、b的特征點(diǎn)記作p1，p2，p3，p4，q1，q2，q3，q4；依次連接特征點(diǎn)形成空間對(duì)象a、b的特征鏈記作Ca=p1p2p3p4、Cb= q1q2q3q4；將特征鏈?zhǔn)孜岔槾芜B接形成空間對(duì)象a、b的可視區(qū)域記作Fab= p1p2p3p4q1q2q3q4p1；將兩條特征鏈?zhǔn)资走B接、尾尾連接形成由多個(gè)三角形構(gòu)成的多邊形可視區(qū)域，其中三角形包括Δp1q1p2、Δp2q1q2、Δp2q2p3、Δp3q2p3、Δp3q3p4、Δp4q3p4；構(gòu)造空間對(duì)象a與空間對(duì)象b之間的方向關(guān)系Voronoi圖是D1D2，由線段1、2、3、4、5和6組成。

按照上述計(jì)算Voronoi圖各線段所對(duì)應(yīng)射線方位角的方法，分別計(jì)算出各線段所對(duì)應(yīng)的方位角、方向關(guān)系、線段長(zhǎng)度以及長(zhǎng)度百分比，如表1所示，經(jīng)計(jì)算可得非連通源目標(biāo)對(duì)象a的67.4%在參考對(duì)象b的西北方向，32.6%在參考對(duì)象b的西南方向。

綜上所述，利用本文提出的VG-irregular模型描述非連通空間對(duì)象間的方向關(guān)系時(shí)大致經(jīng)歷四個(gè)過(guò)程，即：a）提取非連通空間對(duì)象特征點(diǎn)；b）借助Gestalt心理學(xué)理論，將距離相近、特征相似的空間對(duì)象特征點(diǎn)連接形成特征鏈，通過(guò)特征鏈構(gòu)造可視區(qū)域；c）在上述過(guò)程的基礎(chǔ)上生成方向關(guān)系Voronoi圖；d）計(jì)算Voronoi圖中各線段的方位角，并利用射線方位角信息與空間方向關(guān)系的對(duì)應(yīng)關(guān)系得到非連通空間對(duì)象間的方向關(guān)系。

下面將通過(guò)一個(gè)具體的實(shí)例說(shuō)明VG-irregular模型的表示方法及過(guò)程，如圖5所示。

a）利用非連通目標(biāo)對(duì)象a1、a2和非連通參考對(duì)象b1、b2特征鏈邊界上的特征點(diǎn)的偏角信息，提取非連通空間對(duì)象a、b的特征點(diǎn)，即特征點(diǎn)A、B、C、D、E、F、G、H、I、J。

b）連接空間對(duì)象a1、a2、b1、b2特征點(diǎn)，構(gòu)建空間對(duì)象a、b的特征鏈，即特征鏈ABCD、EFGHIJ。然后將特征鏈ABCD和特征鏈EFGHIJ首首連接、尾尾連接形成由多個(gè)三角形構(gòu)成的多邊形可視區(qū)域，即可視區(qū)域ABCDEFGHIJA。其中三角形包括△AIJ、△ABI、△BHI、△BCH、△CHG、△CDG、△DEF。

c）判斷各三角形的類型（銳角三角形、直角三角形、鈍角三角形），連接各三角形的中點(diǎn)或者垂點(diǎn)?！鰽IJ是鈍角三角形，則取AI的中點(diǎn)作垂線得到線段MK，同理可得，線段1、2、3、4、5、6、7、8。將空間對(duì)象a、b的起訖點(diǎn)M、N和8條線段依次連接得到空間對(duì)象a、b的方向關(guān)系Voronoi圖，即折線MN。

d）計(jì)算8條線段的方位角，根據(jù)方位角與空間方向關(guān)系對(duì)應(yīng)得到每條線段對(duì)應(yīng)的方向關(guān)系，例如線段1：45°—90°＋360°＝315°，對(duì)應(yīng)西北方向，其余同理，并計(jì)算出各線段所線段長(zhǎng)度和長(zhǎng)度百分比，具體如表2所示。

經(jīng)計(jì)算可得圖5中的非連通源目標(biāo)對(duì)象a的81.25%在參考對(duì)象b的西北方向，6.25%在參考對(duì)象b的西方向，12.5%在參考對(duì)象b的西南方向?？梢?jiàn)VG-irregular模型較好地反映了真實(shí)空間對(duì)象間的方向關(guān)系，適用于描述非連通、含洞的空間對(duì)象間的方位關(guān)系，該模型描述精度更高，研究對(duì)象更加貼合實(shí)際。

3 非連通空間對(duì)象間主方向關(guān)系的復(fù)合推理

為了復(fù)合推理的精度，降低復(fù)合推理結(jié)果的不確定性，在VG-irregular方向關(guān)系模型的基礎(chǔ)上，對(duì)空間方向關(guān)系的推理進(jìn)行研究，提出了一個(gè)非連通對(duì)象間主方向關(guān)系復(fù)合推理算法。根據(jù)本文模型所得空間對(duì)象間含比例大小的方向關(guān)系，將其轉(zhuǎn)換為方位角形式，用θ表示；具體的劃分方法是北：θ1=（337.5°，22.5°］、東北：θ2=（22.5°，67.5°］、東：θ3=（67.5°，112.5°］、東南：θ4=（112.5°，157.5°］、南：θ5=（157.5°，202.5°］、西南：θ6=（202.5°，247.5°］、西：θ7=（247.5°，292.5°］、西北：θ8=（292.5°，337.5°］。基于Skiadopoulos和Koubarakis提出的原子主方向關(guān)系合成表進(jìn)行改進(jìn)，得到如表3所示的以“方位角”形式展示的原子主方向關(guān)系復(fù)合表。

若存在空間對(duì)象a，b，c∈REG*，滿足a θ1 b、b θ2 c，則θ1θ2∈2D*。將利用如式（8）所示的矩陣描述，元素值是0或1，僅僅記錄源目標(biāo)對(duì)象與參考對(duì)象的方向關(guān)系，若源目標(biāo)對(duì)象a在參考對(duì)象b的西北方向和西南方向，所對(duì)應(yīng)的矩陣如式（9）所示。

Dir（a，b）=

NW（292.5°，337.5°］N（337.5°，22.5°］NE（22.5°，67.5°］

W（247.5°，292.5°］θ0E（67.5°，112.5°］

SW（202.5°，247.5°］S（157.5，202.5°］SE（112.5°，157.5°］（8）

Dir（a，b）=100000100（9）

定義15 若θ1，…，θk是原子主方向關(guān)系，Pr（θ1：…：θk）表示各原子主方向關(guān)系θ1、…、θk百分制下所占比例的計(jì)算，計(jì)算結(jié)果滿足θ1比例＋：…：＋θk比例=1。

例如：θ4（70%）：θ5（40%），則Pr（θ4（70%）：θ5（40%））=θ4（70%/（70%+40%））：θ5（40%/（70%+40%））=θ4（63.64%）：θ5（36.36%）。

引理1［18］ 若θ1是原子主方向關(guān)系，θ2是主方向關(guān)系，則滿足θ1θ2=θ1Most（θ1，Br（θ2））。

定理1 若θ1、θ2是主方向關(guān)系，θ1=θ11：…：θ1k，θ2=θ21：…：θ2m，θ11，…，θ1k是原子主方向關(guān)系，則滿足θ1kθ2=Pr（θ1kMost（θ1k，Br（θ2）））。

證明 已知k=1，即θ1=θ11，θ1是原子主方向關(guān)系，θ2、θ3是主方向關(guān)系，若a θ1（100%） b，b θ21（x%）：θ22（1-x%）c，根據(jù)引理1可知，存在θ3∈{θ1θ21：θ22}，根據(jù)定義15可知，對(duì)于任意復(fù)合結(jié)果θ31（m%）：θ32（n%），存在θ31（m%）：θ32（n%）=θ31（m%/（m%+n%））：θ32（n%/（m%+n%），故命題成立。證畢。

引理2［18］ 若θ1、θ2是基本主方向關(guān)系，θ1=θ11：…：θ1k，θ2=θ21：…：θ2m，則滿足θ1θ2 ={ Q∈D： （s1，…， sk）（Q=Tile-union（s1，…， sk）∧s1∈θ11θ2∧…∧sk∈θ1kθ2）}。

定理2 若θ1、θ2是主方向關(guān)系，θ1=θ11：…：θ1k，θ2=θ21：…：θ2m，則滿足θ1θ2 =Pr（Tile-union（s1，…，sk︱s1∈θ11θ2，…， sk∈θ1kθ2））。

證明 假設(shè)k=1，則θ1=θ11，θ1是原子主方向關(guān)系， 其結(jié)論顯然成立；假設(shè)k>1，令Q∈θ1θ2，則根據(jù)定義6，存在物體a、b、c∈REG*，滿足a θ1 b∧b θ2 c∧a Q c。已知a θ1 b成立，則存在物體 a1，…，ak∈REG*，a=a1∪…∪ak，使a1θ11b∧…∧ak θ1k b成立，故（a1θ11b∧…∧ak θ1k b）∧b θ2 c∧a Q c。既然a=a1∪…∪ak與a Q c成立，則存在主方向關(guān)系Q1，…，Qk，使得Q=Tile-union（Q1，…，Qk），a1 Q1 c∧…∧ak Qk c成立，故（a1θ11b∧…∧ak θ1k b）∧b θ2 c∧（a1 Q1 c∧…∧ak Qk c）。類似地，（a1 θ11 b∧b θ2 c∧a1 Q1 c）∧…∧ （akθ1k b∧b θ2 c∧ak Qk c）成立，因此Q1∈θ11θ2，…， Qk∈θ1kθ2，即Q=Tile-union （Q1，…， Qk） 成立，根據(jù)定理1可知，θ1θ2 =Pr（Tile-union （Q1，…， Qk））成立，故命題成立。證畢。

對(duì)于任意兩個(gè)主方向關(guān)系的復(fù)合，首先根據(jù)引理1和定理1計(jì)算出一個(gè)主方向關(guān)系中各原子主方向關(guān)系與另一個(gè)主方向關(guān)系的復(fù)合，利用引理2和定理2對(duì)上述復(fù)合結(jié)果進(jìn)行Tile-union運(yùn)算和Pr運(yùn)算，該復(fù)合結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例。基于上述方法，給出了一個(gè)非連通對(duì)象間主方向關(guān)系復(fù)合推理算法COM_PR（），該復(fù)合算法如下。

算法 COM_PR（θ）

輸入：兩個(gè)基本主方向關(guān)系θ1∈D*、θ2∈D*，其中θ1=θ11：…：θ1k，θ2=θ21：…：θ2k，θ11，…，θ2k是原子主方向關(guān)系。

輸出：θ1與θ2的合成結(jié)果θ3。

begin //計(jì)算Sij

ElemType S，S1i; //定義S、S1i變量

for int i：=1 to k do

for int j：=1 to k do //依次計(jì)算θ1i與θ2的復(fù)合關(guān)系

S=θ1iθ2; //依據(jù)定理1即可實(shí)現(xiàn)

S1i：=S1i∪S; //依次合并得到初步的復(fù)合結(jié)果

//對(duì)S1i中的元素進(jìn)行Tile-union運(yùn)算

ElemType S0; //定義S0變量

if （S！=NULL） then //對(duì)S進(jìn)行判空操作

S0=S11; /*將臨時(shí)變量的值，賦給S0，以便S0與下一個(gè)集合運(yùn)算*/

for int i：=1 to k-1 do

S0=Tile-union（S0，S1i+1）∪S0; //依據(jù)定理2即可實(shí)現(xiàn)

//對(duì)θ3k中的方向關(guān)系進(jìn)行比例運(yùn)算

if（S！=NULL） then //對(duì)S進(jìn)行判空操作

for int i：=1 to S0.length do

θ3=θ3∪{Pr（S0i）}; //依次對(duì)θ3中的方向關(guān)系進(jìn)行Pr運(yùn)算

return θ3;

end

定理3 主方向關(guān)系復(fù)合算法COM_PR（）是正確的、完備的。

證明 若θ1∈D*、θ2∈D*，則存在θ3∈D*。定理1給出了θ1i與θ2的復(fù)合關(guān)系Sij∈θ1iθ2j（1≤i≤k，1≤j≤k，1≤i≤length（Si），1≤j≤length（Sj）），其正確性在相應(yīng)的定理中給出了證明。定理2實(shí)現(xiàn)了Tile-union運(yùn)算和Pr運(yùn)算，即S1和S2中的元素依次進(jìn)行Tile-union運(yùn)算，其結(jié)果放入S0中，運(yùn)算結(jié)束后將S0值賦給S2，然后對(duì)S2和S3進(jìn)行Tile-union運(yùn)算，依此類推，直到完成對(duì)Sk-1和Sk中各元素的Tile-union運(yùn)算，最后對(duì)θ31，…，θ3k進(jìn)行比例運(yùn)算，運(yùn)算結(jié)束后賦值給θ3將得到θ1和θ2的復(fù)合關(guān)系θ3，其正確性和完備性在上述定理中均已證明。故算法COM_PR（）是正確的、完備的。證畢。

綜上所述，本文提出的非連通對(duì)象間主方向關(guān)系復(fù)合推理算法COM_PR（）大致經(jīng)歷三個(gè)過(guò)程，即：a）利用引理1、定理1實(shí)現(xiàn)原子主方向關(guān)系與主方向關(guān)系的復(fù)合；b）利用引理2、定理2對(duì)上述初步復(fù)合結(jié)果依次進(jìn)行Tile-union運(yùn)算；c）完成Pr運(yùn)算，實(shí)現(xiàn)任意兩個(gè)主方向關(guān)系的復(fù)合，并且復(fù)合結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例。

下面將通過(guò)一個(gè)具體的實(shí)例說(shuō)明非連通對(duì)象間主方向關(guān)系復(fù)合推理算法的表示方法及過(guò)程。已知a NW（30%）：SW（70%） b、b W（40%）：S（60%） c，計(jì)算a與c間的方向關(guān)系。

a）計(jì)算各原子主方向關(guān)系與非連通主方向關(guān)系的復(fù)合。將NW（30%）：SW（70%）W（40%）：S（60%）轉(zhuǎn)換為方位角形式的空間方向關(guān)系，即（292.5°， 337.5°］（30%）：（202.5°， 247.5°］（70%）（247.5°， 292.5°］（40%）：（157.5°， 202.5°］（60%），然后計(jì)算（292.5°， 337.5°］（247.5°， 292.5°］：（157.5°，202.5°］、（202.5°， 247.5°］（247.5°， 292.5°］：（157.5°， 202.5°］的合成結(jié)果，得到S1={（292.5°， 337.5°］，（247.5°， 292.5°］，（292.5°， 337.5°］：（247.5°，292.5°］}、S2={（202.5°，247.5°］}。

b）完成Tile-union運(yùn)算。針對(duì)S1={（292.5°，337.5°］，（247.5°，292.5°］，（292.5°，337.5°］：（247.5°，292.5°］}、S2={（202.5°，247.5°］} 依次進(jìn)行Tile-union運(yùn)算。Tile-union（S1，S2）={ （202.5°， 247.5°］：（292.5°， 337.5°］，（202.5°，247.5°］：（247.5°， 292.5°］，（202.5°， 247.5°］：（292.5°， 337.5°］： （247.5°， 292.5°］}。

c）完成Pr運(yùn)算。針對(duì){（202.5°，247.5°］：（292.5°，337.5°］，（202.5°，247.5°］：（247.5°，292.5°］，（202.5°，247.5°］：（292.5°，337.5°］： （247.5°，292.5°］}進(jìn)行Pr運(yùn)算。根據(jù)原子主方向關(guān)系的比例關(guān)系進(jìn)行基本主方向關(guān)系的比例運(yùn)算，已知空間方向關(guān)系（202.5°，247.5°］占比70%、（292.5°，337.5°］占比30%、（247.5°，292.5°］占比40%、（157.5°，202.5°］占比60%， （202.5°，247.5°］：（292.5°，337.5°］的比例關(guān)系是（202.5°，247.5°］（70%）：（292.5°，337.5°］（30%），其余同理。可得（202.5°，247.5°］ （70%）：（292.5°，337.5°］ （30%）（202.5°，247.5°］ （63.64%）：（247.5°，292.5°］ （36.36%）、（202.5°，247.5°］ （50%）：（292.5°，337.5°］ （21.43%）：（247.5°，292.5°］ （28.57%）。

將角度形式的空間方向關(guān)系轉(zhuǎn)換為SW（70%）：NW（30%）、SW（63.64%）：W（36.36%）、SW（50%）：NW（21.43%）：W（28.57%）。因此，NW（30%）：SW（70%）與W（40%）：S（60%）復(fù)合的結(jié)果包括SW（70%）：NW（30%）、SW（63.64%）：W（36.36%）、SW（50%）：NW（21.43%）：W（28.57%） 三種情況，其中SW（70%）：NW（30%）表示空間對(duì)象a的70%的部分位于空間對(duì)象c的西南方向、空間對(duì)象a的30%的部分位于空間對(duì)象c的西北方向，另外兩種結(jié)果的含義同樣如此。

4 分析驗(yàn)證

4.1 VG-irregular模型的實(shí)例分析與對(duì)比

4.1.1 表達(dá)精度分析驗(yàn)證

描述如圖6（a）所示的非連通空間對(duì)象間的方向關(guān)系時(shí)，利用方向關(guān)系矩陣模型得到的空間方向關(guān)系是非連通源目標(biāo)對(duì)象a在非連通參考對(duì)象b的西、西北方向，如圖6（b）所示。若利用VG-irregular方向關(guān)系模型描述非連通空間對(duì)象間的方向關(guān)系，通過(guò)提取空間對(duì)象特征點(diǎn)、形成特征鏈、構(gòu)造可視區(qū)域、生成Voronoi圖等過(guò)程，得到非連通源目標(biāo)對(duì)象a與非連通參考對(duì)象b之間的方向關(guān)系，如圖6（c）所示，即非連通源目標(biāo)對(duì)象a的3.17%在非連通參考對(duì)象b的西北方向，a的55.56%在b的正西方向，a的41.27%在b的西南方向，具體計(jì)算過(guò)程如表4所示。由此可見(jiàn)，VG-irregular模型精度更高，給出了具體的百分比，更加符合現(xiàn)實(shí)生活中人們對(duì)于方向關(guān)系的認(rèn)識(shí)習(xí)慣。

4.1.2 空間對(duì)象自身特性影響程度分析

描述如圖7（a）所示的非連通參考對(duì)象與連通源目標(biāo)對(duì)象間的方向關(guān)系時(shí)，方向關(guān)系矩陣模型將非連通參考對(duì)象看作一個(gè)整體，可得連通源目標(biāo)對(duì)象b在非連通參考對(duì)象a的正西方向，如圖7（b）所示，未體現(xiàn)參考對(duì)象的非連通特性。若利用本文VG-irregular方向關(guān)系模型描述非連通參考對(duì)象與連通源目標(biāo)對(duì)象間方向關(guān)系，如圖7（c）所示，以點(diǎn)G1為基點(diǎn)，可得源目標(biāo)對(duì)象b的64.7%在非連通參考對(duì)象a的東南方向，b的23.91%在a的東面，b的11.39%在a的東北方向，具體計(jì)算過(guò)程如表5所示。從現(xiàn)實(shí)角度分析，僅說(shuō)明空間對(duì)象b在空間對(duì)象a的正西方向是不正確的，方向關(guān)系矩陣模型的描述結(jié)果誤差較大，而本文VG-irregular方向關(guān)系模型的描述結(jié)果考慮了空間對(duì)象a的非連通性，受空間對(duì)象自身特性影響較小。

4.1.3 外在因素影響程度分析

除了上述空間對(duì)象自身特性包括形狀、大小等因素會(huì)影響空間對(duì)象間的方向關(guān)系，空間對(duì)象間的空間距離、簡(jiǎn)單拓?fù)潢P(guān)系、分布密度、分布范圍等因素也將影響空間方向關(guān)系的描述。方向關(guān)系矩陣模型利用參考對(duì)象的最小外包矩形代替空間對(duì)象本身，將空間劃分成九個(gè)方向區(qū)域，忽略了空間距離、簡(jiǎn)單拓?fù)潢P(guān)系、分布密度、分布范圍等外在因素帶來(lái)的影響。本文提出的VG-irregular方向關(guān)系模型利用方向關(guān)系Voronoi圖從定性與定量?jī)蓚€(gè)角度對(duì)非連通空間對(duì)象間的空間方向關(guān)系進(jìn)行描述與計(jì)算，既顧及了空間對(duì)象的大小、形狀和距離等因素的影響，又可以獲得較為精確的計(jì)算結(jié)果，適用于多種情況下空間方向關(guān)系的描述，在廣泛性、正確性、唯一性、普遍性方面均有優(yōu)勢(shì)。

綜上，無(wú)論是描述準(zhǔn)確性、受空間對(duì)象自身特性影響程度，還是外在因素影響程度，VG-irregular方向關(guān)系模型具有明顯優(yōu)勢(shì)，描述精度更高，適用范圍更廣，考慮了空間對(duì)象形狀、大小等因素帶來(lái)的影響，受空間對(duì)象自身特性影響程度較小，所得空間方向關(guān)系描述結(jié)果更符合現(xiàn)實(shí)生活中人們的認(rèn)知習(xí)慣，較好地反映了真實(shí)空間對(duì)象的形狀與空間對(duì)象間的方向關(guān)系。

4.2 復(fù)合算法的實(shí)例分析與對(duì)比

利用C語(yǔ)言編程實(shí)現(xiàn)了算法COM_PR（），在Visual Studio 2019平臺(tái)上運(yùn)行，程序?qū)崿F(xiàn)的基本思路利用引理1、定理1實(shí)現(xiàn)原子主方向關(guān)系與主方向關(guān)系的復(fù)合，利用引理2、定理2對(duì)上述初步復(fù)合結(jié)果依次進(jìn)行Tile-union運(yùn)算和Pr運(yùn)算，實(shí)現(xiàn)任意兩個(gè)主方向關(guān)系的復(fù)合，復(fù)合結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例。在本節(jié)中，將利用兩個(gè)實(shí)例對(duì)算法COM_PR（）進(jìn)行分析驗(yàn)證。通過(guò)第一個(gè)實(shí)例分析驗(yàn)證算法對(duì)于非連通主方向關(guān)系復(fù)合的計(jì)算與推理能力，并且與手工推理的結(jié)果進(jìn)行對(duì)比；通過(guò)第二個(gè)實(shí)例分析驗(yàn)證算法復(fù)合結(jié)果的精度，并將其復(fù)合結(jié)果與具有代表性的Skiadopoulos等人［23］提出的經(jīng)典推理方法和當(dāng)前較新的歐陽(yáng)繼紅等人［18］提出的主方向關(guān)系復(fù)合推理方法進(jìn)行對(duì)比分析驗(yàn)證。

下面通過(guò)第3章中的實(shí)例驗(yàn)證算法COM_PR（）的正確性，即 NW（30%）：SW（70%）W（40%）：S（60%），將空間方向關(guān)系轉(zhuǎn)換為方位角形式的空間方向關(guān)系，即（292.5°， 337.5°］（30%）：（202.5°，247.5°］（70%）（247.5°，292.5°］（40%）：（157.5°， 202.5°］（60%），利用算法中的前兩個(gè)for循環(huán)計(jì)算（292.5°， 337.5°］（247.5°，292.5°］：（157.5°，202.5°］、（202.5°，247.5°］（247.5°， 292.5°］：（157.5°， 202.5°］，得到S1={（292.5°， 337.5°］，（247.5°， 292.5°］，（292.5°， 337.5°］： （247.5°，292.5°］}、S2={（202.5°，247.5°］}。該過(guò)程的實(shí)現(xiàn)對(duì)應(yīng)復(fù)合算法COM_PR（）第一部分的for循環(huán)，其中引理1與定理1的正確性已證明完畢。

利用第三個(gè)for循環(huán)可得Tile-union（S1，S2）={ （202.5°，247.5°］：（292.5°，337.5°］，（202.5°，247.5°］：（247.5°，292.5°］，（202.5°，247.5°］：（292.5°，337.5°］： （247.5°，292.5°］}。該過(guò)程的實(shí)現(xiàn)對(duì)應(yīng)復(fù)合算法COM_PR（）第二部分的for循環(huán)，其中引理2的正確性已證明完畢。

利用第四個(gè)for循環(huán)可得復(fù)合結(jié)果（202.5°，247.5°］：（292.5°，337.5°］的比例關(guān)系是（202.5°，247.5°］（70%）：（292.5°，337.5°］（30%），其余同理。該過(guò)程的實(shí)現(xiàn)對(duì)應(yīng)復(fù)合算法COM_PR（）第三部分的for循環(huán)，且定理2的正確性已證明完畢。最后將角度形式的空間方向關(guān)系轉(zhuǎn)換為SW（70%）：NW（30%）、SW（63.64%）：W（36.36%）、SW（50%）：NW（21.43%）：W（28.57%）。因此，NW（30%）：SW（70%）與W（40%）：S（60%）復(fù)合的結(jié)果包括SW（70%）：NW（30%）、SW（63.64%）：W（36.36%）、SW（50%）：NW（21.43%）：W（28.57%）三種情況。為驗(yàn)證該推理結(jié)果的正確性，進(jìn)行手工推理，其手工推理的所有可能的空間布局如圖8所示，可得算法COM_PR（）的推理結(jié)果與實(shí)際情形一致。

為了進(jìn)一步驗(yàn)證COM_PR（）算法的正確性和完備性，通過(guò)第二個(gè)實(shí)例將COM_PR（）算法的推理結(jié)果與文獻(xiàn)［18，23］的方法的推理結(jié)果進(jìn)行對(duì)比分析。例如，源目標(biāo)對(duì)象a與參考對(duì)象b、c的空間方向關(guān)系是a W（100%） b、b W（40%）：SW（60%） c。

在文獻(xiàn)［23］中提出的復(fù)合推理方法采用自然語(yǔ)言描述方向關(guān)系矩陣模型，僅對(duì)部分定義、定理進(jìn)行形式化描述，給出了復(fù)合思想框架，計(jì)算218種基本主方向關(guān)系，針對(duì)W（100%）W（40%）：SW（60%），通過(guò)預(yù)處理Br運(yùn)算和Most運(yùn)算，得到復(fù)合結(jié)果是{SW，W，SW：W}，如圖9所示。

在文獻(xiàn)［18］中提出了一種改進(jìn)的二維基本主方向關(guān)系復(fù)合推理方法，形式化描述文獻(xiàn)［23］的復(fù)合思想，并對(duì)其進(jìn)行細(xì)化，簡(jiǎn)化了Most運(yùn)算，降低了復(fù)合的復(fù)雜性，針對(duì)W（100%）W（40%）：SW（60%），依次轉(zhuǎn)換為方向關(guān)系矩陣復(fù)合，得到復(fù)合結(jié)果仍是{SW，W，SW：W}，如圖9所示。

COM_PR（）算法利用方位角描述空間方向關(guān)系，在傳統(tǒng)復(fù)合推理算法的基礎(chǔ)上增加了Tile-union運(yùn)算和Pr運(yùn)算，得到復(fù)合結(jié)果是a SW（100%） c、a W（100%） c、a W（40%）：SW（60%） c。a SW（100%） c表示源目標(biāo)對(duì)象a在參考對(duì)象c的西南面，如圖9所示的空間對(duì)象a1、b、c的方向關(guān)系；a W（40%）：SW（60%） c表示最大范圍內(nèi)源目標(biāo)對(duì)象a的40%在參考對(duì)象c的西面、60%在參考對(duì)象c的西南面，如圖9所示的a21、a22、a23、…、a2n與參考對(duì)象c的方向關(guān)系；a W（100%） c表示源目標(biāo)對(duì)象a在參考對(duì)象c的西面，如圖10所示的空間對(duì)象a2、b、c的方向關(guān)系。綜上，經(jīng)上述三個(gè)復(fù)合推理方法的對(duì)比分析，可得本文的推理結(jié)果精度更高，推理結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例。

通過(guò)上述兩個(gè)實(shí)例驗(yàn)證了COM_PR（）算法的正確性和完備性，COM_PR（）算法在傳統(tǒng)復(fù)合推理算法的基礎(chǔ)上增加Tile-union運(yùn)算和Pr運(yùn)算，使得推理結(jié)果具有明顯優(yōu)勢(shì)，實(shí)現(xiàn)了非連通主方向關(guān)系的復(fù)合，提高了推理的精度，降低了復(fù)合結(jié)果的不確定性，該算法可以廣泛應(yīng)用于空間數(shù)據(jù)中的空間查詢領(lǐng)域。

5 結(jié)束語(yǔ)

本文提出了一種基于Voronoi圖的非連通空間對(duì)象方向關(guān)系表達(dá)模型，即VG-irregular方向關(guān)系模型，該模型較好地表達(dá)了區(qū)域空間對(duì)象間的方向關(guān)系，借助Gestalt心理學(xué)理論，經(jīng)提取非連通空間對(duì)象的特征點(diǎn)、特征鏈，構(gòu)建空間對(duì)象間的可視區(qū)域，生成方向關(guān)系Voronoi圖，從而實(shí)現(xiàn)了非連通、含洞的空間對(duì)象間方向關(guān)系的精準(zhǔn)描述，更加貼近真實(shí)的空間對(duì)象，并給出了該模型下非連通對(duì)象間主方向關(guān)系復(fù)合推理算法，該復(fù)合方法實(shí)現(xiàn)了非連通主方向關(guān)系間的復(fù)合，推理結(jié)果給出了主方向關(guān)系中各原子主方向關(guān)系所占比例，提高了復(fù)合推理的精度。

未來(lái)將圍繞以下問(wèn)題開(kāi)展研究：

a）在本文提出的VG-irregular方向關(guān)系模型、二維主方向關(guān)系復(fù)合推理算法的基礎(chǔ)上，結(jié)合現(xiàn)有的反關(guān)系推理、一致性檢驗(yàn)等工作，將本文提出的Pr運(yùn)算運(yùn)用在二維主方向關(guān)系的反關(guān)系推理和一致性檢驗(yàn)中，提高推理精度，實(shí)現(xiàn)二維主方向關(guān)系的反關(guān)系推理、一致性檢驗(yàn)等問(wèn)題的自動(dòng)計(jì)算、推理和分析。

b）在本文研究的基礎(chǔ)上，確立有效融合方向關(guān)系、距離關(guān)系和拓?fù)潢P(guān)系的方法?，F(xiàn)有的結(jié)合方向關(guān)系、距離關(guān)系和拓?fù)潢P(guān)系的空間方位關(guān)系模型還無(wú)法真正實(shí)現(xiàn)三者的統(tǒng)一描述，實(shí)際上仍然使用各自相互獨(dú)立的描述方法，缺乏統(tǒng)一的表達(dá)模型是影響表達(dá)和推理精度的主要障礙。

參考文獻(xiàn)：

［1］郝忠孝. 時(shí)空數(shù)據(jù)庫(kù)查詢與推理 ［M］. 北京： 科學(xué)出版社，2010： 326-362. （Hao Zhongxiao. Query and reasoning of spatiotemporal database ［M］. Beijing： Science Press，2010： 326-362.）

［2］王淼，王曉桐，李松，等. 二維基本矩形主方向關(guān)系的原關(guān)系推理 ［J］. 西安交通大學(xué)學(xué)報(bào)，2020，54（4）： 133-143. （Wang Miao，Wang Xiaotong，Li Song，et al. The original relation reasoning of the principal direction relation of a two-dimensional basic rectangle ［J］. Journal of Xi’an Jiaotong University，2020，54（4）： 133-143.）

［3］董星星，高繼勛，王曉桐，等. 空間方向關(guān)系表達(dá)與推理模型研究綜述 ［J］. 計(jì)算機(jī)工程，2023，49（9）： 1-15. （Dong Xingxing，Gao Jixun，Wang Xiaotong，et al. A review of research on spatial directional relationship expression and inference models ［J］. Computer Engineering，2023，49（9）： 1-15.）

［4］王淼，方振西，王曉桐，等. 空間方向關(guān)系定性推理技術(shù)研究進(jìn)展 ［J］. 計(jì)算機(jī)應(yīng)用研究，2023，40（9）： 2561-2572. （Wang Miao，F(xiàn)ang Zhenxi，Wang Xiaotong，et al. Research progress on qualitative reasoning techniques for spatial direction relations ［J］. Computer Application Research，2023，40（9）： 2561-2572.）

［5］Gao Jixun，Li Mengmeng，Wang Miao，et al. A comprehensive model incorporating multiple spatial relations in 3D space ［J］. Recent Advances in Computer Science and Communications，2023，16（8）： 65-77.

［6］Wang Miao，Li Mengmeng，F(xiàn)ang Zhenxi，et al. Block algebra-based consistency checking with cardinal direction relations in 3D space ［J］. IEEE Access，2023，11： 130010-130021.

［7］Lark R M，Chagumaira C，Milne A E. Decisions，uncertainty and spatial information ［J］. Spatial Statistics，2022，50（18）：100619.

［8］Haar R. Computational models of spatialrelationa ［R］. College Park，MD： University of Maryland，1976.

［9］Papadias D，Sellis T. Qualitative representation of spatial knowledge in two dimensional space［J］. VLDB Journal，1994，3（4）： 479-516.

［10］Goyal R. Similarity assessment for cardinal directions between exten-ded spatial objects ［D］. Maine： The University of Maine，2000.

［11］閆浩文，郭仁忠. 基于Voronoi 圖的空間方向關(guān)系形式化描述 ［J］. 武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2003，28（4）： 468-471. （Yan Haowen，Guo Renzhong. Formal description of spatialorientation relationship based on Voronoi diagram ［J］. Journal of Wuhan University：Information Science Edition，2003，28（4）： 468-471.）

［12］王淼，郝忠孝. 采用定性坐標(biāo)的位置表達(dá)及主方向關(guān)系推理 ［J］. 西安交通大學(xué)學(xué)報(bào)，2010，44（8）： 36-41. （Wang Miao，Hao Zhongxiao. Position expression and principal direction relational reasoning using qualitative coordinates ［J］. Journal of Xi’an Jiaotong University，2010，44（8）： 36-41.）

［13］郝曉紅，李松，郝忠孝. 復(fù)雜3D空間中的3DR46模型的表示與推理 ［J］. 計(jì)算機(jī)科學(xué)與探索，2020，14（12）： 2004-2013. （Hao Xiaohong，Li Song，Hao Zhongxiao. Representation and re-asoning of 3DR46 model in complex 3D space ［J］. Computer Science and Exploration，2020，14（12）： 2004-2013.）

［14］李朋朋，劉紀(jì)平，閆浩文，等. 基于方向關(guān)系矩陣的空間方向相似性計(jì)算改進(jìn)模型 ［J］. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2018，35（2）： 215-220. （Li Pengpeng，Liu Jiping，Yan Haowen，et al. An improved model for calculating spatial orientation similarity based onorientation relation matrix ［J］. Journal of Surveying and Mapping Science and Technology，2018，35（2）： 215-220.）

［15］陳超，王中輝，馬品. 面狀群 （組） 目標(biāo)空間方向關(guān)系的形式化描述與計(jì)算 ［J］. 測(cè)繪與空間地理信息，2021，44（9）： 17-21. （Chen Chao，Wang Zhonghui，Ma Pin. Formal description andcalculation of the spatial orientation relationship of surface group （group） targets ［J］. Surveying and Mapping and Spatial Geographic Information，2021，44（9）： 17-21.）

［16］王玉竹，閆浩文. 一種改進(jìn)的群組目標(biāo)空間方向關(guān)系計(jì)算模型 ［J］. 測(cè)繪科學(xué)，2022，47（4）： 169-174. （Wang Yuzhu，Yan Haowen. An improved model for calculating the spatial direction relationship of group targets ［J］. Surveying and Mapping Science，2022，47（4）： 169-174.）

［17］江坤，王中輝. 錐形模型的面群方向關(guān)系相似性度量方法 ［J］. 測(cè)繪科學(xué)，2022，47（6）： 174-180. （Jiang Kun，Wang Zhonghui. Similarity measurement method for surface group direction relationship of conical models ［J］. Surveying and Mapping Science，2022，47（6）： 174-180.）

［18］歐陽(yáng)繼紅，孫偉，劉大有，等. 方向關(guān)系矩陣的復(fù)合 ［J］. 吉林大學(xué)學(xué)報(bào)：工學(xué)版，2010，40（4）： 1048-1053. （Ouyang Jihong，Sun Wei，Liu Dayou，et al. Composition of direction relationship matrix ［J］. Journal of Jilin University：Engineering Edition，2010，40（4）： 1048-1053.）

［19］顧衛(wèi)杰，劉永山. 雙投影矩陣模型的方向關(guān)系組合推理研究 ［J］. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2014，31（5）： 538-542. （Gu Weijie，Liu Yongshan. Research on direction relationship combination reasoning of double projection matrix model ［J］. Journal of Surveying and Mapping Science and Technology，2014，31（5）： 538-542.）

［20］Wang Miao，Liu Xiaodong，Li Songyang，et al. Composing 3D cardinal direction relations ［J］. Journal of Computational and Theoretical Nanoscience，2016，13（1）： 623-627.

［21］Li Song，Song Shuang，Hao Xiaohong，et al. Directional nearest neighbor query method for specified geographical direction space based on Voronoi diagram ［J］. High Technology Letters，2022，28（2）： 122-133.

［22］王淼，何莉，李松. 基本主方向關(guān)系的反關(guān)系推理 ［J］. 計(jì)算機(jī)應(yīng)用研究，2013，30（1）： 138-141. （Wang Miao，He Li，Li Song. Inverse relationship reasoning of basic principal direction relationships ［J］. Application Research of Computers，2013，30（1）： 138-141.）

［23］Skiadopoulos S，Koubarakis M. Composing cardinal direction relations ［J］. Artificial Intelligence，2004，152（2）： 143-171.

［24］時(shí)玉，劉永山，王寶宗，等. 一種基于真實(shí)物體的主方向關(guān)系的合成算法 ［J］. 計(jì)算機(jī)工程與應(yīng)用，2008，44（5）： 75-78. （Shi Yu，Liu Yongshan，Wang Baozong，et al. A synthesis algorithm based on principal direction relationships of realobjects ［J］. Computer Engineering and Applications，2008，44（5）： 75-78.）

［25］劉永山，成雪琴. 基于坐標(biāo)映射模型的方向關(guān)系一致性檢驗(yàn) ［J］. 計(jì)算機(jī)工程，2011，37（16）：68-71. （Liu Yongshan，Cheng Xueqie. Consistency testing of directional relationships based on coordinate mapping models ［J］. Computer Engineering，2011，37（16）： 68-71.）

［26］Wang Miao，F(xiàn)ang Zhenxi，Liu Weiguang，et al. Computing the inverse of cardinal direction relations between regions ［J］. Journal of Intelligent Systems，2022，31 （1）： 1160-1177.

［27］Bukenberger D R，Buchin K，Botsch M. Constructing L∞ Voronoi diagrams in 2D and 3D ［J］. Computer Graphics Forum，2022，41（5）： 135-147

［28］王中輝，閆浩文. 基于方向Voronoi圖模型的群組目標(biāo)空間方向關(guān)系計(jì)算 ［J］. 武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2013，38（5）： 584-588. （Wang Zhonghui，Yan Haowen. Calculation of group targetspace orientation relationship based on Voronoi pattern model ［J］. Journal of Wuhan University：Information Science Edition，2013，38（5）： 584-588.）

［29］張?jiān)坪?，蘇立晨，董云帆，等. 基于Voronoi圖最近鄰協(xié)商的多機(jī)協(xié)同追捕方法 ［J］. 哈爾濱工程大學(xué)學(xué)報(bào)，2023，44（2）： 284-291. （Zhang Yunhe，Su Lichen，Dong Yunshan，et al. Multi machine collaborative pursuit method based on Voronoi graph nearest neighbor negotiation ［J］. Journal of Harbin Engineering University，2023，4W7mBpgdDTAUUuzVEGgDBtQ==4（2）： 284-291.）

［30］Izmirlioglu Y，Erdem E. Reasoning about cardinal directions between 3-D imensional extended objects using answer set programming ［J］. Theory and Practice of Logic Programming，2020，20（6）： 942-957.

［31］Zong Chen，Wang Pengfei，Yan Dongming，et al. Parallel post-processing of restricted Voronoi diagram on thin sheet models ［J］. Computer-Aided Design，2023，159： 103511.

收稿日期：2024-01-07；修回日期：2024-03-06 基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61802115，62173126）；河南省科技攻關(guān)項(xiàng)目（232102210068，232102210156，232102210085）；河南省高等學(xué)校重點(diǎn)科研項(xiàng)目（23A510018）

作者簡(jiǎn)介：王淼（1981—），男，河南光山人，副教授，博士，CC會(huì)員，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論與應(yīng)用、空間關(guān)系、空間數(shù)據(jù)查詢與推理等（wmscan@tom.com）；董星星（1998—），女，河南濮陽(yáng)人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論與應(yīng)用、空間關(guān)系等；高繼勛（1980—），男，河南鄭州人，教授，碩導(dǎo)，主要研究方向?yàn)閳D像處理、數(shù)據(jù)庫(kù)理論與應(yīng)用等；方振西（1996—），男，河南商丘人，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論與應(yīng)用、空間推理、空間關(guān)系等；唐昊（2000—），男，河南鄭州人，碩士研究生，主要研究方向?yàn)榭臻g推理、空間數(shù)據(jù)庫(kù)理論與應(yīng)用等；李松（1977—），男，江蘇徐州人，教授，博士，主要研究方向?yàn)閿?shù)據(jù)庫(kù)理論與應(yīng)用、數(shù)據(jù)挖掘、數(shù)據(jù)查詢和推理.