空间网格体系下基于GJK的空域冲突检测算法

蔡 明，万路军，高志周，徐鑫宇

（空军工程大学空管领航学院,陕西 西安 710051）

联合作战涉空力量多元、涉空行动多样，无论是地对地、地对空、空对地，还是舰对空、舰对舰等作战行动，都要涉空用空，战场空域变得越来越拥挤，如何对战场空域冲突进行高效检测，是制约联合作战水平提升的重点、难点问题[1]。军航的各类航空器的高机动、高速度等特性，决定了与民航航空器冲突检测存在显著的差异。例如地空导弹和歼击机的飞行速度和机动性能要比民航飞机强得多，导致航向诸元变化极快，飞行状态及位置极难预测；同时，现代战争的高烈度导致成千上万件武器装备在同一时间单元、有限的战场空域内协同作战，故无法使用现有的民航飞机之间的飞行冲突检测方法对其进行一一检测。因此，可行的做法是诸军兵种向空域管理部门申请所需空域。这些申请的空域通常会发生相互交织，空域冲突检测即检测不同空域之间的间隔是否满足安全间隔规定，通过安全间隔将各类型飞行器所在的活动空域隔离开。对于检测无冲突的空域，空域内的飞行器活动轨迹必须遵守该空域的使用规则，以防止飞行冲突，提升空域使用效率。

空域之间的冲突检测问题，核心目标是确定空域之间是否满足安全间隔标准，可以抽象为两个多面体之间的碰撞检测问题。为此，国内外学者进行了大量的探索，目前比较常用的有基于扫描实体的算法[2]、应用闵可夫斯基和集与球面高斯映射相结合的方法[3]、保守前进算法及其改进算法以及线性连续碰撞检测（Linear continuous collision detection）算法[4]。上述方法只能检测出空域间有无重叠，对于无重叠的空域即认为无冲突。实际上，在无重叠的基础上还应满足空域间的最小安全间隔，才能确定空域无冲突。

Gilbert-Johnson-Keerthi 算法(简称GJK 算法)是一种通过向量映射构成闵可夫斯基差集（Minkowski Difference），可以较快计算得到两物体间的最小距离并检测碰撞的渐进算法[5]，也是目前多面体间相交检测问题和距离计算问题最为有效的几何算法之一[6]。该算法在物理仿真、机器人碰撞检测和虚拟现实等领域有着十分广泛的应用。

针对高效空域冲突检测的现实需求，本文以北京大学程承旗教授等[7]提出的2n一维整型数组全球经纬剖分网格（Geographic Coordinate Subdividing Grid with One Dimension Integral Coding on 2n-Tree，GeoSOT）为基础，将空域表达为多层级、多尺度的网格集合，为了提高空域冲突检测算法的准确性与高效性，建立了在GeoSOT 剖分网格系统下基于GJK 算法的空域冲突检测模型。

1 GeoSOT 剖分网格系统

GeoSOT 剖分网格系统由北京大学程承旗教授[8−9]所带领的团队提出，属于等经纬度的四叉树剖分网格体系。其核心思想是将整数“度”及整数“分”级网格进行逻辑上的外延，使得网格具有整数特征；同时，较完备地实现了大到整个地球、小到厘米级面片的全球四叉树格网结构。格网上下级别之间的父子面片、面积之比大致都为4∶1，并且与我国及世界各国主要的规格地理格网之间都具有一致性聚合特性[10]。

在网格的剖分方式上，为确保下一级面片能在上一级面片的基础上进行四叉划分，生成的网格编码为整数，将地球表面进行了3 次扩展[11]。第1次扩展将180°×360°地球表面空间扩展为512°×512°；同时，为了保证经纬线上严格整型二分，进一步对1°和1′的面片进行扩展，即从1°等于60′扩展到1°等于64′；从1′等于60″扩展到1′等于64″，建立起全球空间GeoSOT 剖分框架网格基础[12]。GeoSOT各层级面片与尺度对应关系见表1。

表1 GeoSOT 各层级与尺度对应关系

GeoSOT 网格编码具有四进制一维、二进制一维、二进制二维以及十进制二维4 种形式[13]。这种编码方式使得得到编码能够与计算机处理模式以及经纬度语义形成一致，各种进制编码之间能够快速转换。

