基于Graham算法的飛行程序保護(hù)區(qū)邊界畫法

王坤

[摘 要]飛行程序保護(hù)區(qū)的輔助設(shè)計(jì)中，風(fēng)螺旋線作為轉(zhuǎn)彎機(jī)動(dòng)的限制邊界，其不規(guī)則性使得計(jì)算機(jī)難以精確繪制。文中對飛行程序保護(hù)區(qū)做出數(shù)學(xué)描述的同時(shí)引入Graham算法使得精確繪制不規(guī)則邊界成為可能，并且對比以斜率作為參考的粗糙的算法做時(shí)間復(fù)雜度的對比分析，最終設(shè)計(jì)程序證實(shí)了算法的可行性和高效性，為飛行程序保護(hù)區(qū)自動(dòng)繪制增添新的模型

[關(guān)鍵詞]輔助設(shè)計(jì)；風(fēng)螺旋線；Graham；時(shí)間復(fù)雜度

中圖分類號(hào)：V323；TP311.11 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2017）22-0360-03

1 引言

飛行程序設(shè)計(jì)工作中，計(jì)算機(jī)輔助設(shè)計(jì)隨著計(jì)算機(jī)科學(xué)和編程算法的發(fā)展已經(jīng)廣泛應(yīng)用，主要集中在對保護(hù)區(qū)中障礙物判斷以及保護(hù)區(qū)劃設(shè)等方面。目前區(qū)域結(jié)構(gòu)較為簡單的進(jìn)近程序和簡化的離場程序都已經(jīng)有了較為完整的輔助設(shè)計(jì)系統(tǒng)[1]，開發(fā)方法雖然不同，但難度集中在保護(hù)區(qū)結(jié)構(gòu)的準(zhǔn)確數(shù)學(xué)描述，因此造成了編程時(shí)沒有可以保證準(zhǔn)確性的算法結(jié)構(gòu)。飛行程序設(shè)計(jì)保護(hù)區(qū)的構(gòu)型中以風(fēng)螺旋線的位置特別且要求最嚴(yán)格，過去解決手段主要是直接調(diào)用編程語言相關(guān)函數(shù)[2]或者通過單點(diǎn)迭代利用直線擬合曲線進(jìn)而以點(diǎn)對點(diǎn)關(guān)系構(gòu)造相關(guān)區(qū)域[3]，這些方法可以在一定程度上解決飛行程序設(shè)計(jì)工作中風(fēng)螺旋線與其他圖元之間的結(jié)構(gòu)問題，不足在于由于需要調(diào)用特殊的函數(shù)無法在不同的開發(fā)環(huán)境中廣泛使用，當(dāng)某一個(gè)編程方法在飛行程序設(shè)計(jì)軟件的開發(fā)功能上顯得不足需要其他接口加入時(shí)，此類實(shí)現(xiàn)保護(hù)區(qū)劃設(shè)的方法則不具備通用性。因此，建立合適的數(shù)學(xué)模型，從算法結(jié)構(gòu)的角度解決飛行程序設(shè)計(jì)保護(hù)區(qū)中風(fēng)螺旋線與多種圖元相對關(guān)系是有必要實(shí)現(xiàn)的。

2 相關(guān)飛行程序

風(fēng)螺旋線表示航空器轉(zhuǎn)彎時(shí)每轉(zhuǎn)過一定角度受到內(nèi)風(fēng)的影響形成的轉(zhuǎn)彎偏移，圖1所示為航空器繞中心圓點(diǎn)飛行90°生成的風(fēng)螺旋線（wind spiral），在過去的手工繪圖中通常以若干正圓為輪廓線，通過各輪廓間的擬合得到保守的近似覆蓋最大范圍的風(fēng)螺旋線。近年來借鑒了機(jī)械，建筑領(lǐng)域中計(jì)算機(jī)制圖“阿基米德螺旋線”的概念[4]，遵循公式（1-1）可以將風(fēng)螺旋線這樣的極坐標(biāo)曲線用極小步長生成。

