陳占龍,葉 文

中國(guó)地質(zhì)大學(xué)(武漢)信息工程學(xué)院，湖北 武漢 430074

空間關(guān)系是指若干地理實(shí)體及實(shí)體間相互作用的關(guān)系，主要包括拓?fù)?、距離、方向關(guān)系及一些其他類型的空間特征。作為空間關(guān)系中重要的組成部分，復(fù)雜對(duì)象間的拓?fù)潢P(guān)系及其描述是地理信息科學(xué)的一個(gè)基礎(chǔ)研究問(wèn)題，對(duì)完善空間關(guān)系理論體系、空間推理、人工智能等具有重要意義[1]。

拓?fù)鋽?shù)據(jù)模型和數(shù)據(jù)結(jié)構(gòu)的出現(xiàn)很大程度上是受到不準(zhǔn)確的幾何計(jì)算結(jié)果和有限的數(shù)字系統(tǒng)的影響，拓?fù)淠Ｐ统霈F(xiàn)的最初動(dòng)機(jī)是人們對(duì)認(rèn)知合理的定性空間模型的需求?，F(xiàn)階段對(duì)空間拓?fù)潢P(guān)系的研究主要集中在線面拓?fù)潢P(guān)系與面面拓?fù)潢P(guān)系。在線面空間關(guān)系方面，文獻(xiàn)[2]基于線面空間關(guān)系提出了元拓?fù)涓拍?，總結(jié)出線面復(fù)合關(guān)系的集成表達(dá)模型；文獻(xiàn)[3]提出了一種基于節(jié)點(diǎn)度的線面細(xì)分拓?fù)潢P(guān)系描述與計(jì)算方法，在定義線/面單元交線并分析其特點(diǎn)的基礎(chǔ)上,引入節(jié)點(diǎn)度來(lái)區(qū)分線/面單元交線細(xì)分類型。在面與面空間關(guān)系方面，區(qū)域連接演算(RCC)[4-5]是空間關(guān)系的一個(gè)重要形式。另一個(gè)相似的形式是Egenhofer[6-9]的9交模型9IM,其使用九交矩陣分析了各種帶洞面之間的拓?fù)潢P(guān)系。Tryfona和Egenhofer在將有多個(gè)面的區(qū)分解為簡(jiǎn)單區(qū)的基礎(chǔ)上來(lái)處理拓?fù)潢P(guān)系；文獻(xiàn)[10]在此研究基礎(chǔ)上增加了兩個(gè)帶洞面目標(biāo)之間的拓?fù)潢P(guān)系；文獻(xiàn)[11]在9交模型9IM的基礎(chǔ)上提出了一種25交模型25IM,根據(jù)點(diǎn)集拓?fù)淅碚撛谂懦环线壿嫷耐負(fù)潢P(guān)系后對(duì)8種基本拓?fù)潢P(guān)系進(jìn)行描述，更詳細(xì)地表達(dá)空間面拓?fù)潢P(guān)系；文獻(xiàn)[12]提出了空間面目標(biāo)間拓?fù)潢P(guān)系區(qū)分的層次表達(dá)方法，針對(duì)空間區(qū)之間的交與差、空間區(qū)邊界間的交與差運(yùn)算以及簡(jiǎn)單面與帶洞面的外部間的交運(yùn)算描述了簡(jiǎn)單面和帶洞面間的23種層次拓?fù)潢P(guān)系；文獻(xiàn)[13]提出了分層方向關(guān)系矩陣模型，將方向關(guān)系分解為外部方向關(guān)系矩陣，MBR外部方向關(guān)系矩陣和目標(biāo)整體方向關(guān)系矩陣3個(gè)層面。

盡管現(xiàn)階段對(duì)拓?fù)潢P(guān)系的研究取得了豐碩成果[14-19]，但現(xiàn)有模型對(duì)復(fù)雜的面實(shí)體邊界間可能發(fā)生的復(fù)雜交互的描述能力仍然不足[20-25]。如帶洞面間或帶洞面與由多個(gè)部分組合成的多區(qū)實(shí)體之間，它們的拓?fù)潢P(guān)系實(shí)際上不一樣，而現(xiàn)有的拓?fù)潢P(guān)系描述模型可能會(huì)得到拓?fù)涞葍r(jià)的結(jié)果。如圖1所示，A、A′是簡(jiǎn)單面，B、B′是帶洞面，而HB、HB′分別是B和B′中的洞?，F(xiàn)有模型對(duì)圖1中的空間關(guān)系進(jìn)行描述，將會(huì)得到兩者空間關(guān)系完全一致的結(jié)論。若從人的空間認(rèn)知角度出發(fā)，其中的差別則很明顯，原因在于(HB,A)的交集與(HB′,A)的不同。故對(duì)于存在著復(fù)雜邊界交互的空間實(shí)體，已有模型對(duì)其拓?fù)潢P(guān)系的描述仍然存在改進(jìn)空間。因此本文顧及復(fù)雜面實(shí)體的拓?fù)湎嘟患?xì)節(jié)，利用元拓?fù)潢P(guān)系組合來(lái)對(duì)復(fù)雜面實(shí)體的拓?fù)潢P(guān)系進(jìn)行精細(xì)化表達(dá)。

