李愷 張晗 康曉軍

（北京機(jī)電研究所，北京 100094）

0 引言

當(dāng)衛(wèi)星在軌飛行過(guò)程中要求進(jìn)行太陽(yáng)閃耀觀測(cè)時(shí)，控制軟件在判斷衛(wèi)星星下點(diǎn)所在位置滿足觀測(cè)條件后，才可進(jìn)行觀測(cè)。因?yàn)樾l(wèi)星星下點(diǎn)與海岸線地圖的相對(duì)位置實(shí)時(shí)變化，所以在整個(gè)觀測(cè)過(guò)程中，需要根據(jù)最新更新的軌道要素?cái)?shù)據(jù)，實(shí)時(shí)判斷觀測(cè)條件是否滿足，這要求判斷算法快速完成任務(wù)。

實(shí)際工程中，將以星下點(diǎn)為中心的矩形區(qū)域與海岸線地圖的位置關(guān)系作為判斷能否進(jìn)行太陽(yáng)閃耀觀測(cè)的條件。當(dāng)矩形處于海洋區(qū)域時(shí)，可以觀測(cè)；當(dāng)矩形與海洋區(qū)域相交或在陸地區(qū)域時(shí)，不可以觀測(cè)。

上述問(wèn)題類似于計(jì)算機(jī)圖形學(xué)[1]中，利用指定區(qū)域?qū)χ付ú灰?guī)則多邊形進(jìn)行截取，并顯示截取部分。但本文只需確定不規(guī)則多邊形與指定區(qū)域的位置關(guān)系，截取部分的實(shí)際形狀不是必須得到的。所以，本文所述問(wèn)題即可被等效為如何快速準(zhǔn)確地判定矩形（星下點(diǎn)矩形）與不規(guī)則多邊形（陸地區(qū)域）的位置關(guān)系問(wèn)題。

對(duì)于矩形和不規(guī)則多邊形的位置關(guān)系[2]如圖1所示，分相交、外部和內(nèi)部三種情況。所使用的算法必須能區(qū)分清楚這三種情況。

常用解決算法分兩種[3]，一種是以Cohen-Sutherland算法為代表的直線段裁剪法，另一種是以Sutherland-Hodgman算法為代表的多邊形裁剪法。

Cohen-Sutherland算法[4]首先將矩形區(qū)域四邊所在直線延長(zhǎng)，將整個(gè)平面分成9個(gè)區(qū)域并分別賦不同碼值。然后根據(jù)組成多邊形的各邊端點(diǎn)所在位置對(duì)應(yīng)碼值，依次判斷相鄰線段與矩形的位置關(guān)系，最終得到多邊形與矩形的位置關(guān)系。其弊端在于僅是孤立地處理被裁剪線段兩端點(diǎn)，沒(méi)有得到整根線段的整體信息，不可避免的會(huì)求取無(wú)效交點(diǎn)，降低運(yùn)算效率[5]。并且如果需對(duì)多邊形裁剪，需要將所有邊等效為獨(dú)立線段，經(jīng)多次重復(fù)計(jì)算才可得到最終結(jié)果[6]。

針對(duì)上述缺陷，Sutherland-Hodgman算法是將多邊形關(guān)于矩形的裁剪等效為多邊形關(guān)于矩形四邊所在直線的裁剪，此算法充分利用了線段與被裁剪多邊形位置關(guān)系信息，沒(méi)有無(wú)用運(yùn)算，而且算法采用流水線方式執(zhí)行，更易于硬件執(zhí)行[7-8]。主要缺點(diǎn)在于只適用于凸多邊形，如果是凹多邊形，需要將其分解為多個(gè)凸多邊形分別判斷[9]。

