面向規(guī)則網(wǎng)格的連續(xù)天際線可視域精確算法

張建民，余接情，艾 偉，杜 丹

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081;2.河北省智能化信息感知與處理重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081;3.中國(guó)礦業(yè)大學(xué)環(huán)境與測(cè)繪學(xué)院，江蘇 徐州 221116;4.陸裝駐石家莊地區(qū)第一軍代室，河北 石家莊 050081)

0 引言

設(shè)施選址[1]、景觀分析與規(guī)劃[2-3]、軍事突防[4-5]、安防監(jiān)控[6]及信號(hào)盲區(qū)計(jì)算[7-8]等問(wèn)題均需獲取相對(duì)視點(diǎn)可見(jiàn)的表面區(qū)域，即可視域計(jì)算。計(jì)算機(jī)中，地形表面常采用基于規(guī)則網(wǎng)格的數(shù)字高程模型來(lái)描述。為此，可視域計(jì)算通常為尋找相對(duì)于視點(diǎn)的所有可見(jiàn)網(wǎng)格。某一網(wǎng)格可見(jiàn)當(dāng)且僅當(dāng)其與視點(diǎn)連線不被其它網(wǎng)格遮擋。

作為地理信息系統(tǒng)空間分析的經(jīng)典問(wèn)題，可視域計(jì)算已有較多研究。Shapira[9]提出了一種精確的可視域計(jì)算算法―R3算法。該算法為每一網(wǎng)格引一條視線，通過(guò)視線是否被阻擋來(lái)判斷每一網(wǎng)格的可見(jiàn)性。由于每一網(wǎng)格的可見(jiàn)性除當(dāng)前網(wǎng)格外還涉及視線所途經(jīng)的網(wǎng)格，為此，R3算法的計(jì)算量極為龐大，時(shí)間復(fù)雜度達(dá)O(n3)，其中，n為地形沿某一維度的網(wǎng)格數(shù)量。為提高算法速度，Kreveld[10]提出了一種時(shí)間復(fù)雜度為O (n2logn)的掃描線(Sweep Line,SL)算法；Franklin和Ray[11]提出了一種時(shí)間復(fù)雜度為O(n2)的xDraw算法和R2算法；Wang等[12]基于視線后方鄰近網(wǎng)格的視面提出了一種更快的參考面算法。事實(shí)上，當(dāng)前網(wǎng)格是否可見(jiàn)不僅與視線后方鄰近網(wǎng)格有關(guān)，還與離視點(diǎn)更近網(wǎng)格所構(gòu)成的視面有關(guān)。對(duì)此，Yu等[13]提出了一種視面綜合算法(Synthetic Visual Plane, SVP)，將任意相鄰網(wǎng)格構(gòu)成的視面投影至遠(yuǎn)處的投影面，形成一條天際線，通過(guò)合成多條更近天際線以獲得當(dāng)前天際線，從而判斷當(dāng)前網(wǎng)格的可見(jiàn)性。為提高算法效率，該算法以一定的精度損失為代價(jià)對(duì)天際線進(jìn)行了離散化處理。

然而，精度是可視域計(jì)算的重要考慮因素。Kauci和Zalik[14]將可視域計(jì)算算法分為精確算法和近似算法。除R3算法和SL算法外，上述均為近似算法[13-16]。實(shí)際應(yīng)用中，可視域計(jì)算既要考慮時(shí)間性能也要考慮算法精度。例如，飛機(jī)突防應(yīng)用中，錯(cuò)誤的可視域結(jié)果會(huì)為突防飛機(jī)帶來(lái)風(fēng)險(xiǎn)，而較低的計(jì)算效率又難以滿足應(yīng)用要求。對(duì)精確算法進(jìn)行并行化改造是一種可滿足上述要求的方案。Zhao等人[15]及Chaulio等人[16]利用并行計(jì)算分別對(duì)R3算法和SL算法進(jìn)行了改造。然而，并行化方案雖可行但終究依賴硬件，特定場(chǎng)合下難以適用。

本文在SVP算法的基礎(chǔ)上改進(jìn)描述方法并設(shè)計(jì)了高效的數(shù)據(jù)結(jié)構(gòu)與算法來(lái)應(yīng)對(duì)天際線描述方式變更后所帶來(lái)的天際線快速更新問(wèn)題，提出一種高效且精準(zhǔn)的可視域計(jì)算算法。

