空間拓?fù)洳樵冄芯颗c實(shí)現(xiàn)

魯 磊，張紅波

(73603部隊(duì)，江蘇 南京210049)

一、引 言

空間數(shù)據(jù)庫(kù)作為現(xiàn)代數(shù)據(jù)庫(kù)的一個(gè)分支，已經(jīng)發(fā)展的比較成熟?？臻g拓?fù)潢P(guān)系是空間數(shù)據(jù)庫(kù)研究中的一個(gè)重要問題。空間對(duì)象間的拓?fù)潢P(guān)系、特性和操作已被廣泛討論。

本文在Topology Suite的基礎(chǔ)上，擴(kuò)展了空間拓?fù)洳僮黝悾岢隽俗约旱目臻g數(shù)據(jù)拓?fù)洳樵冋Z言以及在查詢結(jié)果顯示時(shí)用到的索引算法。并對(duì)這些工作進(jìn)行了系統(tǒng)的理論分析，在實(shí)際項(xiàng)目中對(duì)查詢語言進(jìn)行試驗(yàn)分析。分析結(jié)果表明，本文的拓?fù)洳樵冋Z言可以準(zhǔn)確高效的對(duì)空間數(shù)據(jù)進(jìn)行查詢與分析。

二、空間數(shù)據(jù)類型

開放空間信息協(xié)會(huì)(The Open Geospatial Consortium，OGC)組織各成員單位制定了一系列地理信息共享方面的標(biāo)準(zhǔn)，它是一個(gè)非盈利的、國(guó)際化的、自愿協(xié)商的標(biāo)準(zhǔn)化組織，其主要目的就是制定與空間信息、基于位置服務(wù)相關(guān)的標(biāo)準(zhǔn)。OGC的SFS(簡(jiǎn)單要素規(guī)范)APIS(application programming interfaces)規(guī)定了對(duì)點(diǎn)、線、面以及多點(diǎn)等簡(jiǎn)單要素的發(fā)布、存儲(chǔ)、讀取和簡(jiǎn)單操作。這些規(guī)范的目的是使得GIS軟件設(shè)計(jì)師在不同的技術(shù)下(OLE/COM，SQL，CORBA)能夠使用這些接口來操作由簡(jiǎn)單幾何要素組成的要素(如圖1所示)。

圖1 幾何對(duì)象模型

圖1顯示的是SFS中幾何對(duì)象的關(guān)系結(jié)構(gòu)，簡(jiǎn)單要素中的幾何對(duì)象主要就是定義了點(diǎn)、線、面和多點(diǎn)、多線、多面。曲線是基類，線和孔曲線的子類。幾何集也是基類，復(fù)合線，復(fù)合面都是幾何集的子類。幾何體是基類，所有的空間類型都是幾何體的子類。

三、空間關(guān)系

空間拓?fù)潢P(guān)系描述空間對(duì)象之間在拓?fù)渥兓碌牟蛔冴P(guān)系，是空間數(shù)據(jù)研究中最廣泛并且解決方案最完備的一種關(guān)系?？臻g對(duì)象之間的拓?fù)潢P(guān)系包括點(diǎn)/點(diǎn)關(guān)系(P/P)、點(diǎn)/線關(guān)系(P/L)、點(diǎn)/面關(guān)系(P/A)、線/線關(guān)系(L/L)、線/面關(guān)系(L/A)和面/面關(guān)系(A/A)，這些關(guān)系表現(xiàn)了對(duì)象間的相鄰性、連接性、關(guān)聯(lián)性、閉合性、包含性和一致性等，是對(duì)空間數(shù)據(jù)進(jìn)行查詢處理的依據(jù)［1］。