圖1 復(fù)雜空間對(duì)象的拓?fù)潢P(guān)系Fig.1 Topological relations of complex spatial object

1 復(fù)雜面實(shí)體及其拓?fù)潢P(guān)系

從應(yīng)用的觀點(diǎn)出發(fā)，空間應(yīng)用處理復(fù)雜的空間實(shí)體更多，而不是當(dāng)前空間數(shù)據(jù)庫(kù)系統(tǒng)、空間查詢語(yǔ)言和GIS中常見(jiàn)的簡(jiǎn)單點(diǎn)、線和面?，F(xiàn)實(shí)中的空間對(duì)象可能有若干組成部分，不同組成部分間可能會(huì)互相重疊，且面中可能有洞。Vasardani提出的帶洞面的定性模型主要由5個(gè)互不相同的部分組成，如圖2所示，B°是B的內(nèi)部；B-1是B所圍繞著的內(nèi)部區(qū)域，同時(shí)也填充了B中的洞；B-0是B的外部區(qū)域；?1B是B的內(nèi)部邊界，分隔B0與B-1；?0B是B的外部邊界，分隔B0與B-0，如圖2所示。

圖2 帶洞面的定性模型Fig.2 Qualitative model of the surface with hole

復(fù)雜空間對(duì)象可通過(guò)復(fù)合空間對(duì)象模型進(jìn)行構(gòu)建，其主要思想是對(duì)簡(jiǎn)單對(duì)象進(jìn)行幾何組合生成，如合并和求差。例如：對(duì)于面A和B，若A和B相離，則(A∪B)構(gòu)成有兩個(gè)子區(qū)的多區(qū)(圖3(a))，在A包含B的限制條件下，結(jié)構(gòu)(A-B)形成一個(gè)帶洞面(圖3(b))，對(duì)于A包含B，而C與A,B相離的情況，結(jié)構(gòu)(A-B)∪C形成有2個(gè)子面的多面，其中一個(gè)子面為帶洞面(圖3(c))，在A包含B，B包含C的條件下，結(jié)構(gòu)(A-B)∪C形成一個(gè)子面落在另一個(gè)子面洞內(nèi)的多面(圖3(d))。

圖3 復(fù)雜空間對(duì)象的構(gòu)成Fig.3 Component of complex spatial object

如圖3中的復(fù)雜空間對(duì)象，雖然可以用Vasardani定性模型等方法對(duì)其進(jìn)行描述，但對(duì)其拓?fù)潢P(guān)系的精細(xì)化表達(dá)仍存在一定不足。例如，圖4(a)和(b)中A和C所形成的復(fù)雜面通過(guò)Vasardani定性模型描述都是(A-B)∪C，但二者的拓?fù)潢P(guān)系有著明顯的不同。

圖4 復(fù)雜面拓?fù)潢P(guān)系Fig.4 Topological relation of complex planar

2 復(fù)雜面實(shí)體的元拓?fù)溥吔缃患枋?/h2>

2.1 線面實(shí)體間拓?fù)潢P(guān)系

實(shí)體(包括直線、曲線等)間的拓?fù)潢P(guān)系可以有多種，實(shí)體間邊界的交點(diǎn)可以有多個(gè)，故線實(shí)體間的拓?fù)潢P(guān)系又可細(xì)分多種。若考慮線元素集合的有序性和基本拓?fù)潢P(guān)系組合的任意性，順序與組合方式不同，拓?fù)潢P(guān)系則不同。線實(shí)體間的拓?fù)潢P(guān)系可以非常簡(jiǎn)單，也可以非常復(fù)雜，為便于區(qū)分，可進(jìn)行如下定義：

定義1：將線實(shí)體之間相交次數(shù)為0或1的拓?fù)潢P(guān)系稱為簡(jiǎn)單拓?fù)潢P(guān)系。

定義2：將線實(shí)體之間相交次數(shù)大于1的拓?fù)潢P(guān)系稱為復(fù)合拓?fù)潢P(guān)系。

復(fù)雜拓?fù)潢P(guān)系可由簡(jiǎn)單拓?fù)潢P(guān)系進(jìn)行組合形成。

定義3：若線L1與線L2的交集為空(不相交)，則將其拓?fù)潢P(guān)系定義為相離。

定義4：線L1與線L2，當(dāng)線L1與線L2的交集不為空時(shí)，作線L1與線L2交集的領(lǐng)域ε，則ε與線L1及線L2存在交點(diǎn)，依據(jù)交點(diǎn)數(shù)目可定義以下線L1與L2的拓?fù)潢P(guān)系：

定義4.1：若交點(diǎn)為2，則將其拓?fù)潢P(guān)系定義為包含或重合，如圖5(a)所示；

定義4.2：若交點(diǎn)為3，則將其拓?fù)潢P(guān)系定義為相接，如圖5(b)、(c)所示；