以我国北京市天安门城楼的经纬度坐标（39°54′20″N，116°25′29″E）为例，说明经纬度坐标与网格编码之间的转化方法。由于经度值116°25′29″小于256°和128°，故网格编码的前两位均为0；同时116°25′29″/64°=1 余52°25′29″，则第3 位编码为1；再将网格剖分到大小为32°的第4 层级，52°25′29″/32°=1 余20°25′29″，则第4 位编码也为1，以此类推，最后得到在第16 层级（32″×32″）网格精度下，二进制经度编码为0011101000110010。同理，得到二进制纬度编码为0001001111101100。将纬度编码与经度编码交叉得到天安门城楼所在的第16 层级网格的一维二进制编码为G00000 111010011101010110110100100，转化为一维四进制编码为G001310322-2 312 210，如图1 所示。

图1 天安门城楼位于第16 层级网格下的编码

2 GJK 算法

GJK 算 法（Gilbert-Johnson-Keerthi 算 法）由Gilbert、Johnson、Keerthi 三位学者提出的。该算法通过计算两个物体之间的距离来进行多面体碰撞检测，本质上是在单纯形上逐步寻找距原点最近点的渐降方法[5]。

假设有两多面体A 和B，A 与B 之间的距离d(A,B)可用式（1）来表示：

若取到物体A 和B 上的相邻最近的两点a和b时，一定满足式（2）：

同时引入闵可夫斯基差集的概念。闵可夫斯基差集用多面体A的所有点减去多面体B 中所有的点得到的一个点集合，可用式（3）表示：

闵可夫斯基差集的意义在于，得到两个多边形顶点间的坐标分布关系，如果两个多边形相交，那么差集中点会分布在坐标原点四周，也就是说差集会包含原点。差集有一些特殊的性质，差集构成的多边形的形状与两个多边形之间的距离没有直接关系。两个多边形距离越大，则差集的中心位置离原点越远，反之离原点越近。如果相交，则差集多边形会包含原点。那么多面体A 与多面体B 之间的距离就可以用|minm(A,B)|表示，描述为式（4）：

通过引入闵可夫斯基差集的概念，可将两多面体之间的冲突检测问题转化为判断两多面体之间构成的闵可夫斯基差集是否包含原点的问题。通过转化，大大简化了求解难度，也使计算结果更加直观清晰，如图2 所示。

图2 (b) 闵可夫斯基差集与原点之间的距离

图2 (a) 多面体A 与B 之间的距离

3 空域冲突检测模型的建立

3.1 构建安全包围盒

在进行空域冲突检测时，不仅要计算空域间是否发生重叠，还要考虑空域间隔是否满足安全间隔标准。当两个空域发生重叠或者间隔小于最小安全间隔D 时，则判定两个空域之间存在冲突。

首先根据文献[14]所介绍的空域网格化表达方法，将空域表达为某一层级网格的集合，然后为了在冲突检测模型中充分考虑到最小安全间隔D，考虑构建空域的安全包围盒。构建安全包围盒的方法有两种，第一种方法是将其中一个空域向四周扩大距离D，构建安全包围盒，另一个空域保持不变。第二种方法是将两个空域空间各外扩大D/2，分别构建安全包围盒。本文将空域间最小安全间隔D设定为16 km。当面对大量待检测空域时，第一种方法的局限性就比较明显。因为仅仅对一个空域进行外扩构建安全包围盒，不能保证任意选择的两个空域都已构建安全包围盒，导致检测结果存在大量误差。

3.2 网格体系下空域冲突检测

步骤1：建立网格剖分体系和编码规则，建立经纬度坐标与网格编码之间的转换关系。

步骤2：对空域进行网格化表达。将空域范围分割为第13 级网格（8km×8km）的集合，并通过有序的网格编码建立数据结构，对空域进行记录和组织。

步骤3：建立空域的安全包围盒。由于空域间最小安全间隔为D/2，故将各个空域范围向外膨胀D/2。本文中，将空域向外膨胀一个网格即为安全包围盒。

步骤4：建立坐标系，将包围盒的网格编码转化为坐标。

步骤5：利用GJK 算法，两两逐对计算空域间的闵可夫斯基差集，判断其与原点的包含关系，检验两两空域间是否存在冲突。

步骤5 中，设要检测两个空域1 和2，构建两空域间的闵可夫斯基差集的方法为：在空域1的包围盒上随机抽取一个坐标A，在空域2的包围盒上随机抽取一个坐标B作矢量差，并将得到的结果储存至数组中。多次迭代循环，就构成了所求的闵可夫斯基差集。最后，再将闵可夫斯基差集中的点在坐标系中生成图像点集，并与原点（0,0）的位置进行比较，通过判别生成的闵可夫斯基图像点集是否包含原点，进而判断两空域是否发生冲突。