對(duì)于空間對(duì)象之間的拓?fù)潢P(guān)系的描述，主要有基于點(diǎn)集拓?fù)鋵W(xué)的拓?fù)淠Ｐ秃突趫D論的拓?fù)淠Ｐ??；邳c(diǎn)集拓?fù)鋵W(xué)的空間拓?fù)潢P(guān)系描述有3種方法：Egenhofer提出的四交模型和九交模型［2］以及擴(kuò)展九交模型。基于點(diǎn)集拓?fù)鋵W(xué)的空間關(guān)系描述框架能夠十分有效地描述有公共元素的空間目標(biāo)間的拓?fù)潢P(guān)系，甚至能夠根據(jù)交集的維數(shù)更進(jìn)一步區(qū)分成為各種不同形式。

九交模型實(shí)現(xiàn)了空間對(duì)象之間的拓?fù)潢P(guān)系描述。該模型主要以點(diǎn)集拓?fù)鋵W(xué)為基礎(chǔ)，用兩個(gè)對(duì)象的內(nèi)部(Ao)、邊界(?A)與外部(A－)子集是否相交來刻畫兩個(gè)對(duì)象間的拓?fù)潢P(guān)系。具體的可用九交矩陣來表示，即

集合有相交(1)和不相交(0)兩種情況?？梢詤^(qū)分29=512種不同的情況。

四、基于Topology Suite的空間拓?fù)洳樵儗?shí)現(xiàn)

為實(shí)現(xiàn)空間對(duì)象存儲(chǔ)，本文引入自定義的空間數(shù)據(jù)類型，使用的空間抽象數(shù)據(jù)類型包括非實(shí)例化的基類Geometry和基本派生類 Point、Curve、Surface和Geometrycollection等，同時(shí)規(guī)定了與派生類相適應(yīng)的空間參考系。本文還擴(kuò)展SQL使之包含空間關(guān)系謂詞，根據(jù)OGC的簡(jiǎn)單要素規(guī)范，定義了空間對(duì)象之間的關(guān)系和空間分析功能，通過采用C#開發(fā)語言實(shí)現(xiàn)空間拓?fù)涮幚砗瘮?shù)，從而支持空間查詢。在得到查詢結(jié)果數(shù)據(jù)后，通過空間R樹索引，將查詢結(jié)果以地圖形式返回給客戶。

1.拓?fù)洳樵兛臻g操作類

本文采用維擴(kuò)展九交模型處理幾何體間的拓?fù)潢P(guān)系，使用關(guān)聯(lián)算法實(shí)現(xiàn)基于維擴(kuò)展九交模型的拓?fù)浣Y(jié)構(gòu)計(jì)算。首先設(shè)計(jì)了數(shù)據(jù)結(jié)構(gòu)，定義了相關(guān)的空間操作類。如圖2所示，主要包括：①Geometry類，定義最基本的幾何體對(duì)象和基本屬性(如坐標(biāo)序列、面積、最小外包矩形等)及拓?fù)潢P(guān)系判斷方法;②IntersectionMatrix類，用于描述維擴(kuò)展九交矩陣及匹配的字符串;③geometrygraph類，用于構(gòu)建兩個(gè)幾何體對(duì)象的拓?fù)浣Y(jié)構(gòu)圖，拓?fù)浣Y(jié)構(gòu)圖由Node和Edge組成，分別對(duì)應(yīng)幾何體的節(jié)點(diǎn)和邊線，每個(gè)成員以標(biāo)簽表示其相對(duì)于幾何體的拓?fù)湮恢?，以幾何體a的節(jié)點(diǎn)a1為例：如下圖，a的一個(gè)節(jié)點(diǎn)a1內(nèi)含于 b，則得出 a1標(biāo)簽為{a：ebi;b：iii}(e，b，i分別表示外部、邊界、內(nèi)部);④Dimension類定義平面二維幾何對(duì)象維度;⑤Location類定義矩陣行列與幾何體內(nèi)部、外部、及邊界的關(guān)系。

圖2 拓?fù)洳樵兛臻g操作類

2.空間查詢語言設(shè)計(jì)