定義4.3：若交點(diǎn)為4，有兩種情況：①按順時(shí)針或逆時(shí)針?lè)较?，若ε穿越L1和L2的順序?yàn)榻惶孢M(jìn)行，則將其拓?fù)潢P(guān)系定義為相交，如圖5(f)、(g)所示；②按順時(shí)針或逆時(shí)針?lè)较颍籀糯┰絃1或L2連續(xù)兩次，則將其拓?fù)潢P(guān)系定義為相切，如圖5(d)、(e)所示。

圖5 拓?fù)潢P(guān)系示意圖Fig.5 Schematic diagram of topological relations

簡(jiǎn)而言之，在線實(shí)體間的拓?fù)潢P(guān)系中，當(dāng)兩個(gè)線實(shí)體發(fā)生接觸時(shí)，每條線的兩個(gè)端點(diǎn)在同一側(cè)，則為相切關(guān)系；若線的兩個(gè)端點(diǎn)跨越了接觸部，則為相交關(guān)系；若線的一個(gè)端點(diǎn)位于接觸部，一個(gè)端點(diǎn)不位于接觸部，則為相接關(guān)系。

另外，在線與線發(fā)生接觸的情況下，根據(jù)線線之間交集的維數(shù)，相接有0維相接(0,M)(圖5(b))和1維相接(1,M)(圖5(c))，相切有0維相切(0,T)(圖5(d))和1維相切(1,T)(圖5(e))，相交有0維相交(0,C)(圖5(f))和1維相交(1,C)(圖5(g))，包含(重合)只有1維(圖5(a))。

2.2 元拓?fù)潢P(guān)系

只有線與線之間發(fā)生接觸時(shí)才有可能產(chǎn)生復(fù)合線拓?fù)潢P(guān)系，相離則不能構(gòu)成復(fù)合線關(guān)系。而在發(fā)生接觸的簡(jiǎn)單線關(guān)系中，包含重合可看成是一條線，因此包含重合也不能構(gòu)成復(fù)合線關(guān)系。因此，線與線之間的復(fù)合拓?fù)潢P(guān)系只能由相接、相切和相交關(guān)系組成。由此，可以定義元拓?fù)潢P(guān)系。

定義5：將能夠組成線復(fù)合關(guān)系的、最小不可分的線簡(jiǎn)單拓?fù)潢P(guān)系稱為線元拓?fù)潢P(guān)系。易得，線元拓?fù)潢P(guān)系有3類6種，即0維相交(C0)、1維相交(C1)、0維相切T0、1維相切T1、0維相接(M0)和1維相接(M1)。元拓?fù)潢P(guān)系具有如下特點(diǎn)：

概括性。概括性是指元拓?fù)潢P(guān)系必須概括所有復(fù)合關(guān)系的基本特征。即任意一個(gè)復(fù)合關(guān)系都可以由若干元拓?fù)潢P(guān)系按照一定的排序，經(jīng)過(guò)有限次組合而成。元拓?fù)潢P(guān)系作為基本組成元素存在，必須能概括復(fù)合關(guān)系的所有特征。

“基本”不可分性?！盎尽辈豢煞中裕侵敢话闱闆r下，元拓?fù)潢P(guān)系就是組成復(fù)合拓?fù)潢P(guān)系的最小單元，不可再分。但元拓?fù)潢P(guān)系又不可過(guò)于具體，否則會(huì)導(dǎo)致過(guò)多的繁瑣工作。元拓?fù)潢P(guān)系必須在保證概括性的前提下，保證其不可分性。

2.3 元拓?fù)潢P(guān)系的方位描述

在線與線發(fā)生接觸時(shí)，若把其中一條線看成是一個(gè)面的邊界部分，則線線關(guān)系轉(zhuǎn)變成線面關(guān)系。而線與面發(fā)生接觸時(shí)，線可能在面的外部，也可能在面的內(nèi)部，這就涉及線與面的內(nèi)外方位問(wèn)題。

對(duì)于每個(gè)元拓?fù)潢P(guān)系來(lái)說(shuō)，設(shè)線的兩個(gè)端點(diǎn)為p0和p1，以p0為起始點(diǎn)，沿著L向p1前進(jìn)，記下L與ε的第1個(gè)交點(diǎn)，若此交點(diǎn)在面A的內(nèi)部，則記為in；在面A的外部，則記為out。當(dāng)然，也可以以p1為起點(diǎn)進(jìn)行描述。納入方位關(guān)系以后，分別以p0和p1為起點(diǎn)，線面關(guān)系會(huì)有3類6種。

圖6(a)(out,M0),(out,M0)；(b)(out,T0),(out,T0)；(c)(out,C0),(in,C0)；(d)(out,M1),(out,M1)；(e)(out,T1),(out,T1)；(f)(out,C1),(in,C1)。

記?A為面A的邊界，R(L,A)表示面A和線L的關(guān)系

R(L,A)<=>R(L,?A)=(Orie,MetaR)

其中

Orie={in,out}，MetaR={M1,T1,C1,M0,T0,C0}

圖6 元拓?fù)潢P(guān)系Fig.6 Basic topological relations

2.4 元關(guān)系的連接

