基于掃描線的衛星區域覆蓋分析算法

汪榮峰,胡 敏

(航天工程大學 航天指揮學院,北京 101416)

0 概述

衛星區域覆蓋分析廣泛應用于衛星任務規劃[1]、成像偵察[2]等航天任務中。衛星區域覆蓋分析指標[3]包括覆蓋重數、面積覆蓋百分比、覆蓋累積面積、時間覆蓋百分比、最大重訪時間及平均重訪時間等,其中面積覆蓋百分比(覆蓋率)在很多應用中是核心指標。

衛星區域覆蓋分析方法主要包括解析法、基于幾何運算的方法和網格點法。解析法[4]基于衛星與地球的幾何關系直接得到覆蓋面積計算的解析公式,只適用于單顆衛星且目標區域包含衛星覆蓋范圍的情況?；趲缀芜\算的方法[5-7]在經緯度平面上利用多邊形布爾運算計算覆蓋指標,其中,文獻[5]算法只適用于衛星瞬時覆蓋,文獻[6]算法的通用性和效率更高。衛星區域覆蓋分析的經典算法是數值仿真的網格點法[8],該方法實現簡單,但計算量大、空間復雜度高、計算結果精度受網格大小影響,文獻[9-10]均直接采用網格點法。為提高網格點法的效率,研究者對原始的網格點法進行改進,其中,文獻[11]利用網格點的空間相關性和邊界特征,提出“池中投石法”“油環點火法”和“逐步吸收法”3種優化技術,文獻[12]對網格點的衛星覆蓋時刻集進行優化,文獻[13]提出經度條帶法,對每個條帶應用解析方法。

網格點法的效率瓶頸為衛星采樣點與網格點覆蓋關系計算次數多,且網格點信息記錄次數多。針對以上問題,本文算法通過掃描線與覆蓋帶多邊形求交,將逐采樣點、網格點計算優化為一次處理一個覆蓋條帶和一行網格點,并把掃描線劃分為具有相同覆蓋屬性的分段,省略了網格點信息記錄過程。

1 基于網格點的掃描線構造與數據維護

1.1 網格點法原理

網格點法的基本原理是:在經緯度平面上根據目標區域的包圍盒劃分網格,有等經緯度網格和等面積網格2種劃分策略[14],以網格中心點代表網格進行計算;按給定步長計算衛星采樣點,計算并記錄衛星采樣點對網格點的覆蓋情況;通過統計網格點覆蓋信息得到覆蓋指標,如覆蓋網格點數除以總網格點數得到覆蓋率。

算法需判斷每個衛星采樣點與網格點的位置關系,同時記錄每個網格點的覆蓋信息,因此時空復雜度均較高。

1.2 掃描線及其數據結構

掃描線是計算機圖形學中的經典技術[15],其基于目標區域的剖分網格定義掃描線,并利用掃描線實現衛星區域覆蓋指標的快速計算。

如圖1(a)所示,目標區域按等面積原則進行網格劃分(實際空間大小接近,經緯度平面不均勻,緯度越高,網格越大),其中A、a、b等圓點為網格中心點。每行內各網格大小相同,網格中心點緯度值相同,構成水平掃描線,如圖1(a)中1、2、3所指示的水平線。

掃描線劃分為互不重疊的段,如圖1(a)中掃描線2分為ab、cd、ef3個段。段數據結構定義為:

struct Seg{

int x0,x1;

vector satellites;

vector times;}

其中包括幾何和覆蓋屬性2類信息。以端點表示段幾何信息,端點采用整型數據類型,以避免導致過細的段劃分。覆蓋屬性包括覆蓋衛星及覆蓋時間,每個段的覆蓋屬性一致,可有多衛星覆蓋段或同一衛星多次覆蓋段。

每條掃描線由不重疊且坐標值由小到大的有序Seg數組構成,所有掃描線數據再組織為數組。如圖1(b)所示,目標區域在緯度被劃分為100行,采用100個元素的數組存儲。其中掃描線50共有200個網格點,被分為3段,網格點50～80被Sat0覆蓋,網格點110～130同時被Sat0和Sat1覆蓋,網格點150～170被Sat1在不同時間進行2次覆蓋。

圖1 目標區域網格的掃描線及其數據結構Fig.1 Scanline of the target area grid and its data structure

1.3 掃描線數據維護方法

掃描線段數組初始為空,計算過程中不斷插入新段,插入過程需保持數組中段不重疊、有序。

