基于圖論的測量控制網拓撲分析系統的研究

宇 偉，李曉莉

(合肥工業大學土木與水利工程學院測量工程系，安徽合肥230009)

一、引 言

在研究測量控制網的機理、健康和安全時，首先需要解決的一個關鍵問題就是正確地識別或判斷測量控制網工作時的圖形參數，測量控制網的圖形參數是研究控制網形變機理、健康監測和安全評估的基礎和依據。測量控制網參數的識別屬于系統識別范疇，一般意義上講，就是在識別系統輸入(激勵)和輸出(響應)數據的基礎上，對系統確定一個數學模型，要求這個模型盡可能精確地反映測量控制網的結構特性，從而達到識別測量控制網系統的目的。基于圖論的測量控制網拓撲分析系統是建立在系統輸入和輸出數據的基礎上的，它實現了由控制網圖形的映射、響應，以識別其圖形參數，是一種方便、便宜和可行的方法，可以實現測量控制網的拓撲應用，具有明顯的優點和顯著的特色。

現在的測繪數據的處理一般是基于一定格式的觀測文件，而后建立間接方程。通過觀測文件的一定格式可以識別站點和其他點的拓撲關系，這是建立方程的基礎。但是這種方式缺乏對整個控制網的拓撲分析，本文以圖論為基礎，旨在提高控制網拓撲分析能力，并建立相應的應用。

二、基于圖論的控制網拓撲分析系統的設計

1．思 路

圖論中點與點之間、點與線之間、線與線之間的拓撲關系主要有：①并聯與鄰聯關系;②相交關系;③相離關系。如果兩點存在聯系可用直線相連兩點，否則兩點不連。測量控制網中，點與點之間、點與線之間及線與線之間的聯系同圖論中情況相似。測量控制網中，點與點間的聯系參數包含高差、距離、角度，這就使控制網在拓撲識別的基礎上還要建立與之相對應的觀測數據文件，以建立觀測值和測量控制網圖形的映射關系，實現控制網的拓撲應用。

2．尋找拓撲形的算法過程

(1)數據結構的建立

在一般的儀器測量過程中，會產生以站點為結點的數據結構，可以在此數據結構上進行拓撲分析，也可以轉化為其他的數據結構進行分析。本文以鄰接矩陣來表示控制網的數據結構，并在其基礎上按照一定的算法建立控制網的生成樹，并在其基礎上尋找閉合圈、附合路徑等拓撲條件，再以整個測量控制網為基礎，對控制網進行拓撲分析，這樣可在拓撲形上進行數據處理，算法的基本過程如圖1所示。

圖1 算法的基本過程

(2)參數的初始化

未知參數的初始化主要是根據遍歷控制網生成樹進行的。遍歷從已知點開始，按照廣探法逐級遍歷。即從已知點開始，將未知點初始化，再將其作為已知點初始化下一級未知點，直至未知點被全部初始化。

(3)附合路徑的尋找

附合路徑的尋找主要是尋找已知點和已知點間的路線，由于測量控制網中的已知點固定，可以建立從第一個已知點出發的廣探法遍歷，遍歷的過程中建立記錄遍歷過程的數據結構，然后根據其他已知點在遍歷中的次序，按一定算法找到附合路徑。具體算法如下(若已知點數為n)：

1)從第一個已知點出發建立廣探生成樹，同時要記錄生成樹的路徑。

2)生成樹建立以后，根據其他已知點在遍歷產生數據結構的位置，建立它們和第一個已知點的路徑。

3)依次尋找n-1條路徑為止。

(4)基本閉合圈的尋找

基本閉合圈是構成控制網中最基本非冗余的圈，即組成其他圈的最簡單圈。基本圈的尋找要以控制網的生成樹為基礎，控制網中沒有在生成樹中的邊會和生成樹構成基本圈。具體算法如下：

1)按廣探法建立控制網的生成樹，同時要記錄生成樹的路徑。

2)尋找出不在控制網生成樹中的邊。

3)根據構成這些邊是兩點進行回溯，直到回溯到同一點，建立起到該點的兩條路徑，合并這兩條路徑就組成基本圈。

(5)粗差的檢測和定位

測量控制網的拓撲形狀的識別，如閉合圈、附合路徑均為多余條件，都可按一定的精度要求對拓撲形中的觀測值進行粗差檢測，如閉合差等。如果檢測結果超限，則表明該拓撲形狀中含有粗差。如果控制網中多個拓撲形狀均反映出檢測超限的情況，則粗差很可能出現在各拓撲形的交集上。其算法如下：

1)按照前述的算法找出各拓撲形。

2)按一定的精度要求對拓撲形進行檢測。

3)若拓撲形出現粗差，進行交集分析，定位粗差的范圍。

3．算法過程的主要代碼

三、試驗結果及分析

為使問題簡便，現對一結點控制網展開討論。某一控制網其網形(可取用水準網或是未記角度的導線網)，如圖2所示，該網形的鄰接矩陣(對稱陣)為

圖2

首先由廣探法建立控制網的生成樹，進行初始化。通過拓撲分析后，可尋找到的拓撲形為：① 附合路線1，2，3，4，10; ② 閉合路線分別為：閉合圈一1，2，3，6，5，1，閉合圈二1，5，6，9，8，7，1，閉合圈三3，4，10，9，6，3。這些圖形條件找出后，可以用于建立條件方程和誤差分析等，如：如果5—6段存在粗差，則通過分析，粗差可能在1—5或5—6段;如果是6—9段存在粗差，則可直接確定6-9段。

四、結束語

在控制網數據處理中引入拓撲分析，增強了對控制網圖形條件的使用，實現了數據處理的自動化和簡單化，避免了繁雜的數據處理。由于引入拓撲分析，將改變方程建立模式，對控制網的精度和可靠性分析也會產生變化，如對控制網進行拓撲分析，這樣可在拓撲形上進行數據處理，實現條件方程的建立和粗差的檢測與定位等應用。然而，就控制網拓撲形尋找而言，也有其復雜性，如建立條件方程的圓周條件和極條件的尋找時就要同時利用觀測文件和圖論中的數據結構，或者建立特殊的數據結構，分析也是有一定的難度，但是對于一般的水準網、導線網及GPS網的拓撲分析還是比較簡單的。

[1]項榮武，劉艷杰，胡忠盛．圖論中最短路徑問題的解法[J]．沈陽航空工業學院學報 ，2004，21(2)：86-88．

[2]朱力杰，楊元喜．論粗差修正與粗差剔除[J]．測繪通報，1999(6)：5-6．

[3]柴登峰，張登榮．前N條最短路徑問題的算法及應用[J]．浙江大學學報：工學版，2002，36(5)：531-534．

[4]劉瓚武．應用圖論[M]．長沙：國防科技大學出版社，2006．

[5]李明．數據結構(C++版)[M]．北京：清華大學出版社，2005．

[6]武漢大學測繪學院測量平差學科組．誤差理論與測量平差基礎[M]．武漢：武漢大學出版社，2009．