1 SVP算法介紹

圖1為SVP算法[13]示意圖。該算法以視點(diǎn)為中心將規(guī)則網(wǎng)格表示的地形劃分為4個(gè)扇區(qū)和若干個(gè)環(huán)，并為每一扇區(qū)在離視點(diǎn)一定距離處設(shè)立一個(gè)投影面，如圖1(a)所示。算法將前序所有環(huán)的每一網(wǎng)格點(diǎn)投影至投影面以得出前序天際線。天際線被定義為將某一環(huán)上各網(wǎng)格點(diǎn)投影至投影面并依次連接所形成的一條連續(xù)線段。若當(dāng)前環(huán)的某一網(wǎng)格點(diǎn)的投影(以下簡(jiǎn)稱投影點(diǎn))在前序天際線上面，則當(dāng)前點(diǎn)可見(jiàn)，否則不可見(jiàn)。該算法的關(guān)鍵在于獲取當(dāng)前環(huán)的各投影點(diǎn)后如何更新前序天際線。為提升效率，SVP算法對(duì)天際線進(jìn)行了離散化，如圖1(b)所示。將投影面以一定間距劃分為若干條帶，借助條帶對(duì)天際線進(jìn)行離散化采樣。更新時(shí)，若某一條帶的當(dāng)前投影高程高于先前投影高程，則更新該條帶的投影高程。由于離散化后的天際線更新特別快，為此，SVP算法效率很高。

SVP算法時(shí)間效率與參考面算法相似但精度更高，比R2算法時(shí)間效率更高，但精度略差。雖然可通過(guò)縮短條帶的間距以提高SVP算法的精度，但這樣會(huì)成倍增加算法的時(shí)間消耗，甚至可能超過(guò)R3算法，使得該操作無(wú)過(guò)多實(shí)際應(yīng)用價(jià)值。

圖1 SVP算法示意圖

2 連續(xù)天際線可視域算法

為方便起見(jiàn)，將本文提出的新算法稱為連續(xù)天際線可視域(Viewshed based on Continuous Horizon, VCH)算法。VCH算法以SVP算法為基礎(chǔ)，通過(guò)改進(jìn)其天際線的表達(dá)與更新方法來(lái)實(shí)現(xiàn)可視域的精確計(jì)算。

2.1 算法原理與流程

如上所述，SVP算法的核心之一是對(duì)天際線進(jìn)行離散化。雖然離散化可提高算法的速度，但也帶來(lái)了誤差，降低了算法的精度。為避免該問(wèn)題，VCH算法采用連續(xù)線段來(lái)表達(dá)天際線。與此同時(shí)，為避免連續(xù)線段天際線更新的效率低下問(wèn)題，引入了紅黑樹[17]來(lái)動(dòng)態(tài)管理該天際線。

VCH算法以視點(diǎn)為中心，以兩條45°對(duì)角線為界將規(guī)則格網(wǎng)表示的地形表面劃分為4個(gè)扇區(qū)，再根據(jù)同心方環(huán)的順序依次由內(nèi)向外劃分為若干個(gè)環(huán)，如圖1(a)所示。為避免扇形邊界重復(fù)投影問(wèn)題，VCH算法在四個(gè)方向上同時(shí)設(shè)立了一個(gè)投影面，形成了一個(gè)閉合的投影墻, 如圖2所示。VCH算法的總體流程如下：

圖2 投影墻及初始天際線示意圖

(1)將第一環(huán)上的表面點(diǎn)投影至投影墻(第一環(huán)上的表面點(diǎn)總為可見(jiàn))，形成一條初始天際線，設(shè)置第二環(huán)為當(dāng)前環(huán)；

(2)投影當(dāng)前環(huán)的表面點(diǎn)至投影墻上，然后由前序天際線來(lái)逐一判斷當(dāng)前環(huán)各表面點(diǎn)的可見(jiàn)性；若表面點(diǎn)投影位于前序天際線之上，則可見(jiàn)，否則，不可見(jiàn)；

(3)根據(jù)當(dāng)前環(huán)各投影點(diǎn)高程更新前序天際線；

