[發明專利]一種地理實體拓撲關系的代數結構表達方法

有效

• 申請號: 201210486589.1
• 申請日: 2012-11-26
• 公開（公告）號: CN102982146A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 陳江平;史文中;張鵬林
• 申請（專利權）人: 武漢大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 薛玲

技術領域

本發明屬于GIS空間分析技術領域，特別涉及一種地理實體拓撲關系的代數結構表達方法。

背景技術

現有技術中，表達空間實體之間拓撲關系的方式一般有兩種，一種是顯式表示，另一種是隱式表示。顯式表示就是在存儲空間實體的屬性信息時，同時也存儲它們之間的拓撲信息；而隱式表示方法在存儲空間實體屬性信息的時候并不存儲它們的拓撲信息，而是在需要時根據屬性信息實時計算生成。不管是顯式表示還是隱式表示，其實質都是根據構成空間實體的點要素的坐標計算得到的，缺點就是計算量較大，速度較慢。不同的是，顯式表示的方式是預先計算出空間實體間的拓撲關系，并將其連同其他屬性信息一起存儲，這顯然會浪費存儲空間，而且一旦拓撲關系出現變化，必會產生連動效應，以致影響到整個空間數據的組織，最終導致所有的拓撲關系都必須重建，費時費力。現在一般的主流GIS軟件在存儲數據時都不再保留拓撲信息，而是在需要的時候實時計算生成。但無論如何，計算費時和拓撲重構的連動效應這兩個突出問題是傳統方法所無法避免的。

發明內容

針對背景技術存在的問題，本發明提供一種地理實體拓撲關系的代數結構表達方法。

為解決上述技術問題，本發明采用如下技術方案。

一種地理實體拓撲關系的代數結構表達方法，包括以下步驟，

步驟1：將地理圖形數據轉化為圖形單元，對圖形單元編號；

步驟2：根據圖形單元生成代數結構矩陣；

步驟3：根據所生成的代數結構矩陣判斷圖形單元之間的拓撲關系；

步驟4：根據拓撲關系生成圖形單元之間的拓撲關系矩陣。

所述的圖形單元包括點單元、線單元、面單元中的一種或其組合。

所述的代數結構矩陣為線單元代數結構矩陣。

下面對本方法及其理論作具體說明：

（1）單元代數結構的基本概念

A)論域

如果線單元的索引碼設為非零整數，則代數結構的研究論域D可表示為：D=(+1,-1,…，+i,-i,…，+n,-n)，其中0＜i≤n，n表示線單元的個數；稱+i,-i為空間圖形的單元變量x。

B)置換函數

給定單元變量x∈D，如果y=a_i(x)，且y∈E，E表示線單元的單元子集，則稱a_i是x的置換函數，i的值稱為階數。例如，若i=1則稱為x的一階置換；同時，若有a(x)=a[a(x)]=x，則又稱a是x的對合。

最基本也是最重要的置換函數就是零階置換和一階置換。把單元變量+x到-x或者-x到+x的組合，稱為代數結構的0階置換a₀(x)。按照逆時針方向，如單元變量x與y是鄰接的，x到y的組合[x,y=a₁(x)]則可以給出線單元的鄰接點，則稱a₁(x)為單元變量x的一階置換。

C)代數結構

單元變量的置換函數a_i和論域D組成了空間圖形的代數結構，表示為M={D,a₀，a₁，…，a_n}。a_i與階的大小有關，只要函數的階不同，單元變量可導致不同形態的單元映射。例如，圖1中的圖形單元的代數結構可以用表1來表示。

表1單元變量的代數結構

在記錄單元變量的一階置換時，只需要記錄該單元變量按逆時針方向旋轉遇到的第一個單元變量即可，而不需記錄在改點處鄰接的所有單元變量；這是因為在此處鄰接其他的單元變量可由單元代數結構矩陣隱含給出。例如，在圖1中，線單元1、5、2是在一點相鄰接的，所以這三個單元變量的一階置換應該是a₁(1)=a₁(5)=a₁(2)={1,5,2}，本發明中只記錄按逆時針方向旋轉遇到的第一個單元變量，即a₁(1)=5，a₁(5)=2，a₁(2)=1，由此就可以知道線單元1、5、2是相鄰接的。

（2）單元形態的表達方法

Ⅰ.點的表示

線單元變量的一階置換可以給出該線單元的鄰接點，所以點單元也就是用在該點處鄰接的任一單元變量的一階置換來表示的，它與拓撲結點的概念也是完全等價的。例如，在圖2中，線單元1、2、5在一點處是相鄰接的，用其中的任何一個單元變量的一階置換來表示該點，若選擇單元變量x=2，則該結點N可表示為N(2)={1,5,2}，

Ⅱ.線的表示