作為與數(shù)據(jù)庫(kù)交互的主要手段，查詢語言是數(shù)據(jù)庫(kù)管理系統(tǒng)的一個(gè)核心要素。SQL是用于關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)的一種常見的商業(yè)查詢語言，具有通用性強(qiáng)，直觀便捷的特點(diǎn)。由于空間數(shù)據(jù)庫(kù)系統(tǒng)是一種擴(kuò)充的數(shù)據(jù)庫(kù)管理系統(tǒng)，既可以處理空間數(shù)據(jù)，也可以處理非空間數(shù)據(jù)，所以通過擴(kuò)展SQL語言來支持空間數(shù)據(jù)比較好的選擇。本文主要從增加抽象數(shù)據(jù)類型和空間謂詞等方面擴(kuò)展了標(biāo)準(zhǔn)的關(guān)系查詢語言SQL，以滿足空間數(shù)據(jù)查詢的要求。如表1所示，根據(jù)OGC的簡(jiǎn)單要素規(guī)范，定義了空間對(duì)象之間的關(guān)系和空間分析功能，通過自定義函數(shù)的形式，將這些功能加以實(shí)現(xiàn)。

表1 空間謂詞擴(kuò)展函數(shù)功能

利用上述運(yùn)算函數(shù)可以很方便的構(gòu)造空間查詢語句。例如查詢中國(guó)政區(qū)內(nèi)所有城市：select cities.* from cities，countries where countries.Name='China'and Within(cities.Sysgeometry，countries.Sys-Geometry)='true'。其中，空間數(shù)據(jù)的操作函數(shù)存儲(chǔ)在HashTable中。以相交為例：Hashtable_functions;_functions.Add("Intersects"，"TerraNova.NetTopology-Suite.Geometries.Geometry.Intersects")。

3.空間數(shù)據(jù)拓?fù)洳樵兞鞒?/h3>

利用關(guān)聯(lián)算法計(jì)算幾何體之間的拓?fù)潢P(guān)系分為5個(gè)步驟(如圖3所示);①建立幾何體對(duì)象的拓?fù)浣Y(jié)構(gòu)圖，拓?fù)浣Y(jié)構(gòu)圖包含了對(duì)應(yīng)幾何體的節(jié)點(diǎn)和邊線，其中每個(gè)節(jié)點(diǎn)和每條邊線都被標(biāo)志其相對(duì)于原幾何體的拓?fù)湮恢?②初始化幾何體對(duì)象的交集矩陣。實(shí)例化交集矩陣模型對(duì)象，將其字符串設(shè)為默認(rèn)值“＊＊＊＊＊＊＊＊＊”;③獲取兩個(gè)幾何體間的交集，可利用單調(diào)鏈方法快速精確地求出交集，將幾何體的邊線分解成單調(diào)鏈，使用雙交點(diǎn)法簡(jiǎn)單求出兩條單調(diào)鏈之間的交點(diǎn)，即為幾何體之間交集的節(jié)點(diǎn)，添加到拓?fù)浣Y(jié)構(gòu)圖中;④在幾何體間的交集部分插入節(jié)點(diǎn)，并已添加到拓?fù)浣Y(jié)構(gòu)圖中之后，通過拓?fù)浣Y(jié)構(gòu)圖成員的標(biāo)簽，計(jì)算交集節(jié)點(diǎn)的標(biāo)簽，再計(jì)算幾何體的拓?fù)浣Y(jié)構(gòu)圖中獨(dú)立元件的標(biāo)簽，獨(dú)立元件是指該幾何體中與其他幾何體不相交的節(jié)點(diǎn)或邊線;⑤根據(jù)拓?fù)浣Y(jié)構(gòu)圖中所有成員的標(biāo)簽更新交集矩陣。

圖3 空間數(shù)據(jù)拓?fù)洳樵兲幚砹鞒?/p>

五、系統(tǒng)試驗(yàn)和應(yīng)用