(4)視更新后的天際線為當(dāng)前環(huán)及前序環(huán)所對(duì)應(yīng)的天際線(即下次循環(huán)的前序天際線)，用于后續(xù)環(huán)表面點(diǎn)的可見(jiàn)性判斷，重復(fù)步驟(2)至步驟(4)，直至所有環(huán)均被處理為止。

一條天際線由若干條片段構(gòu)成，上述流程的關(guān)鍵在于根據(jù)當(dāng)前環(huán)各投影點(diǎn)所形成的片段來(lái)更新前序天際線。為加速該更新過(guò)程，本文采用了紅黑樹及雙向鏈表這一數(shù)據(jù)結(jié)構(gòu)來(lái)共同存儲(chǔ)與管理一條天際線，如圖3所示。雙向鏈表的每個(gè)節(jié)點(diǎn)由頭尾兩個(gè)指針和數(shù)據(jù)體構(gòu)成。數(shù)據(jù)體記錄投影點(diǎn)的y和z坐標(biāo)。雙向鏈表的每個(gè)節(jié)點(diǎn)按照其y坐標(biāo)的升序進(jìn)行排列。紅黑樹的每個(gè)節(jié)點(diǎn)記錄投影點(diǎn)的y坐標(biāo)及其在雙向鏈表對(duì)應(yīng)節(jié)點(diǎn)的地址。

圖3 天際線數(shù)據(jù)結(jié)構(gòu)圖

更新時(shí)，需根據(jù)當(dāng)前片段的前后兩個(gè)端點(diǎn)的y坐標(biāo)值，從紅黑樹中依次尋找出對(duì)應(yīng)的節(jié)點(diǎn)，進(jìn)而根據(jù)找到的地址從雙向鏈表中獲取相應(yīng)的前序片段集。前序片段集為前序天際線中的多個(gè)連續(xù)片段的集合。集合中的首片段的起點(diǎn)y坐標(biāo)不小于用于檢索片段的起點(diǎn)的y坐標(biāo)，而集合中的末片段的終點(diǎn)y坐標(biāo)不大于用于檢索片段的終點(diǎn)的y坐標(biāo)。圖4為天際線更新示意圖，其中，線段集I-II-III為片段BC所對(duì)應(yīng)的前序片段集。獲取前序片段集后，按下述規(guī)則將當(dāng)前片段合成并更新至前序天際線(或前序片段集)中。

圖4 天際線更新示意圖

(1)若當(dāng)前片段的某個(gè)投影點(diǎn)(圖4中的A)y坐標(biāo)與前序片段集的某一頂點(diǎn)(圖4中的I)的y坐標(biāo)相同，且投影點(diǎn)的z值更大，則用該投影點(diǎn)的z值替換前序片段集對(duì)應(yīng)頂點(diǎn)的z值；

(2)若當(dāng)前片段的某個(gè)投影點(diǎn)(圖4中的C和D)位于前序片段集的頂部，且其y坐標(biāo)不與前序片段集各頂點(diǎn)的y坐標(biāo)相同，則將該投影點(diǎn)作為一個(gè)新的頂點(diǎn)插入至前序天際線中；

(3)若當(dāng)前片段(圖4中的AB、BC及DE)與前序片段集存在交點(diǎn)(圖4中的S1、S2和S3)，且交點(diǎn)的y坐標(biāo)不與前序片段集各頂點(diǎn)的y坐標(biāo)相同，則將交點(diǎn)作為一個(gè)新的頂點(diǎn)插入至前序天際線中；

(4)若前序片段集的某一頂點(diǎn)(圖4中的Ⅲ)位于當(dāng)前片段(圖4中的CD)的正下方，且該頂?shù)椎膟坐標(biāo)不與當(dāng)前片段的兩個(gè)端點(diǎn)y坐標(biāo)相同，則將該頂點(diǎn)從前序天際線中刪除。

2.2 時(shí)間復(fù)雜度分析

為分析VCH算法的時(shí)間復(fù)雜度，下述偽代碼給出了其總體實(shí)現(xiàn)。

