空間拓撲查詢研究與實現

魯 磊，張紅波

(73603部隊，江蘇 南京210049)

一、引 言

空間數據庫作為現代數據庫的一個分支，已經發展的比較成熟。空間拓撲關系是空間數據庫研究中的一個重要問題。空間對象間的拓撲關系、特性和操作已被廣泛討論。

本文在Topology Suite的基礎上，擴展了空間拓撲操作類，提出了自己的空間數據拓撲查詢語言以及在查詢結果顯示時用到的索引算法。并對這些工作進行了系統的理論分析，在實際項目中對查詢語言進行試驗分析。分析結果表明，本文的拓撲查詢語言可以準確高效的對空間數據進行查詢與分析。

二、空間數據類型

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

圖1 幾何對象模型

圖1顯示的是SFS中幾何對象的關系結構，簡單要素中的幾何對象主要就是定義了點、線、面和多點、多線、多面。曲線是基類，線和孔曲線的子類。幾何集也是基類，復合線，復合面都是幾何集的子類。幾何體是基類，所有的空間類型都是幾何體的子類。

三、空間關系

空間拓撲關系描述空間對象之間在拓撲變化下的不變關系，是空間數據研究中最廣泛并且解決方案最完備的一種關系。空間對象之間的拓撲關系包括點/點關系(P/P)、點/線關系(P/L)、點/面關系(P/A)、線/線關系(L/L)、線/面關系(L/A)和面/面關系(A/A)，這些關系表現了對象間的相鄰性、連接性、關聯性、閉合性、包含性和一致性等，是對空間數據進行查詢處理的依據［1］。

對于空間對象之間的拓撲關系的描述，主要有基于點集拓撲學的拓撲模型和基于圖論的拓撲模型。基于點集拓撲學的空間拓撲關系描述有3種方法：Egenhofer提出的四交模型和九交模型［2］以及擴展九交模型。基于點集拓撲學的空間關系描述框架能夠十分有效地描述有公共元素的空間目標間的拓撲關系，甚至能夠根據交集的維數更進一步區分成為各種不同形式。

九交模型實現了空間對象之間的拓撲關系描述。該模型主要以點集拓撲學為基礎，用兩個對象的內部(Ao)、邊界(?A)與外部(A－)子集是否相交來刻畫兩個對象間的拓撲關系。具體的可用九交矩陣來表示，即

集合有相交(1)和不相交(0)兩種情況。可以區分29=512種不同的情況。

四、基于Topology Suite的空間拓撲查詢實現

為實現空間對象存儲，本文引入自定義的空間數據類型，使用的空間抽象數據類型包括非實例化的基類Geometry和基本派生類 Point、Curve、Surface和Geometrycollection等，同時規定了與派生類相適應的空間參考系。本文還擴展SQL使之包含空間關系謂詞，根據OGC的簡單要素規范，定義了空間對象之間的關系和空間分析功能，通過采用C#開發語言實現空間拓撲處理函數，從而支持空間查詢。在得到查詢結果數據后，通過空間R樹索引，將查詢結果以地圖形式返回給客戶。

1.拓撲查詢空間操作類

本文采用維擴展九交模型處理幾何體間的拓撲關系，使用關聯算法實現基于維擴展九交模型的拓撲結構計算。首先設計了數據結構，定義了相關的空間操作類。如圖2所示，主要包括：①Geometry類，定義最基本的幾何體對象和基本屬性(如坐標序列、面積、最小外包矩形等)及拓撲關系判斷方法;②IntersectionMatrix類，用于描述維擴展九交矩陣及匹配的字符串;③geometrygraph類，用于構建兩個幾何體對象的拓撲結構圖，拓撲結構圖由Node和Edge組成，分別對應幾何體的節點和邊線，每個成員以標簽表示其相對于幾何體的拓撲位置，以幾何體a的節點a1為例：如下圖，a的一個節點a1內含于 b，則得出 a1標簽為{a：ebi;b：iii}(e，b，i分別表示外部、邊界、內部);④Dimension類定義平面二維幾何對象維度;⑤Location類定義矩陣行列與幾何體內部、外部、及邊界的關系。