根據(jù)民航飛行程序設(shè)計(jì)工作的標(biāo)準(zhǔn)規(guī)范DOC8168，基線轉(zhuǎn)彎和直角程序中的保護(hù)區(qū)是在標(biāo)稱航跡的基礎(chǔ)上，由相對的位置關(guān)系在一定的區(qū)域繪制轉(zhuǎn)彎風(fēng)螺旋線，再由風(fēng)螺旋線構(gòu)成的保護(hù)區(qū)邊界區(qū)域生成包絡(luò)線確保飛行保護(hù)區(qū)的安全性最高。圖2為基線轉(zhuǎn)彎保護(hù)區(qū)，圖3（a）（b）為直角程序的模板及保護(hù)區(qū)生成過程。

這兩種程序都是航空器做轉(zhuǎn)彎機(jī)動(dòng)時(shí)使用的飛行程序，因此存在大量轉(zhuǎn)彎時(shí)需要確定的風(fēng)螺旋線的邊界，手工繪圖中為了保證人工操作的誤差不影響安全，采用圓近似替代風(fēng)螺旋線的簡易畫法，雖然保守的保證了航空器的飛行安全但是無形中擴(kuò)大了保護(hù)區(qū)范圍造成一定的空域浪費(fèi)。

3 算法設(shè)計(jì)

為了在空間中構(gòu)造準(zhǔn)確的飛行程序保護(hù)區(qū)邊界，必須建立非描述性的邊界曲線模型，利用地理坐標(biāo)的定位實(shí)現(xiàn)對已知的程序航跡計(jì)算數(shù)學(xué)模型可以很好的解決航跡的建模[5]，但對隨著參數(shù)變化位置不確定的保護(hù)區(qū)邊界，需要借鑒計(jì)算幾何學(xué)的方法尋找各結(jié)構(gòu)間的關(guān)系。要引入計(jì)算幾何算法首先要引入點(diǎn)集的概念[6]。

3.1 二維空間的幾何關(guān)系

在二維空間中，任意多邊形P有N個(gè)頂點(diǎn)，這些頂點(diǎn)構(gòu)成集合，稱為頂點(diǎn)序列。這些點(diǎn)按照出現(xiàn)順序排列為1，2…n，每一個(gè)頂點(diǎn)序列中的點(diǎn)均可用表示該點(diǎn)對應(yīng)坐標(biāo)。根據(jù)基線轉(zhuǎn)彎程序與直角程序設(shè)計(jì)的特點(diǎn)，實(shí)現(xiàn)包絡(luò)線是程序的關(guān)鍵。在幾何學(xué)中，曲線族的包絡(luò)線，是跟該曲線族的每條線都有至少一點(diǎn)相切的一條曲線。假設(shè)每條曲線為，設(shè)表示曲線與包絡(luò)線相切的點(diǎn)，包絡(luò)線為，要求出包絡(luò)線轉(zhuǎn)化為求出。

大的保護(hù)余度而又不需要為了切點(diǎn)的準(zhǔn)確改用簡易畫法繪制。

算法設(shè)計(jì)過程及簡圖如下：

①對所有點(diǎn)計(jì)算坐標(biāo)，選取值最小點(diǎn)，若存在多個(gè)相等的點(diǎn)，選取最小的點(diǎn)，以此選出最下方（或左下）點(diǎn)作為基準(zhǔn)點(diǎn)

②以水平軸方向?yàn)榛鶞?zhǔn)，逆時(shí)針方向，按照兩點(diǎn)連接的線段與基準(zhǔn)軸夾角的增大逐個(gè)掃描點(diǎn)，對于同樣夾角下，只加入離基準(zhǔn)點(diǎn)最遠(yuǎn)點(diǎn)的坐標(biāo)，以此順序形成點(diǎn)集

③先連接基準(zhǔn)點(diǎn)與所有點(diǎn)中夾角最小距離最近點(diǎn)得到初始線段，以與點(diǎn)集中按順序的下一點(diǎn)連接得另一線段

④按照平面坐標(biāo)的計(jì)算方法，運(yùn)算向量與向量的叉積，根據(jù)3.2節(jié)的向量關(guān)系，判斷與的方向關(guān)系（圖5（a））

⑤此處建立的坐標(biāo)系是以最左下的點(diǎn)為基準(zhǔn)，逆時(shí)針方向排列的點(diǎn)集，當(dāng)其中一個(gè)向量與下一向量之間的關(guān)系為順時(shí)針時(shí)，說明該處出現(xiàn)凹邊，移除并從點(diǎn)集中去除點(diǎn)，進(jìn)一步縮小點(diǎn)集規(guī)模（圖5（b））

