復(fù)合面狀對象拓撲關(guān)系的表達模型

陳占龍，馮齊奇，吳信才

1.中國地質(zhì)大學(xué)（武漢）信息工程學(xué)院，湖北 武漢430074；2.地理信息工程國家重點實驗室，陜西 西安710054

1.Department of Information Engineering，China University of Geosciences，Wuhan 430074，China；2.State Key Laboratory of Geography Information Engineering，Xi’an 710054，China

1 引 言

在人們的衣食住行等日常生活中，大約有70%～80%的數(shù)據(jù)都與空間位置相關(guān)，大量空間信息的存在使得信息查詢和綜合成為目前GIS的基本組成部分。文獻［1］總結(jié)了地球空間信息學(xué)的七大理論問題，而這七大理論問題中有4個涉及空間關(guān)系，說明空間關(guān)系在GIS基礎(chǔ)理論研究中的重要地位?？臻g關(guān)系包括了拓撲關(guān)系、度量關(guān)系和距離關(guān)系，其中拓撲關(guān)系是空間關(guān)系理論中最重要的部分。復(fù)雜對象間的拓撲關(guān)系描述分析作為地理信息科學(xué)的一個基礎(chǔ)研究問題，對完善空間關(guān)系理論體系、空間推理、人工智能等具有重要意義。

當(dāng)前在GIS中，空間區(qū)域拓撲關(guān)系的描述模型主要是基于文獻［2—3］提出的9－交集模型（nine－intersection model，9IM）及其一些擴展，如維擴展的9－交集模型（dimensionally extended nine－intersection model，DE－9IM）［4－6］等。它 們描述了簡單區(qū)域間的8種基本拓撲關(guān)系，但現(xiàn)實中的空間對象往往是復(fù)雜的，如一個區(qū)域包括分開的子部分、洞等。例如海南島與中國大陸是分開的，南非的領(lǐng)土是帶洞的，因為它完全包含萊索托，因此對于這些復(fù)合面狀對象僅僅使用簡單面狀對象不能完全模擬現(xiàn)實世界。文獻［7］把有洞區(qū)域分為區(qū)域整體和其包含的洞，擴展了4交集模型，但代價是對一切細節(jié)進行單調(diào)枚舉；文獻［8］同樣通過擴展4交集模型，使其能夠判斷由任意多個二維區(qū)域（可能帶洞）組成的復(fù)雜區(qū)域之間的拓撲關(guān)系，但沒有考慮到分離的部分；文獻［9—10］分別基于9－交集模型研究了復(fù)雜空間對象之間的關(guān)系；文獻［11］通過計算不確定線狀目標(biāo)與面狀目標(biāo)各組成部分之間的相交程度組成的空間向量與9－交集模型確定的空間關(guān)系向量之間的相關(guān)度，確定線狀目標(biāo)和面狀目標(biāo)之間拓撲關(guān)系的描述模型，但是適用范圍較??；文獻［12—13］基于混合幾何對象模型和維擴展9－交集模型，提出了混合幾何對象拓撲關(guān)系判斷模型，但是沒有研究分開的區(qū)域或帶洞區(qū)域；文獻［14］給出了“蛋－黃”模型的鄰近拓撲關(guān)系之間的動態(tài)變化圖和相對應(yīng)的93種拓撲關(guān)系；文獻［15］針對復(fù)雜空間關(guān)系擴展9－交集模型，給出了新的語法、語義和推理規(guī)則。文獻［16］通過擴展9－交集模型，將9－交集矩陣的元素擴展為二進制編碼，分別研究了帶雙洞區(qū)域和簡單區(qū)域［17］、帶單洞區(qū)域和簡單區(qū)域［18］及3個簡單區(qū)域［19］間的拓撲關(guān)系。綜合已有的研究成果可知，基于簡單區(qū)域的9－交集模型表達不夠簡潔、明確，不能統(tǒng)一表達復(fù)合面狀對象的拓撲關(guān)系，無法保證復(fù)合面狀對象間拓撲關(guān)系的唯一性，同一9－交集矩陣可能對應(yīng)多種物理解釋。雖然學(xué)者們在復(fù)合面狀對象拓撲關(guān)系的表達模型方面做了不少研究，但大多都是基于一種特定的面狀對象，如帶單洞區(qū)域和簡單區(qū)域、3個簡單區(qū)域等，并不能擴展到所有復(fù)合面狀對象，適用范圍有限。