1.試驗(yàn)數(shù)據(jù)準(zhǔn)備

試驗(yàn)數(shù)據(jù)采用ESRI(美國(guó)環(huán)境系統(tǒng)研究所)提供的世界地圖數(shù)據(jù)(該數(shù)據(jù)的制作時(shí)間為1980年)作為輸入，格式為SHP格式。

試驗(yàn)分為兩組，一組是空間關(guān)系的查詢，以求中國(guó)政區(qū)內(nèi)的城市為例;另一組是空間操作的查詢，以求中國(guó)和蒙古合并后的形狀為例。

2.空間關(guān)系查詢

為了對(duì)空間數(shù)據(jù)拓?fù)洳樵冞M(jìn)行正確性進(jìn)行評(píng)估，結(jié)合課題組已有的空間關(guān)系查詢方法，在實(shí)際項(xiàng)目中進(jìn)行了測(cè)試。下面就以求全球數(shù)據(jù)中中國(guó)政區(qū)內(nèi)所有的城市為例。

首先需要從數(shù)據(jù)庫(kù)中獲取城市數(shù)據(jù)和中國(guó)政區(qū)數(shù)據(jù)?？梢耘卸ǔ鞘袛?shù)據(jù)為一個(gè)點(diǎn)集，設(shè)為幾何體a;中國(guó)政區(qū)數(shù)據(jù)則為一個(gè)區(qū)域，設(shè)為幾何體b，則本例求的是幾何體a相交幾何體b的部分?jǐn)?shù)據(jù)。圖4是全球的城市分布圖。

圖4 全球的城市分布數(shù)據(jù)圖

例1：求出中國(guó)政區(qū)內(nèi)所有的城市，可以用以下SQL語句進(jìn)行查詢：

上述查詢的文字結(jié)果如圖5所示，共65條數(shù)據(jù)。

圖5 實(shí)際結(jié)果記錄

3.空間操作查詢

為了對(duì)空間分析算法的正確性進(jìn)行評(píng)估，下面就以求中國(guó)和蒙古合并后的形狀為例。

首先從整體上分析中國(guó)和蒙古兩個(gè)國(guó)家的形狀。執(zhí)行 SQL語句如下：Select* From Countries Where Countries.Name='China'Or Countries.Name='Mongolia'。

上述查詢的文字結(jié)果共有兩條記錄，如圖6所示。

圖6 實(shí)際查詢結(jié)果文字記錄?

例2：求中國(guó)和蒙古兩個(gè)國(guó)家合并后的形狀。求解該查詢可執(zhí)行如下語句序列。

中國(guó)和蒙古合并后共一條記錄，文字結(jié)果如圖7所示。

圖7 文字結(jié)果

六、結(jié)束語

空間數(shù)據(jù)庫(kù)技術(shù)由于其在商業(yè)領(lǐng)域和軍事應(yīng)用等各方面的巨大前景，已成為數(shù)據(jù)庫(kù)技術(shù)研究與發(fā)展的熱點(diǎn)。其中，拓?fù)潢P(guān)系的描述與判斷在空間數(shù)據(jù)建模、空間數(shù)據(jù)查詢、分析和數(shù)據(jù)更新等方面起著重要的作用。本文在研究空間拓?fù)潢P(guān)系描述模型的基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)的空間數(shù)據(jù)庫(kù)拓?fù)洳樵兣c索引功能，性能較高，應(yīng)用方便，對(duì)進(jìn)一步開發(fā)新型空間數(shù)據(jù)庫(kù)系統(tǒng)具有重要意義。

［1］陳軍，趙仁亮.GIS空間關(guān)系的基本問題與研究進(jìn)展［J］.測(cè)繪學(xué)報(bào)，1999，5(2)：95-102.

［2］張駿，秦小麟，包磊.一種三維空間9-交模型的簡(jiǎn)化方法［J］.南京航空航天大學(xué)學(xué)報(bào)，2006，38(3)：255-261.