Algorithm:VCH 輸入:(1)規(guī)則網(wǎng)格地形表面點(diǎn) (2)視點(diǎn)、視高及最大視野范圍(r)輸出: 可視域圖1.投影第一環(huán)地表點(diǎn)得初始天際線。2.For i in [2,r] 3. For j in [0, m]//m為當(dāng)前環(huán)的地表點(diǎn)總數(shù)4. 若Pji位于前序天際線上方,輸出可見(jiàn);否則,輸出不可見(jiàn)。//Pji為第i環(huán)的第j個(gè)點(diǎn)5. 尋找當(dāng)前片段(Pj-1i, Pji)的前序片段集。6. 更新當(dāng)前片段至前序片段集(或前序天際線)中7. End For8.End For

易知，語(yǔ)句1和語(yǔ)句4的復(fù)雜度為O(1)。語(yǔ)句5涉及從紅黑樹中尋找特定的節(jié)點(diǎn)，對(duì)應(yīng)的時(shí)間復(fù)雜度為O(logm)[17]，其中，m為前序天際線的頂點(diǎn)數(shù)量。假定前序天際線是由前k個(gè)環(huán)所合成的天際線，則m必然小于8×(1+2+…+k)，這是因?yàn)椴煌h(huán)的表面點(diǎn)投影后的y坐標(biāo)可能相同。顯然，k越小，m越小，反之亦然。若將m平攤至每次循環(huán)中，則一條前序天際線平均擁有不多于4+4n個(gè)頂點(diǎn)，其中，n為最大視野范圍所對(duì)應(yīng)的沿某一維度的網(wǎng)格數(shù)量。為此，語(yǔ)句5的時(shí)間復(fù)雜度為O(logn)。語(yǔ)句6涉及紅黑樹及雙向鏈表的節(jié)點(diǎn)插入與刪除。紅黑樹的插入和刪除操作的時(shí)間復(fù)雜度均為O(logm)[17]。在已知待插入或刪除節(jié)點(diǎn)位置的情況下，雙向鏈表的插入與刪除操作的時(shí)間復(fù)雜度為O(1)。同理，語(yǔ)句6的時(shí)間復(fù)雜度為O(logn)。

綜上分析，易知VCH算法的總體時(shí)間復(fù)雜度為O(n2logn), 其中，n表示最大視野范圍所對(duì)應(yīng)的沿某一維度的網(wǎng)格數(shù)量。

3 實(shí)驗(yàn)與比較

3.1 精度驗(yàn)證

VCH算法根據(jù)前序天際線來(lái)判斷某一表面點(diǎn)是否可見(jiàn)，而前序天際線反映了所有更近點(diǎn)的遮擋情況。為此，理論上VCH算法是一種精確算法。由于可視域的真值難以獲取，本文以公認(rèn)的精確算法[13-16]-R3算法為參考進(jìn)行精度驗(yàn)證。R3算法采用點(diǎn)的高程是否比其可視高程大的方式來(lái)計(jì)算，而VCH算法采用點(diǎn)的投影是否在其對(duì)應(yīng)的前序天際線上面的方式來(lái)計(jì)算。臨界點(diǎn)與可視高程如圖5所示，由于浮點(diǎn)計(jì)算誤差的存在，不同的計(jì)算方式會(huì)導(dǎo)致臨界點(diǎn)(即該點(diǎn)的高程與可視高程極為接近，如圖5的B和C所示)的可見(jiàn)性結(jié)果迥異。雖然理論上VCH算法是精確算法，但其結(jié)果可能不與R3算法的結(jié)果完全相同。

圖5 臨界點(diǎn)與可視高程示意圖

為測(cè)試VCH算法的精度，使用了東經(jīng)115.5°至117.5°、北緯28.7°至30.3°的ASTER DEM數(shù)據(jù)開(kāi)展了實(shí)驗(yàn)。實(shí)驗(yàn)采用了世界墨卡托投影，設(shè)置視點(diǎn)為(12968717.010,3419826.095)、離地高度為100 m、最大視野范圍為50 km，統(tǒng)計(jì)了VCH算法與R3算法不同結(jié)果的網(wǎng)格，包括假正(false positive)網(wǎng)格和真負(fù)(truth negative)網(wǎng)格。假正網(wǎng)格指R3算法可見(jiàn)但VCH算法判為不可見(jiàn)的網(wǎng)格；真負(fù)網(wǎng)格指R3算法不可見(jiàn)卻被VCH算法判為可見(jiàn)的網(wǎng)格。表1給出了VCH算法結(jié)果中的所有網(wǎng)格、假正網(wǎng)格及真負(fù)網(wǎng)格的數(shù)量?？梢园l(fā)現(xiàn)：VCH算法的假正及真負(fù)網(wǎng)格的占比極為微小。