根據(jù)實(shí)際應(yīng)用，耀斑觀測(cè)只需要矩形與多邊形的位置關(guān)系信息，不需得到如果兩者相交，交點(diǎn)連線截取部分的具體形狀信息。上述兩種算法[10]實(shí)現(xiàn)過(guò)程中都會(huì)進(jìn)行交點(diǎn)求取計(jì)算，以便得到截取形狀信息，增加數(shù)學(xué)計(jì)算量，降低了軟件運(yùn)行速度，與耀斑計(jì)算要求的實(shí)時(shí)性相悖[11]。為此，本文提出一種新算法，將矩形與多邊形等效為多條線段，僅通過(guò)比較兩者等效線段位置關(guān)系即可得到矩形與多邊形的位置關(guān)系。

1 等效線段法

首先，將矩形區(qū)域和多邊形區(qū)域分別離散為一組線段的集合。若僅使用離散的坐標(biāo)點(diǎn)只能描述矩形與多邊形邊界而無(wú)法描述其內(nèi)部區(qū)域。在這里期望將矩形邊界及其內(nèi)部區(qū)域均表示出來(lái)，所以采用在矩形區(qū)域內(nèi)，選取間隔為1°的線段來(lái)等效矩形的方式描述矩形。等效結(jié)果如圖2（a）所示，矩形區(qū)域被等效成一組（五根）等間距線段（豎直粗實(shí)線）的集合。

同理，代表海岸線地圖的不規(guī)則多邊形也可用此種方法分割成多條等效線段。針對(duì)給出的描述海岸線地圖輪廓的數(shù)據(jù)，每個(gè)坐標(biāo)點(diǎn)的經(jīng)緯度分辨率為1°，如圖2（b）所示，不規(guī)則多邊形的輪廓用細(xì)實(shí)線描述。假設(shè)將多邊形內(nèi)部沿X軸方向分割，以粗直線AB所在的X軸坐標(biāo)為例，將多邊形內(nèi)部沿Y軸方向分割成幾個(gè)區(qū)域。粗直線與多邊形內(nèi)部的交點(diǎn)分別為C、D。分割的區(qū)域分別為AC、CD、DB。其中CD屬于多邊形內(nèi)部，則在此X軸坐標(biāo)下，線段CD用來(lái)描述多邊形內(nèi)部。這樣，整個(gè)多邊形內(nèi)部就可用其X軸方向上，每個(gè)坐標(biāo)值對(duì)應(yīng)的Y軸方向分割線段的集合（不規(guī)則多邊形內(nèi)的細(xì)虛線）來(lái)描述。

圖2（a）也描述了線段表述的多邊形和矩形的位置關(guān)系，分別是包含（s2）、相交（s3）、不包含（s1）。從圖中可以看出，判斷多邊形與矩形的位置關(guān)系，需要判斷所有組成矩形的線段與對(duì)應(yīng)X軸坐標(biāo)下，所有組成多邊形的線段的位置關(guān)系。線段的位置利用線段上下端點(diǎn)對(duì)應(yīng)的Y軸坐標(biāo)描述。判定途徑有兩種：1）如果矩形全部在多邊形內(nèi)部或者與其相交，即判定矩形不在或不全部在多邊形外部；2）直接判定矩形與多邊形內(nèi)部無(wú)相交或包含成分。

矩形全部在多邊形內(nèi)部或者與其相交的情況分4種（如圖3所示）[7]，AB虛線段為多邊形描述線段，粗實(shí)線為矩形描述線段，兩者均在同一X軸坐標(biāo)下，這里為清晰可見(jiàn)而分開。依次描述的情況為：①多邊形描述線段的下端點(diǎn)在矩形描述線段內(nèi)部，上端點(diǎn)不在內(nèi)部；②多邊形描述線段的上端點(diǎn)在矩形描述線段的內(nèi)部，下端點(diǎn)不在內(nèi)部；③多邊形描述線段的上下端點(diǎn)均在矩形描述線段的外部；④多邊形描述線段的上下端點(diǎn)均在矩形描述線段內(nèi)部。上述任一結(jié)果出現(xiàn)，說(shuō)明矩形描述線段與多邊形相交或者相互包含。