2.4.1 元關(guān)系的連接順序

元拓?fù)潢P(guān)系的類型、內(nèi)外方向的定義對(duì)元拓?fù)潢P(guān)系本身進(jìn)行了描述，但元拓?fù)潢P(guān)系之間的連接關(guān)系則需要連接順序和連接方向來(lái)進(jìn)行約束。設(shè)線L與面A邊界之間有n個(gè)元拓?fù)潢P(guān)(如圖7所示)，線的兩個(gè)端點(diǎn)分別為p0、pn,p0為起點(diǎn)，每個(gè)交點(diǎn)依次被編號(hào)，以面A的邊界?A為參考，從第1個(gè)元拓?fù)潢P(guān)系起，按順時(shí)針?lè)较蚋櫍浵旅總€(gè)元拓?fù)潢P(guān)系的編號(hào)，直到最后一個(gè)元拓?fù)潢P(guān)系為止，則有

Order(L,A)=(k1,k2,k3,…,kn),n≥2

將上式納入到元拓?fù)潢P(guān)系的連接中，有

R(L,A)<=>R(L,?A)=(Order,Orie,MetaR)

其中

Order={1,2,3,…,n}，Orie={in,out}，MetaR={M1,T1,C1,M0,T0,C0}

2.4.2 元關(guān)系的連接方向

在線L與面A邊界相交的n個(gè)元拓?fù)潢P(guān)系中，第i個(gè)元拓?fù)潢P(guān)系的連接方向是從i個(gè)元拓?fù)潢P(guān)系到第i+1個(gè)元拓?fù)潢P(guān)系之間的連接線對(duì)應(yīng)于面邊界投影線的方向，如圖8所示，第1個(gè)元拓?fù)潢P(guān)系的連接方向是順時(shí)針(clockwise)，圖中順時(shí)針箭頭所示，第2個(gè)元拓?fù)潢P(guān)系的連接方向是逆時(shí)針(anticlockwise)，圖中逆時(shí)針箭頭所示，最后一個(gè)元拓?fù)潢P(guān)系沒(méi)有方向。

圖7 連接順序Fig.7 Connecting order

圖8 連接方向Fig.8 Connecting direction

進(jìn)一步納入元拓?fù)潢P(guān)系的連接中，有

R(L,A)<=>R(L,?A)=(Order,Orie1,Orie2,MetaR)

其中

Order={1,2,3,…,n},Orie1={in,out},Orie2={c,a},MetaR={M1,T1,C1,M0,T0,C0}

2.5 線面空間關(guān)系集成表達(dá)模型的約束性

線面空間關(guān)系集成表達(dá)模型有3個(gè)約束條件，分別是元拓?fù)潢P(guān)系的排序，元拓?fù)潢P(guān)系的形式，元拓?fù)潢P(guān)系的連接方式。元拓?fù)潢P(guān)系的排序是指每個(gè)元拓?fù)潢P(guān)系的訪問(wèn)次序，例若按順時(shí)針來(lái)進(jìn)行訪問(wèn)，第2個(gè)元拓?fù)潢P(guān)系不一定緊隨第1個(gè)元拓?fù)潢P(guān)系之后，訪問(wèn)次序可根據(jù)元拓?fù)潢P(guān)系編號(hào)的排列順序確定。元拓?fù)潢P(guān)系的形式可依據(jù)元拓?fù)潢P(guān)系的內(nèi)外方向(Orie1)，元拓?fù)潢P(guān)系的類型(MetaR)來(lái)確定。元拓?fù)潢P(guān)系的連接方式是指元關(guān)系的連接方向，可通過(guò)Orie2的值來(lái)判斷。如圖9所示，沿順時(shí)針?lè)较?，將拓?fù)潢P(guān)系的描述式寫(xiě)成矩陣的形式，則有

矩陣的第1行表示元拓?fù)潢P(guān)系的編號(hào)，其排列順序就是元拓?fù)潢P(guān)系的排序；矩陣的第2行和第4行則表示元拓?fù)潢P(guān)系的形式，第3行代表元拓?fù)潢P(guān)系的連接方式，其中第7個(gè)元拓?fù)潢P(guān)系處于最后，所以連接方式為空。

圖9 拓?fù)潢P(guān)系示例Fig.9 Example of topological relations

2.6 復(fù)雜面邊界間拓?fù)潢P(guān)系描述

面與面拓?fù)湎嘟?，歸根結(jié)底為面邊界之間的相交，故面實(shí)體的邊界交集問(wèn)題可以通過(guò)對(duì)線實(shí)體之間的交集改進(jìn)解決。

2.6.1 簡(jiǎn)單面邊界拓?fù)潢P(guān)系描述

現(xiàn)用上述的元拓?fù)潢P(guān)系來(lái)描述不含洞的簡(jiǎn)單面實(shí)體間的拓?fù)潢P(guān)系。

定義6：沿順時(shí)針?lè)较虮闅v面對(duì)象R的邊界?R時(shí)存在n個(gè)交集Inter?R，每個(gè)交集可用相接(M)，相切(T)和相交(C)來(lái)描述，描述子如下

