區域CORS網絡構造優化算法

呂洪標,郭 英,盧秀山

(山東科技大學海島(礁)測繪技術國家測繪局重點實驗室,山東青島266510)

0 引 言

全球定位系統(GPS)的廣泛應用和現代通信技術的成熟為網絡RTK定位技術的應用和推廣提供了有利條件,使現代連續運行參考站服務系統(CORS)網絡的發展呈現出實時化和規模化的特點。局域范圍內,國外典型的網絡有美國的南加州GPS綜合網、德國的衛星定位導航服務網。在國內,從2000年起,香港、深圳、北京、成都、昆明、上海等城市率先建立了城市多功能GPS服務網。迄今為止,中國國內有近二十個城市已經建設了各自的區域CORS網,更有不少地區正處在籌備計劃中。

隨著計算機技術的發展,拓撲網絡生成技術越來越多地應用到各種工程領域,在眾多網絡結構中,Delaunay三角網(DTIN)最具代表性,適合于區域CORS網絡構造。它具有以下特點:

1)網絡構成唯一,便于CORS網絡識別和管理;

2)每個三角形盡量接近等邊三角形,有利于保證CORS網絡改正數的內插精度;

3)三角形的邊長之和最小,有利于基線上模糊度的快速可靠求解[1]。

中國是一個國土面積相當大的國家,可依據建設管理形式、任務要求和應用范圍,先發展行業的、區域的CORS網絡。這就需要區域CORS網絡構造算法來完成區域CORS網絡的構造。以往的區域CORS網絡構造算法在特殊區域的離散點集內有它的局限性,不能有效完成構網任務,甚至構網中斷。

基于已有的算法,研究區域CORS構網算法優化問題,也就是在區域范圍內能夠有效完成CORS網絡構造,為CORS網的數據處理工作奠定了良好的基礎。

1 Delaunay三角網

在區域范圍內,通常使用Delaunay構網方法即可滿足實際的構網需求。

1.1 Delaunay三角網構網定義及其性質

DTIN的定義是[2]:

①網內任何一個三角形的外接圓內不包含第四點;

②若出現四點共圓的情況,則連接該凸四邊形的較短的對角線形成2個新三角形。如果網絡中任何一個三角形都滿足上述兩點,則稱該網絡是一個DTIN。

為方便描述DTIN的構網算法,現給出DTIN的如下性質:

①三角單元的最大最小角

相鄰兩個Delaunay三角形構成凸四邊形,在交換凸四邊形的對角線之后,六個內角的最小者不再增加。

②三角單元的空外接圓

任何一個Delaunay三角形的外接圓內不能包含任何其他離散點。

這兩個性質,決定了Delaunay三角網具有極大的應用價值。Miles證明Delaunay三角網是“最好”的三角網;Lingas進一步論證了“在一般情況下,Delaunay三角網是最優的”;Sibson認定“在一個有限點集中,只存在一個局部等角的三角網,這就是Delaunay三角網”。

1.2 Delaunay三角網的構網步驟

直接按DTIN的定義搜索三角形單元的效率很低,時間復雜度為O(n3),利用DTIN的最大最小角性質以及空外接圓性質可大大提高搜索效率,使算法的時間復雜度減小為O(n2)[1]。根據性質①,②,提出了一種區域CORS網絡構造優化算法,設計的數據結構包括頂點結構、邊結構、三角形結構、隊列結構以及集合結構,集合結構包含點結構和三角形結構。邊結構中,設計了一個標志變量,用來判斷該邊是否被擴展過。該算法輸入集合頂點集,輸出集合為三角形集。已有的區域CORS網絡構造算法是以2最大最小角性質和空外接圓性質構造網絡算法的實現步驟(見圖1)

圖1 區域CORS網絡構造算法流程圖

1)將所有離散的WGS-84點中心投影到以地心為球心,以地球赤道半徑為半徑的球上,生成頂點集;

2)在頂點集中搜索距離最小的兩點為初始邊,并生成初始三角形;

3)以三角形的另兩條邊為擴展邊,生成新的三角形;

4)判斷是否還有未擴展的邊。若有,轉到3);若無,則輸出三角形集,構網結束。

2 區域CORS網絡構造優化算法