⑥只需要將中已保存的點(diǎn)按順序執(zhí)行回到基準(zhǔn)點(diǎn)，剩余在點(diǎn)集中的點(diǎn)即為滿足凸包的點(diǎn)集

Graham算法下首先對所有平面內(nèi)的點(diǎn)通過極角與距離的關(guān)系做一次淘汰，剩余的點(diǎn)理論上是一個(gè)包圍的點(diǎn)集，若是以1°為步長，大約360個(gè)點(diǎn)，大大減少了需要搜索的點(diǎn)集規(guī)模。整個(gè)算法運(yùn)行中只有①步驟遍歷所有點(diǎn)，且只以基準(zhǔn)點(diǎn)一次遍歷時(shí)間復(fù)雜度為，步驟⑤時(shí)間復(fù)雜度為相比幾何關(guān)系下確定的要小的多，并且隨著風(fēng)螺旋線數(shù)量的增多優(yōu)勢越發(fā)顯著。

4 開發(fā)實(shí)例

前文中算法設(shè)計(jì)主要結(jié)合了平面向量與圖元分布，AutoCAD是當(dāng)前較為主流的平面設(shè)計(jì)軟件，其內(nèi)嵌的ALisp/VLisp語言采用面向過程的設(shè)計(jì)模式，表處理的語言結(jié)構(gòu)編寫快捷[7]，因此采用A/VLisp語言編譯插件實(shí)現(xiàn)保護(hù)區(qū)繪制的主體功能作為算法驗(yàn)證。

直角程序保護(hù)區(qū)的初始化參數(shù)輸入界面設(shè)計(jì)如圖6所示。

最終實(shí)現(xiàn)的基線轉(zhuǎn)彎與直角程序保護(hù)區(qū)自動(dòng)輔助設(shè)計(jì)程序可以根據(jù)基本飛行參數(shù)自行計(jì)算邊界點(diǎn)所在位置，使用Graham算法一次性生成多邊形邊界多線段，直角程序保護(hù)區(qū)取2000個(gè)點(diǎn)運(yùn)行時(shí)間只要0.4秒而基線轉(zhuǎn)彎程序保護(hù)區(qū)則是瞬間完成，圖7圖8是在程序中加入斷點(diǎn)分步執(zhí)行保護(hù)區(qū)生成程序的效果。

5 結(jié)論

本次程序開發(fā)中，對描述性的飛行程序保護(hù)區(qū)邊界用數(shù)學(xué)語言重新描述，并且根據(jù)平面空間的幾何特點(diǎn)，引入Graham算法在縮小空間有效點(diǎn)集規(guī)模的同時(shí)迅速找到邊界特征。在AutoCAD平臺(tái)下以ALisp/VLisp語言開發(fā)軟件核心部分同時(shí)以O(shè)penDCL設(shè)計(jì)友好簡潔界面，成功實(shí)現(xiàn)了保護(hù)區(qū)的自動(dòng)繪制，證明了算法思路符合通用特性，為飛行程序保護(hù)區(qū)自動(dòng)化實(shí)現(xiàn)提供了精確模型。

參考文獻(xiàn)

[1] 沈笑云，趙瑞，焦衛(wèi)東，等.基于 World Wind 的RNP飛行程序三維可視化仿真[J].系統(tǒng)仿真學(xué)報(bào)，2012， 24（010）：2131-2135.

[2] 吳潔明，符曉君.計(jì)算機(jī)輔助實(shí)現(xiàn)航空器基線轉(zhuǎn)彎程序設(shè)計(jì)的方法[J]. 航空計(jì)算技術(shù)，2006，36（4）： 17-20.

[3] 盧敏.基于GIS的飛行程序設(shè)計(jì)[J].2006.

[4] 張湘，郭坤州，夏宏玉，等.基于SolidWorks的漸開線齒輪建模方法研究[J].現(xiàn)代機(jī)械，2008 （4）：37-39.

[5] 李夏.儀表飛行程序三維呈現(xiàn)系統(tǒng)設(shè)計(jì)的初步研究[D][D].中國民用航空飛行學(xué)院，2011.

[6] Cormen T H，Leiserson C E， Rivest R L，et al.Introduction to algorithms[M].Cambridge：MIT press，2001.

[7] 王軍鋒，劉文清，王大勇等.等高線等間距高程自動(dòng)標(biāo)注的方法實(shí)現(xiàn)[J]. 測繪科學(xué)，2014（5）：150-152.