Inter?R={Intersection1,Intersection2,…,

Intersectionn}

式中，Intersectionn=S(Order,Orie1,Orie2,MetaR)，S表示與R有交集的面。

在圖10中，面M和面N的邊界相交，對(duì)邊界?M進(jìn)行順時(shí)針遍歷時(shí)會(huì)得到兩個(gè)C0交集，即交集中沒(méi)有邊界重疊。在邊界相交部分，第1個(gè)交集中N的邊界從外由內(nèi)穿入M中，第2個(gè)交集N的邊界從內(nèi)到外穿出M，因此完整的交集表達(dá)式可表示為

Inter?M:{N(1,out,c,C0),N(2,in,-,C0)}

有時(shí)多條邊界線會(huì)在一個(gè)點(diǎn)上交匯(圖11(a)中的交集2)或邊界交集中同時(shí)存在1維相交和0維相切(圖11(b)中的交集3)，如上圖所示。從圖11(a)可得到如下3條交集表達(dá)式，其中邊界的遍歷都以順時(shí)針的方向從區(qū)域外部開(kāi)始。

圖10 拓?fù)潢P(guān)系示例Fig.10 Example of topological relations

Inter?A={B(1,out,c,C0),B(2,in,-,C0),C(3,out,c,T0),C(4,out,-,T0)}

Inter?B={C(1,out,c,T0),C(2,out,-,T0),A(3,out,a,C0),A(4,in,-,C0)}

Inter?C={A(1,out,a,T0),A(2,out,-,T0),B(3,out,c,T0),B(4,out,-,T0)}

圖11(b)中A和C在2、3、4的交集為1維相交，B和C以及B和A在3處的交集為0維相切，因此邊界交集可表達(dá)為

Inter?A={C(1,in,c,C0),C(2,out,-,C1),B(3,out,-,T0)}

Inter?B={C(1,out,-,T0),A(2,out,-,T0)}

Inter?C={B(1,out,-,T0),A(2,in,c,C1),A(3,out,-,C0)}

圖11 拓?fù)潢P(guān)系示例 Fig.11 Example of topological relations

2.6.2 重疊面積描述

圖12(a)中，面M1和M2相接，且它們之間形成一個(gè)外部分區(qū)，面M3分別與面M1和M2交疊，圖12(b)中N1和N2相接，它們間存在兩個(gè)外部分區(qū)，面N3分別與面N1和N2交疊。首先利用上述的元拓?fù)潢P(guān)系對(duì)兩個(gè)實(shí)體組合中的關(guān)系進(jìn)行描述。

圖12 拓?fù)潢P(guān)系事例Fig.12 Example of topological relations

Inter?M1={M2(1,out,c,T1)M2(2,out,-,T1)M3(3,out,c,C0)M3(4,in,-,C0)}

Inter?M2={M1(1,out,a,T1)M1(2,out,-,T1)M3(3,out,a,C0)M3(4,in,-,C0)}

Inter?M3={M1(1,out,a,C0)M1(2,in,-,C0)M2(3,out,a,C0)M2(4,in,-,C0)}

Inter?N1={N2(1,out,c,T1)N2(2,out,c,T0)N2(3,out,-,T1)N3(4,out,c,C0)N3(5,in,-,C0)}

Inter?N2={N1(1,out,c,T1)N1(2,out,c,T0)N1(3,out,-,T1)N3(4,out,a,C0)N3(5,in,-,C0)}

Inter?N3={N1(1,out,a,C0)N1(2,in,-,C0)N2(3,out,a,C0)N2(4,in,-,C0)}

在圖12中，(M2,M3)和(N2,N3)間的邊界交集有著十分相似的表達(dá)式，但是它們有著不同的拓?fù)湫螒B(tài)。故此元拓?fù)潢P(guān)系雖然可以描述面實(shí)體，但是仍不能精確地區(qū)別部分復(fù)雜面關(guān)系。

在圖13中(a)(b)的元拓?fù)潢P(guān)系及其表達(dá)式完全相同，但是用眼睛來(lái)判斷二者的空間對(duì)象關(guān)系卻不一樣,原因在于圖13(a)中A和B重疊部分比圖13(b)中的少。故只用元拓?fù)潢P(guān)系來(lái)描述，不能完全區(qū)分開(kāi)復(fù)雜面的關(guān)系；引入重疊部分的面積進(jìn)行輔助描述，則可進(jìn)一步區(qū)分復(fù)雜面的關(guān)系?，F(xiàn)引入重疊面積的概念，圖13中陰影部分的面積可記為Area則Area=area(A∩B)。

圖13 重疊面積示例Fig.13 Example of topological area

在元拓?fù)潢P(guān)系中，相接和相切的重疊面積可記為?，于是面實(shí)體間的描述子可進(jìn)一步記為

Inter?R={Intersection1,Intersection2,…,Intersectionn,

Area1,Area2,…,Aream}

其中Intersectionn=S(Order,Orie1,Orie2,MetaR)。

此時(shí)圖12中的拓?fù)潢P(guān)系可進(jìn)一步表示成如下：