基于區域CORS網絡構造算法,在特殊區域范圍內,不能有效構網。提出了區域CORS網絡構造優化算法。算法核心是以最小角降序且空外接圓約束構造網絡,其實現步驟如下(見圖2)。

1)將所有離散的WGS-84點中心投影到以地心為球心,以地球赤道半徑為半徑的球上,生成頂點集;

2)在頂點集中搜索距離最小的兩點為初始邊,搜索以初始邊為擴展邊的所有三角形,按照最小角從大到小的順序,進行空外接圓約束,并生成初始三角形;

3)以三角形的另兩條邊為擴展邊,按照最小角降序且空外接圓約束來生成新三角形;

4)判斷是否還有未擴展的邊。若有,轉到3);若無,則輸出三角形集,構網結束。

圖2 區域CORS網絡構造優化算法流程圖

3 實例分析

在大多數區域CORS網絡構造中,兩種算法的構網結果都是一樣的,但是在特殊區域的情況下,構造的CORS網絡結果存在一定的差異。針對在特殊區域內,對構網的差異進行試驗分析。試驗用ITRF的7個IGS站點構造區域CORS網絡來驗證區域CORS網絡構造優化算法的可靠性,同時比較兩種算法的有效性。如圖3、4所示。

試驗結果為:

圖3 區域CORS網絡構造算法構網結果

1)已有的區域CORS網絡構造算法得出圖3結果,生成兩個三角形(hivi,ormt,lewi)和(lewi,ormt,fred)(黑色標記)就結束了,原因在于以擴展邊(fred,lewi)構造網絡,搜索到三個三角形(fred,lewi，tswy）（綠色標記),(fred,lewi,bcyi)和(fred,lewi,coon)(紅色標記),其中三角形(fred,ewi,tswy)為最小角最大的,但是它不滿足空外接圓性質(包含點coon),沒有完成構網任務,數據處理工作無法繼續進行。

圖4 區域CORS網絡構造優化算法構網結果

2)用區域CORS網絡構造優化算法得出圖4結果,在以擴展邊(fred,lewi)搜索到的三個三角形中按每個三角形的最小角降序排列,依次進行空外接圓約束,最后得出三角形(fred,lewi,coon)滿足空外接圓性質,進而得以順利向下進行構造網絡。

3)實例比較分析說明,區域CORS網絡構造優化算法避免了區域CORS網絡構造算法的局限性,證明了在任何區域范圍內,區域CORS網絡構造優化算法是可靠的,而且也是有效的。

4 結論與建議

在區域范圍內,用DTIN構造CORS網絡具有可靠性和優越性。針對 DTIN提出的區域CORS網絡構造優化算法,較之以往的區域CORS構網算法大大提高了可靠性,并用ITRF的IGS站點構成了區域CORS網絡,證明和比較了該算法是可靠和有效的。該算法在區域性CORS網絡組成全國性CORS網絡中也能解決相應問題,有著非常廣闊的應用前景。

區域CORS網絡構造作為新的大地基準以及坐標參考框架為國土測繪起著重要作用,此外,還為氣象學、電離層等研究提供了時空高密度的大量原始觀測數據,為相關領域的科學研究做出了寶貴的貢獻。CORS網絡構造除了在地殼運動監測和大地測量基準專業領域發揮重要作用外,還將促進定位信息市場的發展壯大和新產品的開發。

[1]周樂韜,黃丁發,李成鋼,等.基于球面Delaunay三角網的GPS網絡構造算法[J].西南交通大學學報,2007,42(3):380-383.

[2]王建華,徐強勛,張 銳.任意形狀三維物體的Delaunay網格生成算法[J].巖石力學與工程學報,2003,22(5):717-722.

[3]梅勝強,宮煦利,姚宜斌,等.基于Delaunay三角網的大規模CORS基準站組網技術研究[J].大地測量與地球動力學,2008,28(1):131-135.

[4]武曉波,王世新,肖春生.Delaunay三角網的生成算法研究[J].測繪學報,1999,28(1):28-35.

[5]鄒 榮,劉 暉,姚宜斌,等.Delaunay三角網構網技術在連續運行衛星定位服務系統中的應用[J].測繪信息與工程,2005,30(6):9-11.

[6]宋占峰,蒲 浩,詹振炎.快速構建Delaunay三角網算法研究[J].鐵道學報,2001,23(5):85-91.