復(fù)雜面實體拓?fù)潢P(guān)系的精細化模型

陳占龍,葉 文

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

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

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

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

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

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

從應(yīng)用的觀點出發(fā)，空間應(yīng)用處理復(fù)雜的空間實體更多，而不是當(dāng)前空間數(shù)據(jù)庫系統(tǒng)、空間查詢語言和GIS中常見的簡單點、線和面?，F(xiàn)實中的空間對象可能有若干組成部分，不同組成部分間可能會互相重疊，且面中可能有洞。Vasardani提出的帶洞面的定性模型主要由5個互不相同的部分組成，如圖2所示，B°是B的內(nèi)部；B-1是B所圍繞著的內(nèi)部區(qū)域，同時也填充了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ù)雜空間對象可通過復(fù)合空間對象模型進行構(gòu)建，其主要思想是對簡單對象進行幾何組合生成，如合并和求差。例如：對于面A和B，若A和B相離，則(A∪B)構(gòu)成有兩個子區(qū)的多區(qū)(圖3(a))，在A包含B的限制條件下，結(jié)構(gòu)(A-B)形成一個帶洞面(圖3(b))，對于A包含B，而C與A,B相離的情況，結(jié)構(gòu)(A-B)∪C形成有2個子面的多面，其中一個子面為帶洞面(圖3(c))，在A包含B，B包含C的條件下，結(jié)構(gòu)(A-B)∪C形成一個子面落在另一個子面洞內(nèi)的多面(圖3(d))。

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

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

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

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

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

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

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

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

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

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

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

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

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

定義4.3：若交點為4，有兩種情況：①按順時針或逆時針方向，若ε穿越L1和L2的順序為交替進行，則將其拓?fù)潢P(guān)系定義為相交，如圖5(f)、(g)所示；②按順時針或逆時針方向，若ε穿越L1或L2連續(xù)兩次，則將其拓?fù)潢P(guān)系定義為相切，如圖5(d)、(e)所示。

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

簡而言之，在線實體間的拓?fù)潢P(guān)系中，當(dāng)兩個線實體發(fā)生接觸時，每條線的兩個端點在同一側(cè)，則為相切關(guān)系；若線的兩個端點跨越了接觸部，則為相交關(guā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ā)生接觸時才有可能產(chǎn)生復(fù)合線拓?fù)潢P(guān)系，相離則不能構(gòu)成復(fù)合線關(guān)系。而在發(fā)生接觸的簡單線關(guān)系中，包含重合可看成是一條線，因此包含重合也不能構(gòu)成復(fù)合線關(guān)系。因此，線與線之間的復(fù)合拓?fù)潢P(guān)系只能由相接、相切和相交關(guān)系組成。由此，可以定義元拓?fù)潢P(guān)系。

定義5：將能夠組成線復(fù)合關(guā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)系具有如下特點：

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

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

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

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

對于每個元拓?fù)潢P(guān)系來說，設(shè)線的兩個端點為p0和p1，以p0為起始點，沿著L向p1前進，記下L與ε的第1個交點，若此交點在面A的內(nèi)部，則記為in；在面A的外部，則記為out。當(dāng)然，也可以以p1為起點進行描述。納入方位關(guān)系以后，分別以p0和p1為起點，線面關(guān)系會有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)外方向的定義對元拓?fù)潢P(guān)系本身進行了描述，但元拓?fù)潢P(guān)系之間的連接關(guān)系則需要連接順序和連接方向來進行約束。設(shè)線L與面A邊界之間有n個元拓?fù)潢P(guān)(如圖7所示)，線的兩個端點分別為p0、pn,p0為起點，每個交點依次被編號，以面A的邊界?A為參考，從第1個元拓?fù)潢P(guān)系起，按順時針方向跟蹤，記下每個元拓?fù)潢P(guān)系的編號，直到最后一個元拓?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個元拓?fù)潢P(guān)系中，第i個元拓?fù)潢P(guān)系的連接方向是從i個元拓?fù)潢P(guān)系到第i+1個元拓?fù)潢P(guān)系之間的連接線對應(yīng)于面邊界投影線的方向，如圖8所示，第1個元拓?fù)潢P(guān)系的連接方向是順時針(clockwise)，圖中順時針箭頭所示，第2個元拓?fù)潢P(guān)系的連接方向是逆時針(anticlockwise)，圖中逆時針箭頭所示，最后一個元拓?fù)潢P(guān)系沒有方向。

圖7 連接順序Fig.7 Connecting order

圖8 連接方向Fig.8 Connecting direction

進一步納入元拓?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)系集成表達模型的約束性

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

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

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

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

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

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

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

定義6：沿順時針方向遍歷面對象R的邊界?R時存在n個交集Inter?R，每個交集可用相接(M)，相切(T)和相交(C)來描述，描述子如下

Inter?R={Intersection1,Intersection2,…,

Intersectionn}

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

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

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

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

圖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維相切，因此邊界交集可表達為

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相接，且它們之間形成一個外部分區(qū)，面M3分別與面M1和M2交疊，圖12(b)中N1和N2相接，它們間存在兩個外部分區(qū)，面N3分別與面N1和N2交疊。首先利用上述的元拓?fù)潢P(guān)系對兩個實體組合中的關(guā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)間的邊界交集有著十分相似的表達式，但是它們有著不同的拓?fù)湫螒B(tài)。故此元拓?fù)潢P(guān)系雖然可以描述面實體，但是仍不能精確地區(qū)別部分復(fù)雜面關(guān)系。

在圖13中(a)(b)的元拓?fù)潢P(guān)系及其表達式完全相同，但是用眼睛來判斷二者的空間對象關(guān)系卻不一樣,原因在于圖13(a)中A和B重疊部分比圖13(b)中的少。故只用元拓?fù)潢P(guān)系來描述，不能完全區(qū)分開復(fù)雜面的關(guā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)系中，相接和相切的重疊面積可記為?，于是面實體間的描述子可進一步記為

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

Area1,Area2,…,Aream}

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

此時圖12中的拓?fù)潢P(guā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)}

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

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

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

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

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

Intersectionn,-R′}

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

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

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

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

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

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

圖14 面實體組合Fig.14 Combination of plane entities

圖15 面實體組合Fig.15 Combination of plane entities

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

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)}

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

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)系表達式，可以看出圖14和圖15的Inter?A,Inter?A′,Inter?B,Inter?C,Inter?D都有明顯的差異，故文中提出的擴展元拓?fù)潢P(guān)系可以很好地區(qū)分出復(fù)雜面實體邊界的拓?fù)潢P(guān)系。且每一個表達式都可用矩陣表示?，F(xiàn)將圖15中的拓?fù)潢P(guān)系表達式轉(zhuǎn)化為矩陣形式，如下

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

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

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

3.1 基礎(chǔ)程序算法

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

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

組合表達算法

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

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

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

COMBINED-EXPRESSION(R,N,M):

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

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

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

foreachp∈bdo ∥順時針遍歷改邊界上的交點

assertp==out/in ∥判斷該點的進出

assertp==c/a∥判斷該點與下一點之間的方向

assertp==C0/C1/T0/T1∥判斷該點的相交方式

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

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

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

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

foreachp∈bdo ∥逆時針遍歷改邊界上的交點

assertp==out/in ∥判斷該點的進出

assertp==c/a∥判斷該點與下一點之間的方向

assertp==C0/C1/T0/T1∥判斷該點的相交方式

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

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

∥實體是否有面積相交

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

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

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

returnM

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

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

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

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

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

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

4 總結(jié)與展望

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

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

續(xù)表1

續(xù)表1

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