區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法

呂洪標(biāo),郭 英,盧秀山

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

0 引 言

全球定位系統(tǒng)(GPS)的廣泛應(yīng)用和現(xiàn)代通信技術(shù)的成熟為網(wǎng)絡(luò)RTK定位技術(shù)的應(yīng)用和推廣提供了有利條件,使現(xiàn)代連續(xù)運行參考站服務(wù)系統(tǒng)(CORS)網(wǎng)絡(luò)的發(fā)展呈現(xiàn)出實時化和規(guī)?；奶攸c。局域范圍內(nèi),國外典型的網(wǎng)絡(luò)有美國的南加州GPS綜合網(wǎng)、德國的衛(wèi)星定位導(dǎo)航服務(wù)網(wǎng)。在國內(nèi),從2000年起,香港、深圳、北京、成都、昆明、上海等城市率先建立了城市多功能GPS服務(wù)網(wǎng)。迄今為止,中國國內(nèi)有近二十個城市已經(jīng)建設(shè)了各自的區(qū)域CORS網(wǎng),更有不少地區(qū)正處在籌備計劃中。

隨著計算機技術(shù)的發(fā)展,拓?fù)渚W(wǎng)絡(luò)生成技術(shù)越來越多地應(yīng)用到各種工程領(lǐng)域,在眾多網(wǎng)絡(luò)結(jié)構(gòu)中,Delaunay三角網(wǎng)(DTIN)最具代表性,適合于區(qū)域CORS網(wǎng)絡(luò)構(gòu)造。它具有以下特點:

1)網(wǎng)絡(luò)構(gòu)成唯一,便于CORS網(wǎng)絡(luò)識別和管理;

2)每個三角形盡量接近等邊三角形,有利于保證CORS網(wǎng)絡(luò)改正數(shù)的內(nèi)插精度;

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

中國是一個國土面積相當(dāng)大的國家,可依據(jù)建設(shè)管理形式、任務(wù)要求和應(yīng)用范圍,先發(fā)展行業(yè)的、區(qū)域的CORS網(wǎng)絡(luò)。這就需要區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法來完成區(qū)域CORS網(wǎng)絡(luò)的構(gòu)造。以往的區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法在特殊區(qū)域的離散點集內(nèi)有它的局限性,不能有效完成構(gòu)網(wǎng)任務(wù),甚至構(gòu)網(wǎng)中斷。

基于已有的算法,研究區(qū)域CORS構(gòu)網(wǎng)算法優(yōu)化問題,也就是在區(qū)域范圍內(nèi)能夠有效完成CORS網(wǎng)絡(luò)構(gòu)造,為CORS網(wǎng)的數(shù)據(jù)處理工作奠定了良好的基礎(chǔ)。

1 Delaunay三角網(wǎng)

在區(qū)域范圍內(nèi),通常使用Delaunay構(gòu)網(wǎng)方法即可滿足實際的構(gòu)網(wǎng)需求。

1.1 Delaunay三角網(wǎng)構(gòu)網(wǎng)定義及其性質(zhì)

DTIN的定義是[2]:

①網(wǎng)內(nèi)任何一個三角形的外接圓內(nèi)不包含第四點;

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

為方便描述DTIN的構(gòu)網(wǎng)算法,現(xiàn)給出DTIN的如下性質(zhì):

①三角單元的最大最小角

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

②三角單元的空外接圓

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

這兩個性質(zhì),決定了Delaunay三角網(wǎng)具有極大的應(yīng)用價值。Miles證明Delaunay三角網(wǎng)是“最好”的三角網(wǎng);Lingas進一步論證了“在一般情況下,Delaunay三角網(wǎng)是最優(yōu)的”;Sibson認(rèn)定“在一個有限點集中,只存在一個局部等角的三角網(wǎng),這就是Delaunay三角網(wǎng)”。

1.2 Delaunay三角網(wǎng)的構(gòu)網(wǎng)步驟

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

圖1 區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法流程圖

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

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

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

4)判斷是否還有未擴展的邊。若有,轉(zhuǎn)到3);若無,則輸出三角形集,構(gòu)網(wǎng)結(jié)束。

2 區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法

基于區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法,在特殊區(qū)域范圍內(nèi),不能有效構(gòu)網(wǎng)。提出了區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法。算法核心是以最小角降序且空外接圓約束構(gòu)造網(wǎng)絡(luò),其實現(xiàn)步驟如下(見圖2)。

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

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

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

4)判斷是否還有未擴展的邊。若有,轉(zhuǎn)到3);若無,則輸出三角形集,構(gòu)網(wǎng)結(jié)束。

圖2 區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法流程圖

3 實例分析

在大多數(shù)區(qū)域CORS網(wǎng)絡(luò)構(gòu)造中,兩種算法的構(gòu)網(wǎng)結(jié)果都是一樣的,但是在特殊區(qū)域的情況下,構(gòu)造的CORS網(wǎng)絡(luò)結(jié)果存在一定的差異。針對在特殊區(qū)域內(nèi),對構(gòu)網(wǎng)的差異進行試驗分析。試驗用ITRF的7個IGS站點構(gòu)造區(qū)域CORS網(wǎng)絡(luò)來驗證區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法的可靠性,同時比較兩種算法的有效性。如圖3、4所示。

試驗結(jié)果為:

圖3 區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法構(gòu)網(wǎng)結(jié)果

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

圖4 區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法構(gòu)網(wǎng)結(jié)果

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

3)實例比較分析說明,區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法避免了區(qū)域CORS網(wǎng)絡(luò)構(gòu)造算法的局限性,證明了在任何區(qū)域范圍內(nèi),區(qū)域CORS網(wǎng)絡(luò)構(gòu)造優(yōu)化算法是可靠的,而且也是有效的。

4 結(jié)論與建議

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

區(qū)域CORS網(wǎng)絡(luò)構(gòu)造作為新的大地基準(zhǔn)以及坐標(biāo)參考框架為國土測繪起著重要作用,此外,還為氣象學(xué)、電離層等研究提供了時空高密度的大量原始觀測數(shù)據(jù),為相關(guān)領(lǐng)域的科學(xué)研究做出了寶貴的貢獻。CORS網(wǎng)絡(luò)構(gòu)造除了在地殼運動監(jiān)測和大地測量基準(zhǔn)專業(yè)領(lǐng)域發(fā)揮重要作用外,還將促進定位信息市場的發(fā)展壯大和新產(chǎn)品的開發(fā)。

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

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

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

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

[5]鄒 榮,劉 暉,姚宜斌,等.Delaunay三角網(wǎng)構(gòu)網(wǎng)技術(shù)在連續(xù)運行衛(wèi)星定位服務(wù)系統(tǒng)中的應(yīng)用[J].測繪信息與工程,2005,30(6):9-11.

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