針對目前9－交集模型表達復(fù)合面狀對象拓撲關(guān)系時所存在的問題，本文采用“分解”思想，分解復(fù)合面狀對象，對現(xiàn)有的9－交集模型進行改進，擴展到一般情況，并不只針對某一特定面狀對象，增強其適用范圍。方法1根據(jù)復(fù)合面狀對象的結(jié)構(gòu)分解成多個簡單區(qū)域，用多個9－交集矩陣表示拓撲關(guān)系；方法2根據(jù)空間區(qū)域劃分方法分解成點集，使9－交集矩陣的元素擴展為二進制編碼。這樣9－交集矩陣的表示范圍變大，能夠準(zhǔn)確地區(qū)分復(fù)合面狀對象間的拓撲關(guān)系。最后比較了擴展模型和9－交集模型的表達能力。

2 復(fù)合面狀對象

從應(yīng)用的觀點出發(fā)，空間應(yīng)用處理更多的是復(fù)合的幾何結(jié)構(gòu)，而不是當(dāng)前空間數(shù)據(jù)庫系統(tǒng)、空間查詢語言和GIS中常見的簡單點、線、區(qū)。開放地理信息聯(lián)盟（OGC）在OGC抽象規(guī)范［6］及地理標(biāo)記語言GML中提出了稱為簡單要素的幾何結(jié)構(gòu)，對這些被稱為MultiPoint、MultiLineString和MultiPolygon的幾何結(jié)構(gòu)進行了非正式的描述。

復(fù)合面狀對象A是由n（n≥1）個區(qū)域組成，這些區(qū)域或分離，或相交于一個或多個邊界點，或帶洞，即A＝｛A1∪A2∪…∪An｝，如圖1所示。

圖1 復(fù)合面狀對象AFig.1 Complex geometric objects A

3 復(fù)合面狀對象的拓撲關(guān)系描述模型

針對復(fù)合面狀對象，9－交集模型雖然也能表達區(qū)域間的拓撲關(guān)系，但是其表達不夠準(zhǔn)確，無法將區(qū)域的子集、邊界、補集與另一個區(qū)域的相交情況的細節(jié)區(qū)分開，無法保證復(fù)合面狀對象間拓撲關(guān)系的唯一性，同一9－交集矩陣可能對應(yīng)多種物理解釋。例如，圖2中的兩種拓撲關(guān)系是不同的，但卻對應(yīng)同一個9－交集矩陣，用簡單9－交集模型表示為相離。

圖2 不同拓撲關(guān)系對應(yīng)同一個9－交集矩陣Fig.2 Different topological relations correspond to the same 9－intersection matrix

經(jīng)典9－交集模型出現(xiàn)這種問題的原因在于將區(qū)域劃分為內(nèi)部A0、邊界?A和外部A－3部分，而在復(fù)合面狀對象中，這幾部分包含了多個相離的子集，僅用這3部分的整體的相交程度無法區(qū)分各部分細節(jié)的拓撲關(guān)系。因此，研究復(fù)合面狀對象間的拓撲關(guān)系的關(guān)鍵是如何描述復(fù)合面狀對象各部分子集的拓撲關(guān)系。本文采用“分解”的思想，將復(fù)合面狀對象分解，以表現(xiàn)復(fù)合面狀對象各部分細節(jié)的拓撲關(guān)系。

3.1 分解成簡單區(qū)域的9－交集模型

