陳占龍,葉 文

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

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

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

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

圖1 復雜空間對象的拓撲關系Fig.1 Topological relations of complex spatial object

1 復雜面實體及其拓撲關系

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

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

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

圖3 復雜空間對象的構成Fig.3 Component of complex spatial object

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

圖4 復雜面拓撲關系Fig.4 Topological relation of complex planar

2 復雜面實體的元拓撲邊界交集描述

2.1 線面實體間拓撲關系

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

定義1：將線實體之間相交次數(shù)為0或1的拓撲關系稱為簡單拓撲關系。

定義2：將線實體之間相交次數(shù)大于1的拓撲關系稱為復合拓撲關系。

復雜拓撲關系可由簡單拓撲關系進行組合形成。

定義3：若線L1與線L2的交集為空(不相交)，則將其拓撲關系定義為相離。

定義4：線L1與線L2，當線L1與線L2的交集不為空時，作線L1與線L2交集的領域ε，則ε與線L1及線L2存在交點，依據(jù)交點數(shù)目可定義以下線L1與L2的拓撲關系：

定義4.1：若交點為2，則將其拓撲關系定義為包含或重合，如圖5(a)所示；

定義4.2：若交點為3，則將其拓撲關系定義為相接，如圖5(b)、(c)所示；

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

圖5 拓撲關系示意圖Fig.5 Schematic diagram of topological relations

簡而言之，在線實體間的拓撲關系中，當兩個線實體發(fā)生接觸時，每條線的兩個端點在同一側，則為相切關系；若線的兩個端點跨越了接觸部，則為相交關系；若線的一個端點位于接觸部，一個端點不位于接觸部，則為相接關系。

另外，在線與線發(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ā)生接觸時才有可能產(chǎn)生復合線拓撲關系，相離則不能構成復合線關系。而在發(fā)生接觸的簡單線關系中，包含重合可看成是一條線，因此包含重合也不能構成復合線關系。因此，線與線之間的復合拓撲關系只能由相接、相切和相交關系組成。由此，可以定義元拓撲關系。

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

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

“基本”不可分性。“基本”不可分性，是指一般情況下，元拓撲關系就是組成復合拓撲關系的最小單元，不可再分。但元拓撲關系又不可過于具體，否則會導致過多的繁瑣工作。元拓撲關系必須在保證概括性的前提下，保證其不可分性。

2.3 元拓撲關系的方位描述

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

對于每個元拓撲關系來說，設線的兩個端點為p0和p1，以p0為起始點，沿著L向p1前進，記下L與ε的第1個交點，若此交點在面A的內部，則記為in；在面A的外部，則記為out。當然，也可以以p1為起點進行描述。納入方位關系以后，分別以p0和p1為起點，線面關系會有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的關系

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

其中

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

圖6 元拓撲關系Fig.6 Basic topological relations

2.4 元關系的連接

2.4.1 元關系的連接順序

元拓撲關系的類型、內外方向的定義對元拓撲關系本身進行了描述，但元拓撲關系之間的連接關系則需要連接順序和連接方向來進行約束。設線L與面A邊界之間有n個元拓撲關(如圖7所示)，線的兩個端點分別為p0、pn,p0為起點，每個交點依次被編號，以面A的邊界?A為參考，從第1個元拓撲關系起，按順時針方向跟蹤，記下每個元拓撲關系的編號，直到最后一個元拓撲關系為止，則有

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

將上式納入到元拓撲關系的連接中，有

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 元關系的連接方向

在線L與面A邊界相交的n個元拓撲關系中，第i個元拓撲關系的連接方向是從i個元拓撲關系到第i+1個元拓撲關系之間的連接線對應于面邊界投影線的方向，如圖8所示，第1個元拓撲關系的連接方向是順時針(clockwise)，圖中順時針箭頭所示，第2個元拓撲關系的連接方向是逆時針(anticlockwise)，圖中逆時針箭頭所示，最后一個元拓撲關系沒有方向。

圖7 連接順序Fig.7 Connecting order

圖8 連接方向Fig.8 Connecting direction

進一步納入元拓撲關系的連接中，有

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 線面空間關系集成表達模型的約束性

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

矩陣的第1行表示元拓撲關系的編號，其排列順序就是元拓撲關系的排序；矩陣的第2行和第4行則表示元拓撲關系的形式，第3行代表元拓撲關系的連接方式，其中第7個元拓撲關系處于最后，所以連接方式為空。

圖9 拓撲關系示例Fig.9 Example of topological relations

2.6 復雜面邊界間拓撲關系描述

面與面拓撲相交，歸根結底為面邊界之間的相交，故面實體的邊界交集問題可以通過對線實體之間的交集改進解決。

2.6.1 簡單面邊界拓撲關系描述

現(xià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的邊界從外由內穿入M中，第2個交集N的邊界從內到外穿出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 拓撲關系示例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 拓撲關系示例 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交疊。首先利用上述的元拓撲關系對兩個實體組合中的關系進行描述。

圖12 拓撲關系事例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)間的邊界交集有著十分相似的表達式，但是它們有著不同的拓撲形態(tài)。故此元拓撲關系雖然可以描述面實體，但是仍不能精確地區(qū)別部分復雜面關系。

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

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

在元拓撲關系中，相接和相切的重疊面積可記為?，于是面實體間的描述子可進一步記為

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

Area1,Area2,…,Aream}

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

此時圖12中的拓撲關系可進一步表示成如下：

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ū)別出不同的復雜面拓撲關系。

2.6.3 帶洞面邊界拓撲關系描述

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

當洞中不含面時，先以定義6遍歷并描述對象R的外邊界?R。再沿順時針方向遍歷對象R的內邊界?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′。

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

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

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

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

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

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

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

由上述的擴展元拓撲關系的定義可以得到圖14的拓撲關系表達式，如下

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

由上述的擴展元拓撲關系的定義可以得到圖15的拓撲關系表達式，如下

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

上述矩陣中，每一列代表一個元拓撲關系，其中矩陣的第5行代表重疊面積；矩陣RA、RA′、RB、RC、RD是圖14中的面實體組合的拓撲關系矩陣。

3 復雜面實體的拓撲關系精細化表達

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

3.1 基礎程序算法

基于以上所引入的概念和定義，現(xiàn)可將復雜面實體的拓撲關系精細化表達方式總結并設計出相應的算法并實現(xiàn)?；舅惴ㄈ缦拢?/p>

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

組合表達算法

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

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

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

COMBINED-EXPRESSION(R,N,M):

foreachr∈Rdo ∥遍歷每個復雜面實體

foreachb∈rdo ∥遍歷復雜面實體中的內外邊界

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

∥實體是否有面積相交

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

∥生成該邊界的組合關系矩陣表達式

produceM={m1,m2,m3…} ∥生成關系矩陣表達式

returnM

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

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

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

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

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

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

4 總結與展望

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

表1 5種基礎相交情況及其元拓撲關系矩陣

續(xù)表1

續(xù)表1

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