汪榮峰,胡 敏

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

0 概述

衛(wèi)星區(qū)域覆蓋分析廣泛應(yīng)用于衛(wèi)星任務(wù)規(guī)劃[1]、成像偵察[2]等航天任務(wù)中。衛(wèi)星區(qū)域覆蓋分析指標(biāo)[3]包括覆蓋重?cái)?shù)、面積覆蓋百分比、覆蓋累積面積、時(shí)間覆蓋百分比、最大重訪時(shí)間及平均重訪時(shí)間等,其中面積覆蓋百分比(覆蓋率)在很多應(yīng)用中是核心指標(biāo)。

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

網(wǎng)格點(diǎn)法的效率瓶頸為衛(wèi)星采樣點(diǎn)與網(wǎng)格點(diǎn)覆蓋關(guān)系計(jì)算次數(shù)多,且網(wǎng)格點(diǎn)信息記錄次數(shù)多。針對(duì)以上問(wèn)題,本文算法通過(guò)掃描線與覆蓋帶多邊形求交,將逐采樣點(diǎn)、網(wǎng)格點(diǎn)計(jì)算優(yōu)化為一次處理一個(gè)覆蓋條帶和一行網(wǎng)格點(diǎn),并把掃描線劃分為具有相同覆蓋屬性的分段,省略了網(wǎng)格點(diǎn)信息記錄過(guò)程。

1 基于網(wǎng)格點(diǎn)的掃描線構(gòu)造與數(shù)據(jù)維護(hù)

1.1 網(wǎng)格點(diǎn)法原理

網(wǎng)格點(diǎn)法的基本原理是:在經(jīng)緯度平面上根據(jù)目標(biāo)區(qū)域的包圍盒劃分網(wǎng)格,有等經(jīng)緯度網(wǎng)格和等面積網(wǎng)格2種劃分策略[14],以網(wǎng)格中心點(diǎn)代表網(wǎng)格進(jìn)行計(jì)算;按給定步長(zhǎng)計(jì)算衛(wèi)星采樣點(diǎn),計(jì)算并記錄衛(wèi)星采樣點(diǎn)對(duì)網(wǎng)格點(diǎn)的覆蓋情況;通過(guò)統(tǒng)計(jì)網(wǎng)格點(diǎn)覆蓋信息得到覆蓋指標(biāo),如覆蓋網(wǎng)格點(diǎn)數(shù)除以總網(wǎng)格點(diǎn)數(shù)得到覆蓋率。

算法需判斷每個(gè)衛(wèi)星采樣點(diǎn)與網(wǎng)格點(diǎn)的位置關(guān)系,同時(shí)記錄每個(gè)網(wǎng)格點(diǎn)的覆蓋信息,因此時(shí)空復(fù)雜度均較高。

1.2 掃描線及其數(shù)據(jù)結(jié)構(gòu)

掃描線是計(jì)算機(jī)圖形學(xué)中的經(jīng)典技術(shù)[15],其基于目標(biāo)區(qū)域的剖分網(wǎng)格定義掃描線,并利用掃描線實(shí)現(xiàn)衛(wèi)星區(qū)域覆蓋指標(biāo)的快速計(jì)算。

如圖1(a)所示,目標(biāo)區(qū)域按等面積原則進(jìn)行網(wǎng)格劃分(實(shí)際空間大小接近,經(jīng)緯度平面不均勻,緯度越高,網(wǎng)格越大),其中A、a、b等圓點(diǎn)為網(wǎng)格中心點(diǎn)。每行內(nèi)各網(wǎng)格大小相同,網(wǎng)格中心點(diǎn)緯度值相同,構(gòu)成水平掃描線,如圖1(a)中1、2、3所指示的水平線。

掃描線劃分為互不重疊的段,如圖1(a)中掃描線2分為ab、cd、ef3個(gè)段。段數(shù)據(jù)結(jié)構(gòu)定義為:

struct Seg{

int x0,x1;

vector satellites;

vector times;}

其中包括幾何和覆蓋屬性2類信息。以端點(diǎn)表示段幾何信息,端點(diǎn)采用整型數(shù)據(jù)類型,以避免導(dǎo)致過(guò)細(xì)的段劃分。覆蓋屬性包括覆蓋衛(wèi)星及覆蓋時(shí)間,每個(gè)段的覆蓋屬性一致,可有多衛(wèi)星覆蓋段或同一衛(wèi)星多次覆蓋段。

每條掃描線由不重疊且坐標(biāo)值由小到大的有序Seg數(shù)組構(gòu)成,所有掃描線數(shù)據(jù)再組織為數(shù)組。如圖1(b)所示,目標(biāo)區(qū)域在緯度被劃分為100行,采用100個(gè)元素的數(shù)組存儲(chǔ)。其中掃描線50共有200個(gè)網(wǎng)格點(diǎn),被分為3段,網(wǎng)格點(diǎn)50～80被Sat0覆蓋,網(wǎng)格點(diǎn)110～130同時(shí)被Sat0和Sat1覆蓋,網(wǎng)格點(diǎn)150～170被Sat1在不同時(shí)間進(jìn)行2次覆蓋。