圖2 拓撲查詢空間操作類

2.空間查詢語言設計

作為與數據庫交互的主要手段，查詢語言是數據庫管理系統的一個核心要素。SQL是用于關系數據庫管理系統的一種常見的商業查詢語言，具有通用性強，直觀便捷的特點。由于空間數據庫系統是一種擴充的數據庫管理系統，既可以處理空間數據，也可以處理非空間數據，所以通過擴展SQL語言來支持空間數據比較好的選擇。本文主要從增加抽象數據類型和空間謂詞等方面擴展了標準的關系查詢語言SQL，以滿足空間數據查詢的要求。如表1所示，根據OGC的簡單要素規范，定義了空間對象之間的關系和空間分析功能，通過自定義函數的形式，將這些功能加以實現。

表1 空間謂詞擴展函數功能

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

3.空間數據拓撲查詢流程

利用關聯算法計算幾何體之間的拓撲關系分為5個步驟(如圖3所示);①建立幾何體對象的拓撲結構圖，拓撲結構圖包含了對應幾何體的節點和邊線，其中每個節點和每條邊線都被標志其相對于原幾何體的拓撲位置;②初始化幾何體對象的交集矩陣。實例化交集矩陣模型對象，將其字符串設為默認值“＊＊＊＊＊＊＊＊＊”;③獲取兩個幾何體間的交集，可利用單調鏈方法快速精確地求出交集，將幾何體的邊線分解成單調鏈，使用雙交點法簡單求出兩條單調鏈之間的交點，即為幾何體之間交集的節點，添加到拓撲結構圖中;④在幾何體間的交集部分插入節點，并已添加到拓撲結構圖中之后，通過拓撲結構圖成員的標簽，計算交集節點的標簽，再計算幾何體的拓撲結構圖中獨立元件的標簽，獨立元件是指該幾何體中與其他幾何體不相交的節點或邊線;⑤根據拓撲結構圖中所有成員的標簽更新交集矩陣。

圖3 空間數據拓撲查詢處理流程

五、系統試驗和應用

1.試驗數據準備

試驗數據采用ESRI(美國環境系統研究所)提供的世界地圖數據(該數據的制作時間為1980年)作為輸入，格式為SHP格式。

試驗分為兩組，一組是空間關系的查詢，以求中國政區內的城市為例;另一組是空間操作的查詢，以求中國和蒙古合并后的形狀為例。

2.空間關系查詢

為了對空間數據拓撲查詢進行正確性進行評估，結合課題組已有的空間關系查詢方法，在實際項目中進行了測試。下面就以求全球數據中中國政區內所有的城市為例。

首先需要從數據庫中獲取城市數據和中國政區數據。可以判定城市數據為一個點集，設為幾何體a;中國政區數據則為一個區域，設為幾何體b，則本例求的是幾何體a相交幾何體b的部分數據。圖4是全球的城市分布圖。

圖4 全球的城市分布數據圖

例1：求出中國政區內所有的城市，可以用以下SQL語句進行查詢：

上述查詢的文字結果如圖5所示，共65條數據。

圖5 實際結果記錄

3.空間操作查詢

為了對空間分析算法的正確性進行評估，下面就以求中國和蒙古合并后的形狀為例。

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

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

圖6 實際查詢結果文字記錄?

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

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

圖7 文字結果

六、結束語

空間數據庫技術由于其在商業領域和軍事應用等各方面的巨大前景，已成為數據庫技術研究與發展的熱點。其中，拓撲關系的描述與判斷在空間數據建模、空間數據查詢、分析和數據更新等方面起著重要的作用。本文在研究空間拓撲關系描述模型的基礎上，設計實現的空間數據庫拓撲查詢與索引功能，性能較高，應用方便，對進一步開發新型空間數據庫系統具有重要意義。

［1］陳軍，趙仁亮.GIS空間關系的基本問題與研究進展［J］.測繪學報，1999，5(2)：95-102.

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