根據(jù)OGC抽象規(guī)范［6］中對復(fù)合幾何結(jié)構(gòu)的描述，復(fù)合空間對象主要通過對基本空間對象或它們的拓撲部分進行幾何組合如合并和求差生成，空間對象組成部分間的拓撲關(guān)系約束對于構(gòu)建對象間的拓撲起著至關(guān)重要的作用。對于區(qū)A和區(qū)B，約束條件為A包含B，集的差的閉包就形成了有著一個洞的閉合區(qū)域（圖3（a））；對于區(qū)C和區(qū)D，如果C與D相離，那么將會形成一個封閉的分離區(qū)域（圖3（b））；對于區(qū)E、F和G，約束條件為E包含F(xiàn)，且E與G相離，將會得到一個帶洞區(qū)且在區(qū)外有一個分離部分（圖3（c））。

圖3 復(fù)合面狀對象的構(gòu)成Fig.3 Constitute a complex geometric objects

因此，根據(jù)復(fù)合面狀對象的構(gòu)成方法，可以將復(fù)合面狀對象分解成多個簡單區(qū)域，如圖4所示。圖中在計算復(fù)合面狀對象A與B的拓撲關(guān)系時，可以分解成簡單區(qū)域A1、A2、A3、A4與B的拓撲關(guān)系。

圖4 分解成簡單區(qū)域Fig.4 Broken down into a simple regional

以圖2中幾何對象為例，研究圖2（a）與圖2（b）中A與B的拓撲關(guān)系。

先將幾何對象A與B分解。A分解后的簡單區(qū)域包括A1、A2、A3、A4，由于B是簡單區(qū)域，分解后還是B，故幾何對象A與B的拓撲關(guān)系可以通過A1、A2、A3、A4與B的4個9－交集矩陣表示。這樣，就有R1、R2、R3、R4共4個9－交集矩陣。通過分析這4個9－交集矩陣的值就可以判斷復(fù)合面狀對象A與B的拓撲關(guān)系。

則圖2（a）中，4個9－交集矩陣分別為

圖2（b）中，4個9－交集矩陣分別為

通過比較可以發(fā)現(xiàn)，雖然圖2（a）與圖2（b）中復(fù)合面狀對象A與B都對應(yīng)同一個經(jīng)典9－交集矩陣（相離），但通過分解表示后，R1、R2、R3相同，R4不同，也即圖2（a）與圖2（b）拓撲關(guān)系的不同點的細節(jié)通過R4反映了出來，區(qū)分了圖2（a）與圖2（b）的不同拓撲關(guān)系。

擴展到一般情況，復(fù)合面狀對象A分解成p個簡單區(qū)域，復(fù)合面狀對象B分解成q個簡單區(qū)域，則總共需要p×q個9－交集矩陣。通過比較這p×q個9－交集矩陣來判別復(fù)合面狀對象A與復(fù)合面狀對象B的拓撲關(guān)系細節(jié)。需要指出的是，復(fù)合面狀對象分解成簡單區(qū)域后，需要對每個區(qū)域設(shè)定一個標(biāo)記，來指明簡單區(qū)域是否是洞。

3.2 分解成點集的9－交集模型

按照空間區(qū)域劃分方法［20］，對任意區(qū)域A，令（包括A－和Ah）分別表示其內(nèi)部、內(nèi)邊界（當(dāng)A不帶洞時為空）、外邊界、外部、洞（當(dāng)A不帶洞時為空）、補集。根據(jù)復(fù)合面狀對象的定義，復(fù)合面狀對象是由n個分離的可能帶洞的區(qū)域組成，因此按照復(fù)合面狀對象A分離的構(gòu)成部分分解成n個子集區(qū)域（可能帶洞）A1、A2、…、An，然后按照空間區(qū)域劃分方法分解為分別表示復(fù)合面狀對象n個子集的內(nèi)部、內(nèi)邊界、外邊界、外部、洞、補集（如圖5所示）。

圖5 分解成點集模型Fig.5 Decomposed into point set model

