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

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

0 引言

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

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

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

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

1 SVP算法介紹

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

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

圖1 SVP算法示意圖

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

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

2.1 算法原理與流程

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

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

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

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

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

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

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

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

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

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

圖4 天際線更新示意圖

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

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

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

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

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

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

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

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

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

3 實驗與比較

3.1 精度驗證

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

圖5 臨界點與可視高程示意圖

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

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

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

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

3.2 性能比較

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

圖7 各算法的時間消耗圖

4 結(jié)束語

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

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