在插入新段時,按序判斷與原有各段關系并進行處理,如圖2所示,新插入段cd與已有段ab有5種位置關系:1)cd全部位于ab左側,將cd插入到段數組ab之前;2)cd部分位于ab左側、部分位于ab之間,從數組中刪除ab段,將ca段(覆蓋屬性同cd)、ad段(覆蓋屬性為ab合并cd)、db段(覆蓋屬性同ab)插入數組;3)cd全部位于ab之間,從數組中刪除ab段,將ac段(覆蓋屬性同ab)、cd段(覆蓋屬性為ab合并cd)、db段(覆蓋屬性同ab)插入數組;4)cd部分位于ab之間、部分位于ab右側,從數組中刪除ab段,將ac段(覆蓋屬性同ab)、cb段(覆蓋屬性為ab合并cd)插入數組,構造bd段(覆蓋屬性同cd),繼續將其與數組中后續段進行處理;5)cd全部位于ab右側,繼續將其與數組中后續段進行處理。在上述過程中,需避免段之間重疊,如假設第2)種情況a點坐標為10,則形成的新段范圍為(c,9)、(10,d)。

圖2 待插入段與已有段的位置關系
Fig.2Relationships between positions of the segment to be inserted and the existing segment

2 衛星區域覆蓋分析算法

本文算法步驟具體如下:

步驟1計算目標區域包圍盒并進行網格劃分,得到各掃描線緯度值和經度范圍。如圖3所示,目標區域為ABCDEFG,根據其包圍盒進行網格劃分。

圖3 衛星區域覆蓋分析算法原理Fig.3 Principle of the statellite regional coverage analysis algorithm

步驟2掃描線與目標區域求交,相交部分作為初始計算對象,參與后續計算。在圖3中,第2條掃描線與區域求交結果為ab、cd,將其作為初始計算對象。

步驟3計算衛星覆蓋在經緯度平面的投影,得到覆蓋帶多邊形,如圖3中多邊形1234所示。

步驟4對于每條掃描線,計算所有覆蓋帶多邊形與初始計算對象的交,并根據衛星信息構造段數據結構,插入掃描線段數組中。在圖3中,ab與覆蓋帶相交結果為eb,根據衛星信息構造Seg數據結構,插入第2行掃描線的段數組中。

步驟5遍歷所有掃描線的所有段,統計滿足條件的覆蓋網格數。在圖3中,如eb段滿足統計條件,覆蓋網格數為b-e+1。在計算總覆蓋率時,所有段均滿足要求,以網格點數除以總網格點數得到總覆蓋率。

在本文算法中,以段代表其上所有網格點,幾何運算本身決定了段與其網格點具有相同的覆蓋關系,與直接計算網格點相比不會發生錯判。

3 算法實現中的關鍵技術

3.1 覆蓋帶多邊形生成

根據上文算法步驟生成目標區域過境時間范圍內的覆蓋帶多邊形。每個衛星采樣點對應2個覆蓋帶邊界點,計算衛星采樣點位置和覆蓋角所確定射線與地球表面的交點,根據交點坐標計算經緯度。在圖4中,A、a、B、b等點為覆蓋帶邊界點。

圖4 覆蓋帶多邊形生成過程Fig.4 Generation process of coverage band polygons

覆蓋帶多邊形生成算法的偽代碼具體如下:

generateCoveragePolygon{

for(每個衛星采樣點){

if(采樣點連線與目標區域有交){

if(無已構造覆蓋多邊形){

構造點表lpts和rpts;

并將前一組邊界點輸出到點表中;}

將邊界點分別輸出到兩點表中;}

else if(點表不空){

邊界點輸出到兩點表,

合并兩點表為多邊形并輸出;}}}

在圖4中,Aa、Bb與目標區域無交,不必處理;Cc與目標區域有交,需將BC輸出到點表lpts中,bc輸出到點表rpts中;依次處理,將DE加入到lpts,de加入到rpts中;Ff不再與目標區域相交,將Ff分別輸出到兩點表,此時lpts中為BCDEF,rpts中為bcdef,合并點表,得到覆蓋帶多邊形bcdefFEDCB。

3.2 掃描線與多邊形求交

在本文算法中,掃描線需與目標區域多邊形和覆蓋帶多邊形求交,具體步驟如下:

步驟1計算掃描線所在水平直線與多邊形的所有交點并排序。如圖5所示,對應掃描線AB到KM的交點集合分別為{1,2,3,4},{5,6},{7,8},{9,10},{11,12},{13,14}。

圖5 掃描線與多邊形的求交過程Fig.5 Intersection process of scanlines and polygons