Inter?M1={M2(1,out,c,T1)M2(2,out,-,T1)M3(3,out,c,C0)M3(4,in,-,C0),area(M1∩M3)}

Inter?M2={M1(1,out,a,T1)M1(2,out,-,T1)M3(3,out,a,C0)M3(4,in,-,C0),area(M2∩M3)}

Inter?M3={M1(1,out,a,C0)M1(2,in,-,C0)M2(3,out,a,C0)M2(4,in,-,C0),area(M3∩M1),area(M3∩M2)}

Inter?N1={N2(1,out,c,T1)N2(2,out,c,T0)N2(3,out,-,T1)N3(4,out,c,C0)N3(5,in,-,C0),area(N1∩N3)}

Inter?N2={N1(1,out,c,T1)N1(2,out,c,T0)N1(3,out,-,T1)N3(4,out,a,C0)N3(5,in,-,C0),area(N2∩N3)}

Inter?N3={N1(1,out,a,C0)N1(2,in,-,C0)N2(3,out,a,C0)N2(4,in,-,C0),area(N3∩N1),area(N3∩N2)}

在上述表達(dá)式中，(M2,M3)和(N2,N3)的表達(dá)式十分相似，但它們的重疊面積卻不相同，因此可以精確地區(qū)別出不同的復(fù)雜面拓?fù)潢P(guān)系。

2.6.3 帶洞面邊界拓?fù)潢P(guān)系描述

以上是對(duì)非洞簡(jiǎn)單面邊界拓?fù)潢P(guān)系的討論，現(xiàn)在引入重疊面積輔助描述的簡(jiǎn)單面元拓?fù)潢P(guān)系表達(dá)模型的基礎(chǔ)上討論含洞的復(fù)雜面邊界拓?fù)潢P(guān)系表達(dá)模型。

當(dāng)洞中不含面時(shí)，先以定義6遍歷并描述對(duì)象R的外邊界?R。再沿順時(shí)針?lè)较虮闅v對(duì)象R的內(nèi)邊界?R′，會(huì)存在n個(gè)交集Inter?R′,每個(gè)交集可用相接(M)，相切(T)和相交(C)來(lái)描述，描述如下

Inter?R′={Intersection1,Intersection2,…,

Intersectionn,-R′}

其中,Intersectionn=S(Order,Orie,MetaR)，S表示與R的洞R′有交集的面;-R′代表S與洞R′的重疊面積，但由于R′是洞故將重疊面積置為-R′。

當(dāng)洞中含有面時(shí)，為了在表達(dá)式中明確的體現(xiàn)出此關(guān)系，可以遍歷內(nèi)邊界時(shí)將洞中面和洞的關(guān)系加入到內(nèi)邊界所對(duì)應(yīng)的表達(dá)式中。描述如下

Inter?R′={Intersection1,Intersection2,…,

Intersectionn,-R′,R′?/=I}

其中,R′為帶洞面的內(nèi)邊界，-R′為相交面與洞的重疊面積，I為洞中所包含的面，R′?I代表面I完全被洞R′包含但沒(méi)有完全重合，R′=I代表面I與R′完全重合。

現(xiàn)以圖14、圖15為例進(jìn)行說(shuō)明：兩圖中面A的洞內(nèi)分別存在與A完全相離的面B和與A相切的面B；面D同時(shí)與這3個(gè)面相交，但在邊界細(xì)節(jié)處的拓?fù)潢P(guān)系存在不同。若使用九交模型，方向矩陣或其他拓?fù)涿枋龇椒▉?lái)描述，將會(huì)得到兩個(gè)空間組合拓?fù)潢P(guān)系相同的結(jié)論，且實(shí)體間的方位關(guān)系一致，使得難以分辨兩個(gè)組合間的差別。使用擴(kuò)展(重疊面積輔助描述)的元拓?fù)涠x可對(duì)兩個(gè)實(shí)體組合間的拓?fù)潢P(guān)系進(jìn)行辨認(rèn)。

圖14 面實(shí)體組合Fig.14 Combination of plane entities

圖15 面實(shí)體組合Fig.15 Combination of plane entities

由上述的擴(kuò)展元拓?fù)潢P(guān)系的定義可以得到圖14的拓?fù)潢P(guān)系表達(dá)式，如下

Inter?A={D(1,out,c,C0)D(2,in,-,C0)area(A∩D)}

Inter?A′={D(1,out,a,C0)D(2,in,-,C0)B(3,out,-,T1),-,-,A′?B,A′?C}

Inter?B={D(1,out,a,C0)D(2,in,-,C0)A′(3,in,-,T1)area(B∩D,-,B?A′)}

Inter?D={A(1,out,a,C0)A(2,in,-,C0)A′(3,out,a,C0)A′(4,in,-,C0)B(5,out,a,C0)B(6,in,-,C0)C(7,out,c,C0)C(8,in,-,C0)area(D∩A),-,area(D∩B)area(D∩C)}

由上述的擴(kuò)展元拓?fù)潢P(guān)系的定義可以得到圖15的拓?fù)潢P(guān)系表達(dá)式，如下