圖1 目標(biāo)區(qū)域網(wǎng)格的掃描線及其數(shù)據(jù)結(jié)構(gòu)Fig.1 Scanline of the target area grid and its data structure

1.3 掃描線數(shù)據(jù)維護(hù)方法

掃描線段數(shù)組初始為空,計(jì)算過(guò)程中不斷插入新段,插入過(guò)程需保持?jǐn)?shù)組中段不重疊、有序。

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

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

2 衛(wèi)星區(qū)域覆蓋分析算法

本文算法步驟具體如下:

步驟1計(jì)算目標(biāo)區(qū)域包圍盒并進(jìn)行網(wǎng)格劃分,得到各掃描線緯度值和經(jīng)度范圍。如圖3所示,目標(biāo)區(qū)域?yàn)锳BCDEFG,根據(jù)其包圍盒進(jìn)行網(wǎng)格劃分。

圖3 衛(wèi)星區(qū)域覆蓋分析算法原理Fig.3 Principle of the statellite regional coverage analysis algorithm

步驟2掃描線與目標(biāo)區(qū)域求交,相交部分作為初始計(jì)算對(duì)象,參與后續(xù)計(jì)算。在圖3中,第2條掃描線與區(qū)域求交結(jié)果為ab、cd,將其作為初始計(jì)算對(duì)象。

步驟3計(jì)算衛(wèi)星覆蓋在經(jīng)緯度平面的投影,得到覆蓋帶多邊形,如圖3中多邊形1234所示。

步驟4對(duì)于每條掃描線,計(jì)算所有覆蓋帶多邊形與初始計(jì)算對(duì)象的交,并根據(jù)衛(wèi)星信息構(gòu)造段數(shù)據(jù)結(jié)構(gòu),插入掃描線段數(shù)組中。在圖3中,ab與覆蓋帶相交結(jié)果為eb,根據(jù)衛(wèi)星信息構(gòu)造Seg數(shù)據(jù)結(jié)構(gòu),插入第2行掃描線的段數(shù)組中。

步驟5遍歷所有掃描線的所有段,統(tǒng)計(jì)滿足條件的覆蓋網(wǎng)格數(shù)。在圖3中,如eb段滿足統(tǒng)計(jì)條件,覆蓋網(wǎng)格數(shù)為b-e+1。在計(jì)算總覆蓋率時(shí),所有段均滿足要求,以網(wǎng)格點(diǎn)數(shù)除以總網(wǎng)格點(diǎn)數(shù)得到總覆蓋率。

在本文算法中,以段代表其上所有網(wǎng)格點(diǎn),幾何運(yùn)算本身決定了段與其網(wǎng)格點(diǎn)具有相同的覆蓋關(guān)系,與直接計(jì)算網(wǎng)格點(diǎn)相比不會(huì)發(fā)生錯(cuò)判。

3 算法實(shí)現(xiàn)中的關(guān)鍵技術(shù)

3.1 覆蓋帶多邊形生成

根據(jù)上文算法步驟生成目標(biāo)區(qū)域過(guò)境時(shí)間范圍內(nèi)的覆蓋帶多邊形。每個(gè)衛(wèi)星采樣點(diǎn)對(duì)應(yīng)2個(gè)覆蓋帶邊界點(diǎn),計(jì)算衛(wèi)星采樣點(diǎn)位置和覆蓋角所確定射線與地球表面的交點(diǎn),根據(jù)交點(diǎn)坐標(biāo)計(jì)算經(jīng)緯度。在圖4中,A、a、B、b等點(diǎn)為覆蓋帶邊界點(diǎn)。

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

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

generateCoveragePolygon{

for(每個(gè)衛(wèi)星采樣點(diǎn)){

if(采樣點(diǎn)連線與目標(biāo)區(qū)域有交){

if(無(wú)已構(gòu)造覆蓋多邊形){

構(gòu)造點(diǎn)表lpts和rpts;

并將前一組邊界點(diǎn)輸出到點(diǎn)表中;}

將邊界點(diǎn)分別輸出到兩點(diǎn)表中;}

else if(點(diǎn)表不空){

邊界點(diǎn)輸出到兩點(diǎn)表,

合并兩點(diǎn)表為多邊形并輸出;}}}

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

3.2 掃描線與多邊形求交

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

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

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

步驟2處理掃描線起點(diǎn)。若起點(diǎn)位于所有交點(diǎn)右側(cè),則清空交點(diǎn)集合,轉(zhuǎn)步驟4,如圖5中的掃描線IJ;若起點(diǎn)位于所有交點(diǎn)左側(cè),則轉(zhuǎn)步驟3,如圖5中的掃描線AB、CD、KM;否則,將起點(diǎn)插入到交點(diǎn)數(shù)組,并刪除起點(diǎn)左側(cè)所有交點(diǎn),如圖5中的掃描線GH交點(diǎn)集合變?yōu)閧G,10}。此時(shí),交點(diǎn)集合變?yōu)閧1,2,3,4},{5,6},{E,8},{G,10},{ },{13,14}。