在依次判定比較每?jī)筛€段位置關(guān)系過(guò)程中，只要比較結(jié)果出現(xiàn)上述4種情況中任何一種，即可判定矩形不在多邊形外部，即為包含或者相交的情況。

圖3 矩形全部在多邊形內(nèi)部（或者與其相交）情況下的等效線段位置關(guān)系Fig.3 Location relation between equivalent lines

矩形與多邊形內(nèi)部無(wú)相交或包含成分的情況分為兩種（如圖4所示），依次描述的情況為：①多邊形描述線段整體在矩形描述線段的上部；②多邊形描述線段整體在矩形描述線段的下部。上述任一結(jié)果出現(xiàn)，只能說(shuō)明該矩形描述線段全部在多邊形外部。

在依次判定比較每?jī)筛€段位置關(guān)系過(guò)程中，必須將描述矩形區(qū)域線段集合的每一條線段與相應(yīng)X坐標(biāo)下，描述多邊形區(qū)域的所有線段分別進(jìn)行比較，結(jié)果只出現(xiàn)上述兩種情況，才可判定矩形全部在多邊形外部。

圖4 矩形與多邊形內(nèi)部無(wú)相交（或包含）情況下的等效線段位置關(guān)系Fig.4 Location relation between lines

2 程序設(shè)計(jì)與實(shí)現(xiàn)

按照上述算法實(shí)現(xiàn)地圖匹配，海岸線點(diǎn)坐標(biāo)無(wú)需被依次存儲(chǔ)，只需依次存儲(chǔ)所有描述線段的上下端點(diǎn)坐標(biāo)值即可。若按經(jīng)度索引，緯度范圍±90o，因此每個(gè)線段只需1byte空間，而按照緯度進(jìn)行索引時(shí)，需存儲(chǔ)線段上下端點(diǎn)經(jīng)度值，經(jīng)度范圍±180o，每個(gè)線段需2byte存儲(chǔ)空間。所以按經(jīng)度索引可節(jié)省一半的存儲(chǔ)空間，故而選用經(jīng)度索引描述地圖。

不同經(jīng)度下的描述線段個(gè)數(shù)不同，這里為便于程序?qū)崿F(xiàn)，記錄所有經(jīng)度下，描述線段數(shù)最多的個(gè)數(shù)作為所有經(jīng)度的描述線段個(gè)數(shù)，這樣任意經(jīng)度對(duì)應(yīng)的描述線段存儲(chǔ)空間大小一致，便于程序處理。如果實(shí)際經(jīng)度的描述線段較少，均填充90占位。因?yàn)閷?shí)際矩形區(qū)域能夠到達(dá)的區(qū)域緯度小于90°，故而判定結(jié)果必為：全在陸地區(qū)。

表1為地圖數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。

表1 等效線段法的地圖數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)Tab.1 Memory structure formap data of equivalent linesmethod

算法實(shí)現(xiàn)采用不全在海洋區(qū)域的判定途徑，因?yàn)楦鶕?jù)上文所述，此途徑的比較次數(shù)較少，更加省時(shí)。上述四種情況的第三種可以歸為第一種和第二種情況的組合，所以判斷條件成立的情況減為三種。

為節(jié)約計(jì)算時(shí)間，首先判定矩形的經(jīng)度跨度是否在地圖的經(jīng)度跨度區(qū)間內(nèi)。另外，假設(shè)實(shí)際衛(wèi)星所能運(yùn)行到的緯度區(qū)域確定（實(shí)際為±60°），如果矩形超出此區(qū)域，不進(jìn)行耀斑計(jì)算，設(shè)為進(jìn)入陸地區(qū)。具體計(jì)算流程如圖5所示。

圖5 等效線段法流程Fig.5 Flow chartof equivalent linesmethod

此算法的核心部分在于三種情況的判斷，即比較矩形描述線段上下端點(diǎn)的坐標(biāo)值（yt，yb）與地圖描述線段上下端點(diǎn)坐標(biāo)（YT，YB）的大小關(guān)系：1）YBYT，且yb