Inter?A={D(1,out,c,C0)D(2,in,a,C0)D(3,out,c,C0)D(4,in,-,C0)area(A∩D)}

Inter?A={D(1,out,c,C0)D(2,in,a,C0)D(3,out,c,C0)D(4,in,-,C0)B(5,out,-,T1)-,-,A′?B,A′?C}

Inter?B={D(1,out,a,C0)D(2,in,c,C0)D(3,out,a,C0)D(4,in,-,C0)A′(5,in,-,T1)area(B∩D),-,B?A′}

Inter?C={D(1,out,c,C0)D(2,in,a,C0)D(3,out,c,C0)D(4,in,-,C0)area(C∩D),C?A′}

Inter?D={A(1,out,c,C0)A(2,in,c,C0)A(3,out,a,C0)A(4,in,-,C0)B(5,out,a,C0)B(6,in,a,C0)B(7,out,a,C0)B(8,in,-,C0)C(9,out,c,C0)C(10,in,c,C0)C(11,out,c,C0)C(12,in,-,C0)A′(13,out,a,C0)A′(14,in,c,C0)A′(15,out,a,C0)A′(16,in,-,C0)area(D∩A)area(D∩B)area(D∩C)-}

分別比較上述圖14和圖15的拓?fù)潢P(guān)系表達(dá)式，可以看出圖14和圖15的Inter?A,Inter?A′,Inter?B,Inter?C,Inter?D都有明顯的差異，故文中提出的擴(kuò)展元拓?fù)潢P(guān)系可以很好地區(qū)分出復(fù)雜面實(shí)體邊界的拓?fù)潢P(guān)系。且每一個(gè)表達(dá)式都可用矩陣表示?，F(xiàn)將圖15中的拓?fù)潢P(guān)系表達(dá)式轉(zhuǎn)化為矩陣形式，如下

上述矩陣中，每一列代表一個(gè)元拓?fù)潢P(guān)系，其中矩陣的第5行代表重疊面積；矩陣RA、RA′、RB、RC、RD是圖14中的面實(shí)體組合的拓?fù)潢P(guān)系矩陣。

3 復(fù)雜面實(shí)體的拓?fù)潢P(guān)系精細(xì)化表達(dá)

如圖16所示，文中從線面元拓?fù)潢P(guān)系模型出發(fā)，通過(guò)引入重疊面積，洞邊界遍歷定義和洞中面與洞關(guān)系定義擴(kuò)展線面拓?fù)潢P(guān)系模型，完成對(duì)復(fù)雜面實(shí)體的拓?fù)潢P(guān)系精細(xì)化表達(dá)。

3.1 基礎(chǔ)程序算法

基于以上所引入的概念和定義，現(xiàn)可將復(fù)雜面實(shí)體的拓?fù)潢P(guān)系精細(xì)化表達(dá)方式總結(jié)并設(shè)計(jì)出相應(yīng)的算法并實(shí)現(xiàn)?；舅惴ㄈ缦拢?/p>

圖16 概念流程圖Fig.16 Flow diagram of concept

組合表達(dá)算法

∥初始調(diào)用 INOUT: R->{r1,r2,…,rn}(復(fù)雜面實(shí)體集合);

n(復(fù)雜面實(shí)體個(gè)數(shù))；

OUTPUT:M->{m1,m2,m3…}(關(guān)系矩陣集合)；

COMBINED-EXPRESSION(R,N,M):

foreachr∈Rdo ∥遍歷每個(gè)復(fù)雜面實(shí)體

foreachb∈rdo ∥遍歷復(fù)雜面實(shí)體中的內(nèi)外邊界

Ifb==out then ∥如果b是外邊界

foreachp∈bdo ∥順時(shí)針遍歷改邊界上的交點(diǎn)

assertp==out/in ∥判斷該點(diǎn)的進(jìn)出

assertp==c/a∥判斷該點(diǎn)與下一點(diǎn)之間的方向

assertp==C0/C1/T0/T1∥判斷該點(diǎn)的相交方式

Ifp==lastone then ∥如果p是當(dāng)前邊界的最后一個(gè)交點(diǎn)

assertr∩r′==? orr∩r′!=? ∥判斷b所在的實(shí)體r是否與其他實(shí)體是否有面積相交

assertr∈r′ orr?r′ ∥判斷b所在的實(shí)體是否被包含在其他實(shí)體內(nèi)

Ifb==in then ∥如果b是外邊界

foreachp∈bdo ∥逆時(shí)針遍歷改邊界上的交點(diǎn)

assertp==out/in ∥判斷該點(diǎn)的進(jìn)出

assertp==c/a∥判斷該點(diǎn)與下一點(diǎn)之間的方向

assertp==C0/C1/T0/T1∥判斷該點(diǎn)的相交方式

Ifp==lastone then ∥如果p是當(dāng)前邊界的最后一個(gè)交點(diǎn)

assertr∩r′==? orr∩r′!=? ∥判斷b所在的實(shí)體r是否與其他

∥實(shí)體是否有面積相交