表1 VCH算法中各類網(wǎng)格數(shù)量統(tǒng)計(jì)表

圖6 各假正及真負(fù)網(wǎng)格所對(duì)應(yīng)的最小視高差圖

為測(cè)試VCH算法中假正及真負(fù)網(wǎng)格是否為臨界點(diǎn)網(wǎng)格，引入了視高差這一概念。從視點(diǎn)出發(fā)引一條視線至待測(cè)試的網(wǎng)格點(diǎn)，計(jì)算各途徑點(diǎn)與該視線的距離，即視高差(圖6)。若某一途徑點(diǎn)的視高差接近于零，則表明待測(cè)試網(wǎng)格點(diǎn)是一臨界點(diǎn)。VCH算法所有假正及真負(fù)網(wǎng)格的最小視高差的分布(按從大至小順序排列)如圖6所示?？梢钥闯?，最小視高差不超過(guò)10-12m，意味著VCH算法所有假正及真負(fù)網(wǎng)格所對(duì)應(yīng)的表面點(diǎn)均可認(rèn)為是臨界點(diǎn)，即VCH算法的假正及真負(fù)網(wǎng)格由浮點(diǎn)計(jì)算誤差產(chǎn)生。若不計(jì)浮點(diǎn)計(jì)算誤差的影響，VCH算法與R3算法結(jié)果將等同。也就是說(shuō)，VCH算法是一種精確算法。

3.2 性能比較

為測(cè)試與比較VCH算法的時(shí)間性能，利用C++實(shí)現(xiàn)了R3、SL(由開(kāi)源軟件GRASS提供)、VCH、R2及SVP算法，并在Intel i5-7500 CPU(單核主頻3.40GHz、64位)、8GB DDR內(nèi)存、東芝1TB 7200轉(zhuǎn)機(jī)械硬盤的硬件環(huán)境下運(yùn)行。實(shí)驗(yàn)除最大視野范圍不同，數(shù)據(jù)及其它參數(shù)均與3.1節(jié)保持一致。此外，為便于橫向比較，設(shè)置初始最大視野范圍為10 km，之后以10 km為間隔依次增大直至80 km為止。圖7為各算法的時(shí)間消耗。可以看出，R3算法的時(shí)間消耗最大、SL其次、剩下依次為VCH、R2及SVP，而后三者較為接近。所有算法的時(shí)間消耗隨最大視野范圍的增大而增加，但VCH的增幅明顯小于R3及SL，略大于R2及SVP。

圖7 各算法的時(shí)間消耗圖

4 結(jié)束語(yǔ)

圍繞現(xiàn)有可視域算法在精度及效率難以同時(shí)達(dá)到較高性能這一問(wèn)題，本文以視面綜合算法為基礎(chǔ)，基于連續(xù)天際線思想及紅黑樹與雙向鏈表提出了一種新的可視域算法。新算法可在保證結(jié)果完全準(zhǔn)確的情況下將時(shí)間復(fù)雜度控制在O(n2logn),其中，n為最大視野范圍沿某一維度的網(wǎng)格數(shù)量。與R3精確算法(時(shí)間復(fù)雜度：O(n3))相比，新算法的時(shí)間性能提升了一個(gè)檔次。雖然與掃描線精確算法相比新算法的時(shí)間復(fù)雜度沒(méi)有降低，但真實(shí)實(shí)驗(yàn)表明新算法比掃描線快得多，其時(shí)間性能可與現(xiàn)有的近似算法相媲美。

新算法可用于對(duì)精度和時(shí)間要求均很高的應(yīng)用，如低空突防，信號(hào)盲區(qū)計(jì)算等。后續(xù)研究將對(duì)該算法中的天際線數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn)以進(jìn)一步提升算法的效率。