對于任意的復(fù)合面狀對象A、B首先被分解成n、m個子集區(qū)域，并按照空間區(qū)域的劃分方法，分解成其子集的內(nèi)部、內(nèi)邊界、外邊界、外部、洞、補集。

用一個4nm＋1位的二進制編碼Rij（i≥1、j≤3）代替9－交集矩陣中的值，用這個二進制位中的每位數(shù)值來區(qū)分子集的相交關(guān)系，最后綜合表示復(fù)合面狀對象A、B的拓撲關(guān)系，即

Rij的取值根據(jù)劃分后的點集來確定?？紤]R11，取代的是因此有共n×m個數(shù)值，最后加上一個整體的相交情況A0∩B0。為了區(qū)分整體與細節(jié)，本文采用┐（A0∩B0），即R11需要n×m＋1位來表示。同理，R12取代的是A0∩?B。對于邊界分成了內(nèi)邊界和外邊界的情況，?B共有2m種情況，因此R12需要2nm＋1位來表示。依此類推，可以總結(jié)R11需要nm＋1位（最?。?；R12、R13、R21、R31需要2nm＋1位；R22、R23、R32、R33需要4nm＋1位（最大）。

為了使9－交集矩陣各元素的數(shù)值形式相同，則二進制編碼Rij（i≥1、j≤3）需要4nm＋1位（最大）來表示，不足的用0來補充。Rij＝X4nmX4nm－1…X2nmX2nm－1…XnmXnm－1…X1X0。Rij（i≥1，j≤3）的取值如表1所示。

在實際情況中，根據(jù)分解后的n、m的值確定Rij元素取值表，然后根據(jù)表格確定Rij元素每位的值，形成二進制編碼9－交集矩陣，為了表示方便，可以把二進制編碼Rij轉(zhuǎn)換成十進制數(shù)值表示。

這里同樣以圖2中的幾何對象為例，研究圖2（a）與圖2（b）中A與B的拓撲關(guān)系。

首先將復(fù)合面狀對象A與B分解，A包括A1、A2，B分解后只有B，故這里n＝2、m＝1。因此，二進制編碼Rij（i≥1、j≤3）需要4nm＋1＝4×2×1＋1＝9位來表示。則Rij元素取值表如表2所示。

則圖2（a）中，二進制編碼Rij（i≥1、j≤3）分別為

R11＝000000001（二進制）＝1（十進制）

R12＝000000001（二進制）＝1（十進制）

R13＝000001010（二進制）＝10（十進制）

R21＝000000001（二進制）＝1（十進制）

R22＝000000001（二進制）＝1（十進制）

R23＝010101010（二進制）＝170（十進制）

R31＝000001010（二進制）＝10（十進制）

R32＝000100010（二進制）＝34（十進制）

R33＝010101010（二進制）＝170（十進制）

即圖2（a）中的9－交集矩陣為

同理，圖2（b）中的9－交集矩陣為

通過比較9－交集矩陣R1與R2，可以發(fā)現(xiàn)R1≠R2，也即圖2（a）與圖2（b）中的拓撲關(guān)系不同，區(qū)分了圖2（a）與圖2（b）的不同拓撲關(guān)系。

表1 Rij元素的取值Tab.1 The values of each element for Rij

表2 Rij元素的取值（n＝2，m＝1）Tab.2 The values of each element for Rij（n＝2，m＝1）

4 兩種擴展交集模型及經(jīng)典9－交集模型表達能力的比較

針對同一組復(fù)合面狀對象，通過兩種擴展交集模型及經(jīng)典9－交集模型來描述8種基本的拓撲關(guān)系，顯示擴展交集模型對每一個9－交集矩陣的細化，這里仍然選取圖2中所示的兩個復(fù)合面狀對象，討論其8種基本的拓撲關(guān)系（由于同一拓撲關(guān)系可能的物理解釋較多，只列舉其中兩種不同物理解釋），如表3所示。

表3 兩種擴展交集模型及經(jīng)典9－交集模型比較Tab.3 The intersection of the two expansion models and classic 9－intersection compare models