步驟3處理掃描線終點(diǎn)。若終點(diǎn)位于所有交點(diǎn)左側(cè),則清空交點(diǎn)集合,轉(zhuǎn)步驟4,如圖5中的掃描線KM;若終點(diǎn)位于所有交點(diǎn)右側(cè),則轉(zhuǎn)步驟4,如圖5中的掃描線AB;否則,將終點(diǎn)插入到交點(diǎn)數(shù)組,并刪除終點(diǎn)右側(cè)所有交點(diǎn),如圖5中的掃描線GH交點(diǎn)集合變?yōu)閧G,H}。此時(shí),交點(diǎn)集合變?yōu)閧1,2,3,4},{5,D},{E,8},{G,H},{ }。

步驟4交點(diǎn)數(shù)組中每2個(gè)交點(diǎn)形成一個(gè)輸出段,圖5中輸出段為12、34、5D、E8、GH。

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

4.1 算法精度分析

網(wǎng)格點(diǎn)法以網(wǎng)格點(diǎn)代表目標(biāo)區(qū)域,計(jì)算結(jié)果存在誤差,精度取決于網(wǎng)格大小(網(wǎng)格點(diǎn)距離)和衛(wèi)星采樣頻率,網(wǎng)格點(diǎn)和衛(wèi)星采樣點(diǎn)越密,精度越高。

多星區(qū)域覆蓋分析計(jì)算本身無(wú)解析解,現(xiàn)有研究大多以網(wǎng)格點(diǎn)法隨網(wǎng)格縮小所逼近的值作為分析依據(jù),如將每千米的經(jīng)線數(shù)作為計(jì)算精度,其實(shí)質(zhì)仍是網(wǎng)格越密,精度越高。

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

4.2 算法效率分析

本文算法通過(guò)覆蓋帶多邊形過(guò)濾未過(guò)境衛(wèi)星采樣點(diǎn),傳統(tǒng)網(wǎng)格點(diǎn)法也可通過(guò)其他技術(shù)進(jìn)行過(guò)濾,因此假定2種算法都僅能計(jì)算過(guò)境時(shí)間范圍采樣點(diǎn)。

設(shè)衛(wèi)星過(guò)境次數(shù)為k,過(guò)境采樣點(diǎn)數(shù)與步長(zhǎng)、區(qū)域大小等有關(guān),設(shè)為常數(shù)c。目標(biāo)區(qū)域網(wǎng)格數(shù)設(shè)為m行n列。

在傳統(tǒng)網(wǎng)格點(diǎn)法中,采樣點(diǎn)與網(wǎng)格點(diǎn)覆蓋關(guān)系判斷時(shí)間復(fù)雜度為O(ckmn),網(wǎng)格點(diǎn)信息記錄時(shí)間復(fù)雜度也為O(ckmn)(每個(gè)網(wǎng)格點(diǎn)需多次記錄信息)。每個(gè)網(wǎng)格點(diǎn)都需記錄信息,因此空間復(fù)雜度為O(mn)。

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

4.3 算例分析

通過(guò)網(wǎng)格點(diǎn)法[8]、文獻(xiàn)[12]算法和本文算法對(duì)2個(gè)算例進(jìn)行覆蓋分析:算例1，目標(biāo)區(qū)域?yàn)榘级噙呅?，跨度約為20°，包含8顆衛(wèi)星、過(guò)境22次；算例2，目標(biāo)區(qū)域?yàn)榘级噙呅?，跨度?°，包含12顆衛(wèi)星、過(guò)境29次。算例1和算例2的耗時(shí)如表1、表2所示。由此可知,本文算法效率高于網(wǎng)格點(diǎn)法,網(wǎng)格數(shù)越多,效率提升越明顯,在網(wǎng)格數(shù)量超過(guò)80萬(wàn)時(shí),耗時(shí)僅為網(wǎng)格點(diǎn)法的1.19%。

表1 算例1耗時(shí)對(duì)比Table 1 Comparison of consumed time in Example 1

表2 算例2耗時(shí)對(duì)比Table 2 Comparison of consumed time in Example 2

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

本文利用網(wǎng)格點(diǎn)的空間相關(guān)性,基于掃描線思想實(shí)現(xiàn)覆蓋帶多邊形生成、掃描線與多邊形求交等關(guān)鍵技術(shù),完成網(wǎng)格覆蓋計(jì)算的批量處理。算例分析結(jié)果表明,本文算法的時(shí)間復(fù)雜度和空間復(fù)雜度均優(yōu)于傳統(tǒng)網(wǎng)格點(diǎn)法,尤其適用于大范圍非規(guī)則目標(biāo)區(qū)域的高精度衛(wèi)星覆蓋指標(biāo)計(jì)算。下一步將在提高衛(wèi)星區(qū)域覆蓋分析效率的同時(shí),對(duì)時(shí)間覆蓋百分比、最大重訪時(shí)間等相關(guān)指標(biāo)的計(jì)算問(wèn)題進(jìn)行研究。