基于Graham算法的飞行程序保护区边界画法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Graham算法的飞行程序保护区边界画法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘 要]飞行程序保护区的辅助设计中，风螺旋线作为转弯机动的限制边界，其不规则性使得计算机难以精确绘制。文中对飞行程序保护区做出数学描述的同时引入Graham算法使得精确绘制不规则边界成为可能，并且对比以斜率作为参考的粗糙的算法做时间复杂度的对比分析，最终设计程序证实了算法的可行性和高效性，为飞行程序保护区自动绘制增添新的模型

[关键词]辅助设计；风螺旋线；Graham；时间复杂度

中图分类号：V323；TP311.11 文献标识码：A 文章编号：1009-914X（2017）22-0360-03

1 引言

飞行程序设计工作中，计算机辅助设计随着计算机科学和编程算法的发展已经广泛应用，主要集中在对保护区中障碍物判断以及保护区划设等方面。目前区域结构较为简单的进近程序和简化的离场程序都已经有了较为完整的辅助设计系统[1]，开发方法虽然不同，但难度集中在保护区结构的准确数学描述，因此造成了编程时没有可以保证准确性的算法结构。飞行程序设计保护区的构型中以风螺旋线的位置特别且要求最严格，过去解决手段主要是直接调用编程语言相关函数[2]或者通过单点迭代利用直线拟合曲线进而以点对点关系构造相关区域[3]，这些方法可以在一定程度上解决飞行程序设计工作中风螺旋线与其他图元之间的结构问题，不足在于由于需要调用特殊的函数无法在不同的开发环境中广泛使用，当某一个编程方法在飞行程序设计软件的开发功能上显得不足需要其他接口加入时，此类实现保护区划设的方法则不具备通用性。因此，建立合适的数学模型，从算法结构的角度解决飞行程序设计保护区中风螺旋线与多种图元相对关系是有必要实现的。

2 相关飞行程序

风螺旋线表示航空器转弯时每转过一定角度受到内风的影响形成的转弯偏移，图1所示为航空器绕中心圆点飞行90°生成的风螺旋线（wind spiral），在过去的手工绘图中通常以若干正圆为轮廓线，通过各轮廓间的拟合得到保守的近似覆盖最大范围的风螺旋线。近年来借鉴了机械，建筑领域中计算机制图“阿基米德螺旋线”的概念[4]，遵循公式（1-1）可以将风螺旋线这样的极坐标曲线用极小步长生成。

根据民航飞行程序设计工作的标准规范DOC8168，基线转弯和直角程序中的保护区是在标称航迹的基础上，由相对的位置关系在一定的区域绘制转弯风螺旋线，再由风螺旋线构成的保护区边界区域生成包络线确保飞行保护区的安全性最高。图2为基线转弯保护区，图3（a）（b）为直角程序的模板及保护区生成过程。

这两种程序都是航空器做转弯机动时使用的飞行程序，因此存在大量转弯时需要确定的风螺旋线的边界，手工绘图中为了保证人工操作的误差不影响安全，采用圆近似替代风螺旋线的简易画法，虽然保守的保证了航空器的飞行安全但是无形中扩大了保护区范围造成一定的空域浪费。

3 算法设计

为了在空间中构造准确的飞行程序保护区边界，必须建立非描述性的边界曲线模型，利用地理坐标的定位实现对已知的程序航迹计算数学模型可以很好的解决航迹的建模[5]，但对随着参数变化位置不确定的保护区边界，需要借鉴计算几何学的方法寻找各结构间的关系。要引入计算几何算法首先要引入点集的概念[6]。

3.1 二维空间的几何关系

在二维空间中，任意多边形P有N个顶点，这些顶点构成集合，称为顶点序列。这些点按照出现顺序排列为1，2…n，每一个顶点序列中的点均可用表示该点对应坐标。根据基线转弯程序与直角程序设计的特点，实现包络线是程序的关键。在几何学中，曲线族的包络线，是跟该曲线族的每条线都有至少一点相切的一条曲线。假设每条曲线为，设表示曲线与包络线相切的点，包络线为，要求出包络线转化为求出。

大的保o余度而又不需要为了切点的准确改用简易画法绘制。

算法设计过程及简图如下：

①对所有点计算坐标，选取值最小点，若存在多个相等的点，选取最小的点，以此选出最下方（或左下）点作为基准点

②以水平轴方向为基准，逆时针方向，按照两点连接的线段与基准轴夹角的增大逐个扫描点，对于同样夹角下，只加入离基准点最远点的坐标，以此顺序形成点集

③先连接基准点与所有点中夹角最小距离最近点得到初始线段，以与点集中按顺序的下一点连接得另一线段

④按照平面坐标的计算方法，运算向量与向量的叉积，根据3.2节的向量关系，判断与的方向关系（图5（a））

⑤此处建立的坐标系是以最左下的点为基准，逆时针方向排列的点集，当其中一个向量与下一向量之间的关系为顺时针时，说明该处出现凹边，移除并从点集中去除点，进一步缩小点集规模（图5（b））

⑥只需要将中已保存的点按顺序执行回到基准点，剩余在点集中的点即为满足凸包的点集

Graham算法下首先对所有平面内的点通过极角与距离的关系做一次淘汰，剩余的点理论上是一个包围的点集，若是以1°为步长，大约360个点，大大减少了需要搜索的点集规模。整个算法运行中只有①步骤遍历所有点，且只以基准点一次遍历时间复杂度为，步骤⑤时间复杂度为相比几何关系下确定的要小的多，并且随着风螺旋线数量的增多优势越发显著。

4 开发实例

前文中算法设计主要结合了平面向量与图元分布，AutoCAD是当前较为主流的平面设计软件，其内嵌的ALisp/VLisp语言采用面向过程的设计模式，表处理的语言结构编写快捷[7]，因此采用A/VLisp语言编译插件实现保护区绘制的主体功能作为算法验证。

直角程序保护区的初始化参数输入界面设计如图6所示。

最终实现的基线转弯与直角程序保护区自动辅助设计程序可以根据基本飞行参数自行计算边界点所在位置，使用Graham算法一次性生成多边形边界多线段，直角程序保护区取2000个点运行时间只要0.4秒而基线转弯程序保护区则是瞬间完成，图7图8是在程序中加入断点分步执行保护区生成程序的效果。

5 结论

本次程序开发中，对描述性的飞行程序保护区边界用数学语言重新描述，并且根据平面空间的几何特点，引入Graham算法在缩小空间有效点集规模的同时迅速找到边界特征。在AutoCAD平台下以ALisp/VLisp语言开发软件核心部分同时以OpenDCL设计友好简洁界面，成功实现了保护区的自动绘制，证明了算法思路符合通用特性，为飞行程序保护区自动化实现提供了精确模型。

参考文献

[1] 沈笑云，赵瑞，焦卫东，等.基于 World Wind 的RNP飞行程序三维可视化仿真[J].系统仿真学报，2012， 24（010）：2131-2135.

[2] 吴洁明，符晓君.计算机辅助实现航空器基线转弯程序设计的方法[J]. 航空计算技术，2006，36（4）： 17-20.

[3] 卢敏.基于GIS的飞行程序设计[J].2006.

[4] 张湘，郭坤州，夏宏玉，等.基于SolidWorks的渐开线齿轮建模方法研究[J].现代机械，2008 （4）：37-39.

[5] 李夏.仪表飞行程序三维呈现系统设计的初步研究[D][D].中国民用航空飞行学院，2011.

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

[7] 王军锋，刘文清，王大勇等.等高线等间距高程自动标注的方法实现[J]. 测绘科学，2014（5）：150-152.