續(xù)表3

由于圖2中的兩個幾何對象不可能存在相等的拓撲，但為了表現(xiàn)兩種擴展交集模型及經(jīng)典9－交集模型的表達能力的區(qū)別，表3的相等拓撲關(guān)系選取了簡單的區(qū)域與一個帶洞的區(qū)域進行比較。

由比較可知，相對于經(jīng)典的9－交集模型，兩種擴展的交集模型都能更加準(zhǔn)確地表達出復(fù)合面狀對象各子部分之間的拓撲關(guān)系的細節(jié)。分析可知，分解成簡單區(qū)域和分解成點集兩種擴展方式均采用“分解”的思想，化繁為簡，但分解成簡單區(qū)域是按照OGC抽象規(guī)范［6］中對復(fù)合幾何結(jié)構(gòu)描述分解的，簡單區(qū)域是原子量；分解成點集是按照空間區(qū)域劃分方法［20］分解，點集是原子量。

5 結(jié)束語

為了表達復(fù)合面狀對象間的細節(jié)拓撲關(guān)系，對經(jīng)典9－交集模型進行了改進，本文給出了兩種基于分解思想的交集模型，并且用示例比較了兩種擴展交集模型及經(jīng)典9－交集模型的表達能力。結(jié)果表明，兩種擴展交集模型均能準(zhǔn)確地表達出復(fù)合面狀對象各子部分之間的拓撲關(guān)系的細節(jié)。分解成簡單區(qū)域的9－交集模型9－矩陣較多，表現(xiàn)形式不夠簡潔，影響存儲和分析效率；分解成點集的9－交集模型需要建立Rij元素取值表，由1bit擴充為（4nm＋1）bit，分析效率有待提高。因此，本研究下一步的工作主要集中于兩種擴展交集模型的優(yōu)化，提高分析效率，同時研究基于兩種擴展模型的相似性度量。

［1］LI Deren，GUAN Zequn.Integration and Implementation of Spatial Information Systems［M］.Wuhan：Wuhan University Press，2002.（李德仁，關(guān)澤群.空間信息系統(tǒng)的集成與實現(xiàn)［M］.武漢：武漢大學(xué)出版社，2002）

［2］EGENHOFER M J，F(xiàn)RANZOSA R D.Point－set Topological Spatial Relations［J］.International Journal of Geographical Information Systems，1991，5（2）：161－174.

［3］EGENHOFER M J，HERRING J R.Categorizing Binary Topological Relations between Regions，Curves and Points in Geographic Databases［R］.Orono：University of Maine，1991.

［4］CLEMENTINI E，F(xiàn)ELICE P D.A Comparison of Methods for Representing Topological Relationships［J］.Information Science，1994，80：1－34.

［5］CLEMENTINI E，F(xiàn)ELICE P D，OOSTEROM P V.A Small Set of Formal Topological Relationships Suitable for End－user Interaction［C］∥Advances in Spatial Databases：Proceedings of the third International Symposium.Singapore：Springer－Verlag，1993：277－295.

［6］Open GIS Consortium Inc.OpenGIS Simple Features Specification for SQL［S/OL］.rev 1.1.1999［2013－02－13］.http：∥www.opengis.org1

［7］EGENHOFER M J，CLEMENTINI E，F(xiàn)ELICE P D.Topological Relations between Regions with Holes［J］.International Journal of Geographical Information Systems，1994，8（2）：129－144.

［8］NGUYEN V H，PARENT C，SPACCAPIETRA S.Complex Regions in Topological Queries［C］∥Proceedings of the International Conference on Spatial Information Theory：COSIT97.Laurel Highlands：Springer－Verlag，1997.

［9］SCHNEIDER M，BEHR T.Topological Relationships between Complex Spatial Objects［J］.ACM Transactions on Database Systems，2006，31（1）：39－81.

［10］LI S J.A Complete Classification of Topological Relations Using the 9－intersection Method［J］.International Journal of Geographical Information Science，2006，20（6）：589－610.