首幅地圖判定完畢后，如果矩形判定為在“海洋區(qū)”，即可結(jié)束判斷流程。否則調(diào)入第二幅地圖數(shù)據(jù)，重新進(jìn)行計(jì)算流程，判斷是否落入第二幅地圖的“海洋區(qū)”。從而最終確定矩形與海岸線地圖的位置關(guān)系。

3 實(shí)驗(yàn)結(jié)果分析

根據(jù)工程需要，軟件需快速地判斷出衛(wèi)星能否進(jìn)行耀斑計(jì)算，并執(zhí)行相應(yīng)的動(dòng)作。判斷時(shí)間過(guò)長(zhǎng)會(huì)影響衛(wèi)星進(jìn)行耀斑觀測(cè)的準(zhǔn)確度。為此，通過(guò)表2來(lái)對(duì)上述三種算法判定時(shí)間進(jìn)行總結(jié)[12-13]。

表2 三種算法實(shí)現(xiàn)的計(jì)算量比較Tab.1 The comparison of calculation amountbetween the threemethod

為了比較3種算法的執(zhí)行時(shí)間，這里首先給出實(shí)際海岸線地圖與星下點(diǎn)矩形的基本信息，并按每種算法的計(jì)算量最大時(shí)所用時(shí)間進(jìn)行比較，圖6為海岸線地圖實(shí)際形狀。

圖6 地球指定區(qū)域海岸線地圖Fig.6 Coast linemap of the certain earth area

實(shí)際組成地圖的線段個(gè)數(shù)為881條，不規(guī)則排列并依次首尾銜接，兩條線段銜接點(diǎn)坐標(biāo)均為整數(shù)經(jīng)緯度，同一經(jīng)度對(duì)應(yīng)的緯度描述線段最多3條。實(shí)際要求的星下點(diǎn)矩形經(jīng)度跨度11°，緯度跨度2°。星下點(diǎn)矩形的位置完全由衛(wèi)星的運(yùn)行軌跡確認(rèn)，由于每軌軌跡均不相同，默認(rèn)星下點(diǎn)能夠覆蓋海岸線地圖的所有地方。當(dāng)矩形中心點(diǎn)坐標(biāo)為（91°，22°）時(shí)，出現(xiàn)與地圖交點(diǎn)個(gè)數(shù)最多情況（共7個(gè)交點(diǎn)，上邊、下邊、右邊各2個(gè)，左邊1個(gè)），表3的相交時(shí)間即利用此時(shí)矩形位置計(jì)算。

算法使用80c32單片機(jī)利用C語(yǔ)言編寫，12MHz外部鐘頻。表3給出了矩形與地圖相交、在地圖內(nèi)部、外部時(shí)，三種算法各自的執(zhí)行時(shí)間。等效線段法在實(shí)際使用中，無(wú)需準(zhǔn)確區(qū)分內(nèi)部與相交，只要確認(rèn)其位置關(guān)系為其中之一。如文章第二節(jié)所述，只需區(qū)分矩形在陸地區(qū)或在海洋區(qū)，這使得計(jì)算時(shí)間可以進(jìn)一步減小。

表3 三種算法實(shí)現(xiàn)的計(jì)算時(shí)間比較Tab.3 Comparison of calculation time between the threemethods s

由表3結(jié)果可以看出，Cohen-Sutherland算法與Sutherland-Hodgman算法將大量的時(shí)間用于求取矩形與地圖交點(diǎn)，因?yàn)閮煞N算法均需利用交點(diǎn)求取裁剪線段形狀[14]，但這并不是實(shí)際必需要求實(shí)現(xiàn)的，而且關(guān)于線段間位置的判斷均多于地圖線段組成數(shù)量。等效線段法無(wú)需求取交點(diǎn)，且判斷次數(shù)很少，根據(jù)實(shí)際矩形與地圖描述線段組成個(gè)數(shù)，當(dāng)位置關(guān)系為外部和內(nèi)部時(shí)，需要判斷33次；相交則最多需要判斷33次，即最大判斷次數(shù)為矩形經(jīng)度坐標(biāo)跨度與海岸線地圖緯度描述線段個(gè)數(shù)之積（如果判斷過(guò)程中已經(jīng)確定相交位置關(guān)系，終止判斷）。由上述分析可知，等效線段法僅有少量的判斷次數(shù)，實(shí)現(xiàn)更為快速，因此更能滿足耀斑觀測(cè)的實(shí)時(shí)快速要求。