步驟2處理掃描線起點。若起點位于所有交點右側,則清空交點集合,轉步驟4,如圖5中的掃描線IJ;若起點位于所有交點左側,則轉步驟3,如圖5中的掃描線AB、CD、KM;否則,將起點插入到交點數組,并刪除起點左側所有交點,如圖5中的掃描線GH交點集合變為{G,10}。此時,交點集合變為{1,2,3,4},{5,6},{E,8},{G,10},{ },{13,14}。

步驟3處理掃描線終點。若終點位于所有交點左側,則清空交點集合,轉步驟4,如圖5中的掃描線KM;若終點位于所有交點右側,則轉步驟4,如圖5中的掃描線AB;否則,將終點插入到交點數組,并刪除終點右側所有交點,如圖5中的掃描線GH交點集合變為{G,H}。此時,交點集合變為{1,2,3,4},{5,D},{E,8},{G,H},{ }。

步驟4交點數組中每2個交點形成一個輸出段,圖5中輸出段為12、34、5D、E8、GH。

4 算法精度、效率及算例分析

4.1 算法精度分析

網格點法以網格點代表目標區域,計算結果存在誤差,精度取決于網格大小(網格點距離)和衛星采樣頻率,網格點和衛星采樣點越密,精度越高。

多星區域覆蓋分析計算本身無解析解,現有研究大多以網格點法隨網格縮小所逼近的值作為分析依據,如將每千米的經線數作為計算精度,其實質仍是網格越密,精度越高。

本文算法以段代表包含的網格點,對于每個網格點的判斷與網格點法一致,因此精度與網格點法一致,影響因素是掃描線間距(掃描線基于網格點定義,間距與網格點密度一致)和衛星采樣點密度。

4.2 算法效率分析

本文算法通過覆蓋帶多邊形過濾未過境衛星采樣點,傳統網格點法也可通過其他技術進行過濾,因此假定2種算法都僅能計算過境時間范圍采樣點。

設衛星過境次數為k,過境采樣點數與步長、區域大小等有關,設為常數c。目標區域網格數設為m行n列。

在傳統網格點法中,采樣點與網格點覆蓋關系判斷時間復雜度為O(ckmn),網格點信息記錄時間復雜度也為O(ckmn)(每個網格點需多次記錄信息)。每個網格點都需記錄信息,因此空間復雜度為O(mn)。

本文算法掃描線與覆蓋多邊形相交計算時間復雜度為O(km),如基于覆蓋多邊形頂點數分析的時間復雜度為O(ckm),但此時基本計算是坐標比較,效率遠高于網格點法中的覆蓋判斷。掃描線處理過程中需插入新段,段數最大與過境次數相等,因此插入新段的時間復雜度為O(k),一行掃描線處理段的時間復雜度為O(k2),全部掃描線處理段的時間復雜度為O(mk2)。因此,總的時間復雜度為O(ckm)+O(mk2)。一般應用中k值遠小于n,O(ckm)+O(mk2)遠優于網格點法的O(ckmn)。由于掃描線采用整型數據類型定義段,在極端情況k>n時,段數不超過n,此時算法時間復雜度為O(ckm)+O(mkn),效率仍遠優于網格點法。本文算法空間復雜度取決于段的數量,為O(mk),但k>n時算法空間復雜度會限制在O(mn)內。

4.3 算例分析

通過網格點法[8]、文獻[12]算法和本文算法對2個算例進行覆蓋分析:算例1，目標區域為凹多邊形，跨度約為20°，包含8顆衛星、過境22次；算例2，目標區域為凹多邊形，跨度為3°，包含12顆衛星、過境29次。算例1和算例2的耗時如表1、表2所示。由此可知,本文算法效率高于網格點法,網格數越多,效率提升越明顯,在網格數量超過80萬時,耗時僅為網格點法的1.19%。

表1 算例1耗時對比Table 1 Comparison of consumed time in Example 1

表2 算例2耗時對比Table 2 Comparison of consumed time in Example 2

5 結束語

本文利用網格點的空間相關性,基于掃描線思想實現覆蓋帶多邊形生成、掃描線與多邊形求交等關鍵技術,完成網格覆蓋計算的批量處理。算例分析結果表明,本文算法的時間復雜度和空間復雜度均優于傳統網格點法,尤其適用于大范圍非規則目標區域的高精度衛星覆蓋指標計算。下一步將在提高衛星區域覆蓋分析效率的同時,對時間覆蓋百分比、最大重訪時間等相關指標的計算問題進行研究。