assertr′∈rorr′ ?r∥判斷b所在的實(shí)體是否包含在其他實(shí)體

∥生成該邊界的組合關(guān)系矩陣表達(dá)式

produceM={m1,m2,m3…} ∥生成關(guān)系矩陣表達(dá)式

returnM

3.2 數(shù)據(jù)類型分析與歸納

通過(guò)歸納分析，元拓?fù)浔磉_(dá)關(guān)系描述面與面相交時(shí)可以分為三大類，五小類的基礎(chǔ)相交情況，而更為復(fù)雜的面與面相交的拓?fù)淝闆r均可由5種基礎(chǔ)相交的情況疊加生成。三大類分別是簡(jiǎn)單面(不含洞)與簡(jiǎn)單面(不含洞)相交，簡(jiǎn)單面(不含洞)與含洞面相交，含洞面與含洞面相交；其中含洞面可分為僅含洞的面和洞中有面的面；而洞中有面的面依據(jù)洞中面和面的關(guān)系又可分為洞中面邊界與洞邊界完全重合，部分重合，不重合3種情況。通過(guò)將線面之間相交的元拓?fù)潢P(guān)系擴(kuò)展到5類面面基礎(chǔ)相交情況中，便可以將元拓?fù)潢P(guān)系擴(kuò)展到復(fù)雜面邊界間的拓?fù)潢P(guān)系之中，如圖17所示。

圖17 復(fù)雜面相交情況分解圖Fig.17 Decomposition diagram of complex planar objects

3.3 模擬數(shù)據(jù)驗(yàn)證

為驗(yàn)證算法能否有效的通過(guò)精細(xì)化組合表達(dá)模型區(qū)分復(fù)雜面實(shí)體拓?fù)潢P(guān)系的不同，可在3.2節(jié)5種基礎(chǔ)相交情況上通過(guò)比較每種基礎(chǔ)相交情況簡(jiǎn)單交互和復(fù)雜交互模型，比較該算法所生成的元拓?fù)潢P(guān)矩陣的差異。算法所生成的5種基礎(chǔ)相交情況的元拓?fù)潢P(guān)系矩陣如下表1。

通過(guò)比較表1中的每種拓?fù)潢P(guān)系的矩陣表達(dá)式，可以看出即使在相同的基礎(chǔ)相交情況下簡(jiǎn)單交互與復(fù)雜交互模型的矩陣表達(dá)式之間也存在明顯的差異，因此可以通過(guò)每種拓?fù)潢P(guān)系的擴(kuò)展元拓?fù)潢P(guān)系表達(dá)式來(lái)更好辨別大體相似但細(xì)節(jié)處不同的復(fù)雜面實(shí)體之間的拓?fù)潢P(guān)系，做到精細(xì)化表達(dá)。綜上所述，本文所提出的引出重疊面積輔助描述的元拓?fù)潢P(guān)系可以很好地區(qū)別復(fù)雜面實(shí)體邊界拓?fù)潢P(guān)系。

4 總結(jié)與展望

本文對(duì)包含著復(fù)雜邊界交集的面之間的拓?fù)潢P(guān)系進(jìn)行了分析，探討了使用元拓?fù)潢P(guān)系對(duì)此類面對(duì)象進(jìn)行拓?fù)潢P(guān)系描述時(shí)所存在的限制，針對(duì)限制提出了使用邊界交集元拓?fù)浔磉_(dá)式對(duì)細(xì)節(jié)進(jìn)行呈現(xiàn)，沿順時(shí)針?lè)较蛴涗泴?duì)象間的各個(gè)邊界交集，并使用0維或1維，相交或相接的方式對(duì)邊界交集的不同形式進(jìn)行區(qū)分。為了消除具有相同邊界交集表達(dá)式但拓?fù)潢P(guān)系不同而造成的模糊性，引入了重疊面積的概念，并與元拓?fù)潢P(guān)系結(jié)合對(duì)空間區(qū)組合間的拓?fù)潢P(guān)系進(jìn)行描述。

表1 5種基礎(chǔ)相交情況及其元拓?fù)潢P(guān)系矩陣

續(xù)表1

續(xù)表1

在實(shí)際應(yīng)用中，除了面對(duì)象外，還包括了點(diǎn)、多點(diǎn)、線、多線以及由點(diǎn)、線、區(qū)組合形成的復(fù)雜空間對(duì)象，因此未來(lái)的研究工作：①需要對(duì)以上用來(lái)描述空間面實(shí)體的方法在點(diǎn)、線上進(jìn)行擴(kuò)展，以實(shí)現(xiàn)對(duì)二維空間中任意對(duì)象的處理；②提取空間場(chǎng)景中的定性不變量，如方向和距離等，用此類定性概念加強(qiáng)對(duì)空間對(duì)象拓?fù)潢P(guān)系的描述；③將對(duì)空間對(duì)象間拓?fù)潢P(guān)系的描述擴(kuò)展到擁有大量空間實(shí)體的場(chǎng)景中，以實(shí)現(xiàn)對(duì)空間場(chǎng)景拓?fù)潢P(guān)系的描述。