等效線段法的地圖數(shù)據(jù)總存儲(chǔ)空間（1 766 byte）遠(yuǎn)小于直接存儲(chǔ)地圖坐標(biāo)點(diǎn)的存儲(chǔ)空間（2 643 byte），原因是坐標(biāo)點(diǎn)存儲(chǔ)法中每個(gè)緯度需要1 byte存儲(chǔ)空間，經(jīng)度需要2 byte，而等效線段法的坐標(biāo)點(diǎn)均只需1 byte；程序代碼方面上述三種算法占用空間大小近似，均在1kbyte左右。綜上比較，等效線段法內(nèi)存消耗更小。

等效線段法的計(jì)算精度完全取決于海岸線地圖描述坐標(biāo)的分辨率。星下點(diǎn)矩形的大小固定，中心由衛(wèi)星的位置實(shí)時(shí)確定。由于實(shí)際工程中，地圖的最小分辨率為1°，當(dāng)衛(wèi)星星下點(diǎn)經(jīng)度坐標(biāo)出現(xiàn)小數(shù)時(shí)，必須對(duì)其取整，以便星下點(diǎn)矩形描述線段能夠和海岸線地圖描述線段在經(jīng)度坐標(biāo)上一一對(duì)應(yīng)。所以，求得的星下點(diǎn)經(jīng)度必須進(jìn)行四舍五入，等效線段法的計(jì)算精度會(huì)因此下降。當(dāng)星下點(diǎn)矩形處于海岸線地圖邊界時(shí)，可能導(dǎo)致兩者位置關(guān)系判斷結(jié)果與實(shí)際不符。但是，可以通過(guò)提高海岸線地圖坐標(biāo)的分辨率來(lái)提高判讀精度，因此消耗的額外計(jì)算量與地圖坐標(biāo)分辨率成正比增長(zhǎng)。由表1可知，Cohen-Sutherland算法與Sutherland-Hodgman算法的計(jì)算量與地圖坐標(biāo)的分辨率也是成正比增長(zhǎng)的，所以等效線段法仍具有實(shí)時(shí)快速的優(yōu)點(diǎn)。經(jīng)驗(yàn)證，1°的經(jīng)緯度分辨率已能滿足工程需要，無(wú)需再提高地圖坐標(biāo)分辨率。

4 結(jié)論

為了準(zhǔn)確快速地判定耀斑觀測(cè)能否進(jìn)行，本文提出了一種新的算法——等效線段法，并且給出了具體原理與軟件實(shí)現(xiàn)流程。通過(guò)實(shí)踐證明，該算法因無(wú)需得出截取圖形形狀，而避免了交點(diǎn)求取計(jì)算，僅需少量次數(shù)的數(shù)值大小比較就可得到衛(wèi)星視場(chǎng)與海洋位置關(guān)系，能夠更加快速地判斷耀斑觀測(cè)條件是否滿足，而且占用較少的軟件資源。

（References）

[1] 唐云,羅俊松.計(jì)算機(jī)圖形技術(shù)在數(shù)據(jù)計(jì)算方面的應(yīng)用[J].制造業(yè)自動(dòng)化,2010,32(11):198.TANG Yun,LUO Junsong.Application of Computer Graphics Technology in Data of Computation[J].Manufacturing Automation,2010,32(11):198.(in Chinese)

[2] New ManW M,Sproull R F.Principals of Interactive Computer Graphics[M].M cGraw-Hill New York,1979.