［11］DU Xiaochu，HUANG Maojun.Description and Discrimination of Topological Relations between Uncertain Linear and Area Objects［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：340－350.（杜曉初，黃茂軍.不確定線－面拓撲關(guān)系的描述與判別［J］.測繪學(xué)報，2007，36（3）：340－350.）

［12］ZHONG Zhinong，TANG Zhengwu，ZHANG Fan，et al.A Unified Model of Distinguishing Topological Relationships［J］.Journal of National University of Defense Technology，2004，26（5）：57－62.（鐘志農(nóng)，唐征武，張帆，等.一種統(tǒng)一的拓撲關(guān)系判斷模型［J］.國防科技大學(xué)學(xué)報，2004，26（5）：57－62.）

［13］XUE Dan，ZUO Huaiyu，ZHONG Zhinong，et al.Mixed Geometric Features and Their Topological Relations［J］.Advanced Manufacture and Management，2008，27（7）：26－31.（薛丹，左懷玉，鐘志農(nóng)，等.混合幾何對象及其拓撲關(guān)系［J］.先進制造與管理，2008，27（7）：26－31.）

［14］ZHOU Tao，LU Huiling，YANG Deren，et al.Popularized“Egg－folk”Model［J］.Geomatics and Information Science of Wuhan University，2012，37（2）：242－246.（周濤，陸惠玲，楊德仁，等.“蛋－黃”模型的拓展研究［J］.武漢大學(xué)學(xué)報：信息科學(xué)版，2012，37（2）：242－246.）

［15］HUO Linlin.Research on Some Problems of Complex Spatial Relations Models and Spatial Description Logic［D］.Changchun：Jilin University，2013.（霍林林.復(fù)雜空間關(guān)系模型及空間描述邏輯中若干問題的研究［D］.長春：吉林大學(xué)，2013.）

［16］OUYANG Jihong，HUO Linlin，LIU Dayou，et al.Extended 9－intersection Model for Description of Topological Relations between Regions with Holes［J］.Journal of Jilin University：Engineering and Technology Edition，2009，39（6）：1595－1600.（歐陽繼紅，霍林林，劉大有，等.能表達帶洞區(qū)域拓撲關(guān)系的擴展9－交集模型［J］.吉林大學(xué)學(xué)報：工學(xué)版，2009，39（6）：1595－1600.）

［17］LI Jian，OUYANG Jihong，WANG Zhenxin.Topological Relational between a Region with Two Holes and a Simple Region［J］.Journal of Jilin University：Engineering and Technology Edition，2012，42（5）：1214－1218.（李健，歐陽繼紅，王振鑫.帶雙洞區(qū)域與簡單區(qū)域間的拓撲關(guān)系［J］.吉林大學(xué)學(xué)報：工學(xué)版，2012，42（5）：1214－1218.）

［18］LI Jian，OUYANG Jihong，WANG Guowei，et al.Representation for Topological Relations between a Region with a Hole and a Simple Region［J］.Journal of Jilin University：Science Edition，2012，50（6）：1209－1213.（李健，歐陽繼紅，王國偉，等.一個帶單洞區(qū)域和一個簡單區(qū)域間的拓撲關(guān)系表示［J］.吉林大學(xué)學(xué)報：理學(xué)版，2012，50（6）：1209－1213.）

［19］LI Jian，OUYANG Jihong，WANG Zhenxin，et al.Representation Model of Topological Relational among Three Simple Regions［J］.Journal of Jilin University：Engineering and Technology Edition，2013，43（1）：117－122.（李健，歐陽繼紅，王振鑫，等.三個簡單區(qū)域間的拓撲關(guān)系的表示模型［J］.吉林大學(xué)學(xué)報：工學(xué)版，2013，43（6）：117－122.）

［20］EGENHOFER M J，VASARDANI M.Spatial Reasoning with a Hole［C］∥Proceedings of the 8th International Conference on Spatial Information Theory.Heidelberg：Springer－Verlag，2007：303－320.