混合幾何對象的拓撲關系集合

信息系統(tǒng)（gis）是一個數據信息系統(tǒng)，用于收集、存儲、管理、分析和描述空間和地理分布。它把空間對象的地理位置和相關屬性有機結合起來,借助其獨有的空間分析功能和可視化表達,輔助用戶進行各種決策。GIS系統(tǒng)一般通過空間查詢語言來表述用戶的空間查詢和空間分析的請求,從而使用戶能夠與GIS系統(tǒng)進行交互。因此,設計一種簡單易用、功能強大的空間查詢語言一直是GIS技術研究的一個重要內容。近年來,在這個領域已經進行了大量的研究工作,它們的主要思想都是通過引入空間數據類型和空間操作算子來擴展SQL語言,使用戶能根據空間關系來查詢空間對象。其中最重要的進展是SQL3多媒體規(guī)范(SQL3/MM)和業(yè)界標準——OpenGISSQL實現規(guī)范(OpenGISSimpleFeaturesSpecificationforSQL)的制定,這兩個規(guī)范都定義了一系列的空間數據類型和空間關系,為空間查詢語言的設計和開發(fā)提供了一個框架?？臻g查詢語言中的空間關系主要包括拓撲關系、方向關系和度量關系等。其中拓撲關系是指那些在拓撲變換(如平移、旋轉、縮放)中保持不變的性質,主要描述空間對象間是否相鄰、包含、重疊。拓撲關系作為一種重要的空間關系,廣泛應用于空間分析和查詢中。1拓撲關系集合的定義拓撲關系集合是在概念層上,根據人們對拓撲關系的理解,以自然語言的方式定義的一些命名的拓撲關系及其語義,方便人們進行空間查詢和空間推理。拓撲關系集合的定義必須滿足以下兩個基本性質:互斥性:兩個空間對象之間的拓撲關系不能同時被拓撲關系集合中兩個不同的關系所定義;完備性:任何空間對象之間的拓撲關系都要能被拓撲關系集合中所定義的關系所描述。目前拓撲關系集合的定義主要有:基于9交集模型定義的8個拓撲關系,它主要描述簡單面對象之間的拓撲關系;CBM(Calculus-basedMethod)定義了5個關系,它可以描述簡單點、線、面,復雜點、線、面以及多點、多線、多面等幾何對象間的拓撲關系;RCC(RegionCollectionCalculus)主要描述面對象之間的關系,用于空間推理。另外一個重要的進展是OGC(OpenGISConsortium)制定的業(yè)界標準——OpenGISSQL,它定義了8個拓撲關系算子,可用來描述簡單點、線、面,復雜點、線、面以及多點、多線、多面等幾何對象間的拓撲關系。其中OpenGISSQL規(guī)范中的拓撲關系集合的定義是目前最完整、最全面的定義。但通過分析可以發(fā)現OpenGISSQL對拓撲關系的定義還存在著以下的不足:(1)不滿足相互排斥圖1中(a)和(b)兩種情況都同時滿足OpenGISSQL中Touches和Crosses的定義,因此它不滿足互斥性。(2)拓撲關系定義不完整現實世界中存在這樣一類空間對象,它們的空間描述可能由點、線或面對象共同組合而成,如重點工程可能由油井(點對象)、公路(線對象)和湖泊治理(面對象)組成。而目前所有的拓撲關系定義都不能描述此類空間對象之間的拓撲關系(包括OpenGISSQL規(guī)范),因此當前的拓撲關系研究還不完備?；谝陨贤負潢P系集合定義中的不足,本文引入了混合幾何對象的概念,以混合幾何對象為基礎,對OpenGISSQL中的拓撲關系的定義和范疇進行了擴充,定義了一個由7個拓撲關系組成的互斥、完備的拓撲關系集合,使其能夠描述那些由不同維幾何對象組成的復雜幾何對象之間的拓撲關系,為空間查詢語言中的拓撲關系集合的定義提供了統(tǒng)一的框架。2混合幾何對象概念地理信息系統(tǒng)中一般采用幾何對象來描述空間實體的空間信息。由于空間實體的復雜性,地理信息系統(tǒng)中的幾何對象主要分為兩大類:簡單幾何對象和復雜幾何對象。簡單幾何對象包括簡單點、簡單線和簡單多邊形。復雜幾何對象又可以分為三類:Ⅰ類:單一的非簡單幾何對象。如復雜線(自交叉的線,多于兩個端點的線)、復雜多邊形(帶洞的多邊形)。Ⅱ類:由同維幾何對象構成的組合幾何對象。如多點、多線和多多邊形。Ⅲ類:由不同維的幾何對象構成的組合幾何對象。目前拓撲關系的定義還不能對第三類復雜幾何對象之間的拓撲關系進行描述,如OpenGISSQL規(guī)范只能表述Ⅰ類、Ⅱ類復雜幾何對象的拓撲關系。為了使拓撲關系研究趨于完備,本文引入了混合幾何對象的概念,作為描述第三類復雜幾何對象拓撲關系的基礎。約定:P表示0維幾何對象(簡單點或Ⅱ類復雜點);L表示1維幾何對象(簡單線或Ⅰ類、Ⅱ類復雜線);A表示2維幾何對象(簡單多邊形或Ⅰ類、Ⅱ類復雜多邊形)。定義混合幾何(MixedGeometry):混合幾何是由點(簡單點或Ⅱ類復雜點)、線(簡單線或Ⅰ類、Ⅱ類復雜線)或多邊形(簡單多邊形或Ⅰ類、Ⅱ類復雜多邊形)等不同維幾何元素組成的復雜幾何對象,并且具有以下性質:(1)混合幾何對象的任何兩個子元素的內部不相交;?O∈MixedGeometry,?Pi,Pj∈O,i≠j,I(Pi)∩I(Pj)=>(2)一個子元素的內部不能與另一個子元素的邊界相交;?O∈MixedGeometry,?Pi,Pj∈O,i≠j,I(Pi)∩B(Pj)=>(3)任何兩個子元素的邊界只能在有限個點上重疊;?O∈MixedGeometry,?Pi,Pj∈O,i≠j,Bi=B(Pi),Bj=B(Pj)(Bi∩Bj)?{P1,…,Pk|Pi∈point,1≤i≤k}(4)混合幾何的邊界由其子元素的邊界組成,它的內部為此混合幾何去掉邊界后的點組成。其中I()、B()分別表示一個幾何對象的內部、邊界。根據混合幾何對象的定義,混合幾何對象O可以表述為:O?{P,L,A},即O由P、L或A組成,P、L、A分別代表對象O的點、線、面部分,并且P、L、A只能在有限個點上重疊。當混合幾何對象的子元素是同維對象時,混合幾何對象則轉換為多點、多線或多面對象。3對于混合幾何對象,ab=a,bb混合幾何對象是由不同維幾何對象構成的復雜幾何對象。對于混合幾何對象之間的拓撲關系,我們擴充和重定義了OpenGISSQL規(guī)范中的拓撲關系定義,定義了一個由7個拓撲關系組成的集合C:{disjoint,touches,within,crosses,overlaps,contains,equal}。具體定義如下:disjoint:對于混合幾何對象a和b,a?{P,L,A},b?{P,L,A}。a.disjoint(b)?a∩b=>touches:對于混合幾何對象a和b,a?{P,L,A},b?{P,L,A}。a.touches(b)?(I(a)∩I(b)=>)∧(a∩b≠>)within:對于混合幾何對象a和b,a?{P,L,A},b?{P,L,A}。a.within(b)?(a∩b=a)∧(I(a)∩I(b)≠>)∧(a≠b)wrosses:對于混合幾何對象a和b,a?{P,L},b?{P,L,A}。a.crosses(b)?(a∩b≠a)∧(a∩b≠b)∧(I(a)∩I(b)≠>)∧(?aαbβ)(I(aα)∩I(bβ)≠>→(dim(I(aα)∩I(bβ))<max(dim(I(aα)),dim(I(bβ)))∧(aα∩bβ≠aα)∧(aα∩bβ≠bβ)α∈{p,l},β∈{p,l,a}overlaps:對于混合幾何對象a和b,a?{P,L,A},b?{P,L,A}。a.overlaps(b)?(a∩b≠a)∧(a∩b≠b)∧(I(a)∩I(b)≠>)∧((dim(a)=2)∨(?aαbβ)((dim(I(aα))=dim(I(bβ))=dim(I(aα)∩(bβ)))∨(aα∩bβ=aα)∨(aα∩bβ=bβ))α,β∈{p,l,a}contains:a.contains(b)?b.within(a)。equal:a.equal(b)?a=b。式中,ap、al和aa分別表示混合幾何對象a的點部分、線部分和面部分。dim()算子表示求對象的最大維數。4空間查詢語言中拓撲關系的定義對于第Ⅲ類復雜幾何對象,其子元素之間可能互相重疊,為了明確獲取此對象的內部、外部、邊界以及它的各個組成部分(點部分、線部分和面部分),首先必須對其進行處理,把其規(guī)則化為混合幾何對象,這樣就可以使用上述拓撲關系的定義來描述第Ⅲ類復雜幾何對象間的拓撲關系。當使用拓撲關系集合C來描述第Ⅰ、Ⅱ類復雜幾何對象或簡單幾何對象之間的拓撲關系時,C就等同于OpenGISSQL中對拓撲關系的定義。因此本文所定義的拓撲關系可以對所有空間對象之間的拓撲關系進行描述,為空間查詢語言中拓撲關系的定義提供了一個統(tǒng)一的框架。下面將證明拓撲關系集合C是互斥和完備的。(1)拓撲關系集合c的互斥證明對于兩個空間對象a,b和拓撲關系集合C中的任意兩個不同的關系r1、r2,如果a,b的拓撲關系為r1,則a,b的拓撲關系不滿足r2,即:r1,r2∈C,r1≠r2,(ar1b)=T?(ar2b)=F證明:此命題的證明采用類似文獻中的證明方法。命題的證明分為7個部分,每一個部分分別證明拓撲關系集合C中的一個關系與其它6個關系是互斥的。其形式如下:Part1:(aoverlapsb)?(?(atouchesb))∧(?(awithinb))∧(?(acrossesb))∧(?(adisjointb))∧(?(acontainsb))∧(?(aequalb))本文只對上面這個部分進行證明,其它6個部分可以使用相似的方法證明。(a)根據定義a.overlaps(b)?(a∩b≠a)∧(a∩b≠b)∧(I(a)∩I(b)≠>)?(?(atouchesb))∧(?(awithinb))∧(?(adisjointb))∧(?(acontainsb))∧(?(aequalb))(b)如果dim(a)=2,根據crosses的定義,a?{P,L},即dim(a)≤1,則(aoverlapsb)??(acrossesb);(c)如果dim(I(aα))=dim(I(bβ))=dim(I(aα)∩I(bβ)),而在crosses的定義中,0≤dim(I(aα)∩I(bβ))<max(dim(I(aα)),dim(I(bβ))),所以可證?(acrossesb);(d)如果(aα∧bβ=aα)∨(aα∩bβ=bβ)成立,而在crosses中必須滿足(aα∩bβ≠aα)∧(aα∩bβ≠bβ),因此可證?(acrossesb);由上可證Part1成立。同樣可以證明其它6個部分。因此可以證明拓撲關系集合C是互斥的。這樣就可以使用拓撲關系集合C中定義的關系來描述圖1中(a)、(b)的拓撲關系。根據定義,(a)、(b)中a、b之間的關系都為touches。(2)相關定義中的做任意兩個空間對象a,b的拓撲關系r,必定可以用拓撲關系集合C中的一個關系進行描述,即:(arb)=T?r∈C。證明:此命題的證明可以分為兩個部分。第一個部分證明如果I(a)∩I(b)=>,則r∈{disjoint,touches};第二個部分證明如果I(a)∩I(b)≠>,則r∈{within,crosses,overlaps,contains,equal}。Part1:I(a)∩I(b)=>?r∈{disjoint,touches}I(a)∩I(b)=>又存在兩種情況:①如果a∩b=>,根據定義則(adisjointb);②如果a∩b≠>,則(atouchesb)。因此Part1成立。Part2:I(a)∩I(b)≠>?r∈{within,crosses,overlaps,contains,equal}當I(a)∩I(b)≠Φ時,存在以下幾種情況:(a)a=b,根據定義則(aequalb)。(b)a≠b,如果a∩b=a,則(awithinb);如果a∩b=b,則(acontainsb)。(c)(a∩b≠a)∧(a∩b≠b);考慮以下情況:①當dim(a)=2時,則(aoverlapsb);②如果a,b中存在子元素,使得(aα∧bβ=aα)∨(aα∩bβ=bβ),則(aoverlapsb);③如果不存在(aα∧bβ=aα)∨(aα∩bβ=bβ),即對于所有aα,bβ,(aα∧bβ≠aα)∧(aα∩bβ≠bβ),又由于I(a)∩I(b)≠Φ,所以總存在I(aα)∩I(bβ)≠>,這時又存在兩種情況:(ⅰ)如果存在dim(I(aα))=dim(I(bβ))=dim(I(aα)∩I(bβ))時,則(aoverlapsb);(ⅱ)如果對于所有的I(aα)∩I(bβ)≠>,都存在dim(I(aα)∩I(bβ))<max(dim(I(aα)),dim(I(bβ))),則(acrossesb)。由(a)、(b)、(c)可以得到Part2成立。因此由Part1和Part2,可以證明拓撲關系集合C是完備的。5混合幾何對象概念的引入空間查詢語言與一般查詢語言的一個重要區(qū)別是,空間查詢語言提供了一系列空間關系算子,使用戶能根據空間關系來查詢空間數據庫。拓撲關系作為一種重要的空間關系,被廣泛應用于空間查詢和空間分析中。因此在概念層上,定義一個完備和互斥的、可以嵌入到空間查詢語言中的拓撲關系集合有著非常重要的意義。當前,對拓撲