4 仿真实验及结果

假设某一区域内同时存在3 个空域，3 个空域的参数为如下。

1）空域1的中心点经纬度为（31°12′26″N，119°12′26″E）。空域形状为长方体，长度为64 km，宽度为32 km，高度上限为7 km，高度下限为3 km。

2）空域2的中心点经纬度为（31°32′34″N，119°24′20″E）。空域形状为正方体，长度为48 km，宽度为48 km，高度上限为8 km，高度下限为5 km。

3）空域3的中心点经纬度为（31°48′15″N，120°00′30″E）。空域形状为球体，空域半径为24 km，高度上限为9 km，高度下限为4 km。

将3 个空域进行网格化表达之后如图3 所示。对上述3 个空域，两两进行冲突检测。

图3 目标空域的网格化表达

综合考虑时间成本和检测准确度，将算法的迭代次数设定为10 000，得到的闵可夫斯基差集中有10 000 个元素，再将这些元素点在坐标系中生成，结果如图4 所示。

图4 空域冲突检测结果

图4（a）直观清晰地展现出了闵可夫斯基差集点群与坐标原点（0,0）的关系，可以确定坐标原点在生成的闵可夫斯基差集点群内部，即空域1 和空域2 存在冲突威胁。通过图4（b）和图4（c），可以确定坐标原点在生成的闵可夫斯基差集点群之外，即空域1 和空域3 之间，以及空域2 和空域3 之间均不存在冲突。

目前，传统的空域冲突检测都是在经纬度坐标体系下，采用几何解析或智能算法进行求解，将空域看成各类几何体，通过几何体之间有无相交，判定空域之间是否产生冲突。根据预期划设空域的数据参数（中心点位置、长度、宽度和高度等），将空域边界点转换为经纬度值并在计算机里表示为编码的集合。通过查询编码集合之间有无交集，确定空域之间是否发生重叠，并判定空域之间的距离是否满足安全间隔规定，最终进行冲突判定。

传统的空域冲突检测方法虽然便于理解操作简单，但是具有局限性较多、易导致误差的缺点。导致误差的原因主要在于经纬度坐标体系下单位度量差值距离固定，不够灵活。在传统经纬度坐标体系下，单位纬度长度分别为1″≈30.8 m，1′≈1.85 km，1°≈111 km。单位经度长度的计算方法为该地区单位纬度的距离×该地区纬度的余弦值。

在日常空域划设中，空域大小长度一般在30～100 km 之间。通过经纬度度量值可以粗略将空域1、空域2 和空域3的边界点的经纬度值的集合表示出来（为方便表示取4 个顶点为特征点）。

利用传统空域冲突检测方法通过将各个空域的边界点的经纬度值集合表示出来后，并不能直接对空域是否发生冲突进行判断。若想通过计算机对集合之间进行运算，则需要将空域边界点的经纬度值的集合尽可能多地列举出来，工作量较大，并且受经纬度单位差值距离固定的影响，仍然可能存在两片空域存在冲突，但是集合中未能列举出两片空域的冲突点的情况。

同时，由于经纬度单位差值固定不灵活，且经纬度值计算时同时涉及度、分、秒三级数值对的计算与变化，所以计算较为复杂，工作量较大。

与传统空域冲突检测方法相比，利用GJK 算法将两空域包围盒之间的相交检测转化为对闵可夫斯基差集与坐标原点的包含关系的判断，简化了冲突检测模型，降低了工作量，同时使实验结果表示得更加清晰直观。

5 结论

高效准确地对多个单位在同一区域同一时间段内的空域申请进行高效的冲突检测，对于保障飞行活动的正常有序开展，保证飞行安全至关重要。为此，本文提出了一种在GeoSOT 网格体系下结合GJK 算法的空域冲突检测算法。该算法以GeoSOT 网格为工具，利用空域网格表征和时空二值计算上的优势，将空域之间的相交检测转化为闵可夫斯基差集与坐标原点的包含关系，对问题进行了抽象和简化，实验结果以较为清晰明确的图形关系显现出来，易于论证与检验。本文只研究了网格体系下的空域冲突检测，对于如何将存在的空域冲突进行一体化消解，将是下一步研究的重点。