[3] 彭歡,陸國(guó)棟,譚建榮.基于端點(diǎn)與交點(diǎn)編碼的矩形窗口多邊形裁剪新算法[J].工程圖學(xué)學(xué)報(bào),2006,27(4):72-76.PENG Huan,LU Guodong,TAN Jianrong.A New Algorithm of Polygon Clipping Against RectangularWindow Based on the Endpointand Intersection-point Encoding[J].Manufacturing Automation,2006,27(4):72-76.(in Chinese)

[4] 孔德慧,尹寶才,劉媛媛.對(duì)Cohen-Sutherland線段裁剪算法的改進(jìn)[J].北京工業(yè)大學(xué)學(xué)報(bào),2002,28(4):483.KONG Dehui,YIN Baocai,LIU Yuanyuan.Improvement in the Algorithm of Cohen-surtherland Segment Clipping[J].Journalof Beijing Polytechnic University,2002,28(4):483.(in Chinese)

[5] 嚴(yán)圣華.二維線段裁剪C-S算法的分析與改進(jìn)[C].全國(guó)第21屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議,2010.YAN Shenghua.The Improvement and Analysis of the Cohen-Sutherland Clipping Method[C].The 21st Computer Technology and Application Conference,2010.(in Chinese)

[6] 任洪海.一種基于直線區(qū)域劃分的線段裁剪算法[J].科學(xué)技術(shù)與工程,2008,8(13):3677.REN Honghai.Line Clipping Algorithm Based on Line Region-subdivision[J].Science Technology and Engineering,2008,8(13):3677.(in Chinese)

[7] Liang Y D,Barsky BA.An Analysis and Algorithm for Polygon Clipping[J].CACM,1983(26):11.

[8] 李建勝,張韶華,范東娟.一種基于線性求解的多邊形圖像裁剪方法[J].計(jì)算機(jī)工程與應(yīng)用,2008,39(6):170.LIJiansheng,ZHANG Shaohua,FAN Dongjuan.An Algorithm of Polygon Clipping Based on the Linear Solve Method[J].Computer Engineering and Applications,2008,39(6):170.(in Chinese)

[9] 王世萍,王志強(qiáng).多邊形裁剪通用算法[J].工程圖學(xué)學(xué)報(bào),1995,16(1):42-47.WANG Shiping,WANG Zhiqiang.A General Algorithm of the Polygon Clipping[J].Manufacturing Automation,1995,16(1):42-47.(in Chinese)

[10] 彭妮娜,王琨,李濤.地表雙向反射特性對(duì)遙感圖像的影響分析[J].航天返回與遙感,2011,32(4):45.PENG Nina,WANG Kun,LI Tao.Research of BRDF Effects on Remote Sensing Imagery[J].Spacecraft Recovery&Remote Sensing,2011,32(4):45.(in Chinese)

[11] Creiner G,Hormann K.EfficientClipping of Arbitrary Polygons[J].ACM Transactions on Graphics,1998,17(2):71-83.

[12] 張以成,馮西權(quán).線段二維裁剪與繪制的算法性能分析[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(6):170.ZHANG Yicheng,FENG Xiquan.Performance Analysis on Line Two-dimensional Clipping and Draw ing Algorithm[J].Computer Engineering and Applications,2013,49(6):170.(in Chinese)

[13] 歐中亞.計(jì)算機(jī)圖形學(xué)中二維裁剪算法的研究[J].中小企業(yè)管理與科技(上旬刊),2011(22):288-289.OU Zhongya.The Study of 2-D Clipping Algorithm Computer Graphics Technology[J].Management&Technology of SMEs,2011(22):288-289.(in Chinese)

[14] 徐洪學(xué).二維有向直線段常用裁剪算法裁剪效率比較[J].微型電腦應(yīng)用,1999(7):35.XU Hongxue.The Efficiency Comparison among the General Methods for 2-D Line Clipping[J].M icrocomputer Application,1999(7):35.(in Chinese)

[15] Southerland IE.AClipping Divider[M].FJCC,Thompson Books,Washington D.C,1968.