一种基于网格划分和哈希表索引的空域冲突检测方法及装置
本发明涉及空中交通管理,具体为一种基于网格划分和哈希表索引的空域冲突检测方法及装置。
背景技术:
1、空域是根据飞行训练和飞行需求划定的三维空间范围,空域冲突是指在空中交通管理中,不同的航空器或者同一航空器内部的不同部分之间,由于飞行活动安排不当,导致潜在的或实际的安全风险事件。
2、我国的空域资源使用有限,对空域的需求量逐年增大,当使用的空域资源多、空域数量庞大、空域更新频繁时,现有的空域冲突检测时间长,无法及时的对空域冲突进行有效检测,导致用空冲突,极易引发飞行事故。
3、传统的空域冲突检测方法主要依赖于空域集合图形计算。通过计算两个空域之间的之间的欧氏距离,判断该距离是否小于设定的最小安全间隔。但该算法时间复杂度为,随着空域数量的增加,计算开销呈平方级增长,难以满足大规模、实时性的检测需求。
4、为提高冲突检测的效率,现有技术提出了一些改进方案。例如,基于hadamard矩阵的网格化运算、时空编码或网格"与"运算、gjk几何算法等。但要么仍是矩阵运算,复杂度依然较高,要么其效率和灵活性存在局限,当空域数量增多后,依然难以满足空域冲突检测要求。
5、因此,迫切需要一种计算复杂度低、能够对大规模空域进行精确的冲突检测,并能直接定位冲突位置的新方法。
技术实现思路
1、本发明的目的在于提供一种基于网格划分和哈希表索引的空域冲突检测方法及装置,以解决上述背景技术中提出的问题。
2、本发明的主要设计思路:
3、本发明主要通过将连续空域离散化为体素网格并建立“网格与空域”的反向索引哈希表,将空域间的空间重叠检测转化为哈希表中列表长度的判断,从而将算法复杂度从降低至近似,以实现毫秒级的大规模空域冲突快速检测与精确定位。
4、为实现上述目的,本发明提供如下技术方案:
5、第一方面,本发明提供一种基于网格划分和哈希表索引的空域冲突检测方法,包括:
6、依据总空域的空域范围和预设的体素尺寸,将总空域剖分为多个体素,并为每个体素建立对应的体素索引;
7、为每一个待检空域分配对应的待检空域编码,计算该待检空域所覆盖的体素,获得该待检空域的体素索引集合;
8、初始化一个哈希表,其键为体素索引,其值为空域列表;
9、遍历所有待检空域及其体素索引集合,对于该体素索引集合中的每一个体素索引,将当前遍历的待检空域的待检空域编码添加至所述哈希表中以该体素索引为键所对应的空域列表中;
10、遍历所述哈希表,对于其中的每一个条目,若其值对应的空域列表的元素数量大于1,则判定该空域列表中所有元素对应的待检空域在该条目键所对应的体素索引处发生冲突;
11、输出所有发生冲突的体素索引及其对应的待检空域编码列表。
12、进一步优选地,所述依据总空域的空域范围和预设的体素尺寸,将总空域剖分为多个体素,包括:
13、设总空域在、、方向上的空域范围分别为,,;
14、预设体素尺寸在、、方向上的分量分别为、、;
15、依据所述体素尺寸对所述空域范围所限定的总空域按立方体进行剖分,获得在、、方向上的体素数量、、分别为:
16、
17、
18、
19、剖分后的体素编码记为,,,。
20、进一步优选地,为每个体素建立对应的体素索引,包括:
21、
22、其中,表示体素索引,、、分别表示体素编码在、、方向上的分量。
23、进一步优选地,输出所有发生冲突的体素索引及其对应的待检空域编码列表,还包括输出体素索引所对应的体素编码。
24、进一步优选地,所述通过体素索引获取体素编码,包括:
25、
26、
27、
28、
29、其中,表示中间变量,表示向下取整,表示取模运算。
30、进一步优选地,计算该待检空域所覆盖的体素,包括:
31、通过计算该待检空域的空域范围与每个体素的包含或相交关系实现。
32、第二方面,本发明提供一种基于网格划分和哈希表索引的空域冲突检测装置,用于实现所述的方法,包括:
33、网格划分编码模块,被配置为依据总空域的空域范围和预设的体素尺寸,将总空域剖分为多个体素,并为每个体素建立对应的体素索引;
34、待检空域处理模块,被配置为每一个待检空域分配对应的待检空域编码,计算该待检空域所覆盖的体素,获得该待检空域的体素索引集合;
35、哈希表构建模块,被配置为初始化一个哈希表,其键为体素索引,其值为空域列表,遍历所有待检空域及其体素索引集合,对于该体素索引集合中的每一个体素索引,将当前遍历的待检空域的待检空域编码添加至所述哈希表中以该体素索引为键所对应的空域列表中;
36、空域冲突检测模块,被配置为遍历所述哈希表,对于其中的每一个条目,若其值对应的空域列表的元素数量大于1,则判定该空域列表中所有元素对应的待检空域在该条目键所对应的体素索引处发生冲突;
37、冲突结果输出模块,输出所有发生冲突的体素索引及其对应的待检空域编码列表。
38、与现有技术相比,本发明的有益效果是:
39、1.本发明将传统的几何空间重叠判断(复杂度)转化为一次哈希表构建和遍历(复杂度),极大提升了大规模空域下的冲突检测速度,实验表明可达毫秒级响应,满足空域检测的实时性要求。
40、2.本发明不仅能够判断空域间是否存在冲突,还能直接、精确地输出冲突发生的具体位置(体素索引,可转换为体素编码)以及在该位置所有发生冲突的待检空域编码,为后续的冲突解脱提供了直观、具体的输入。
41、3.本发明通过构建体素-空域列表这一反向索引哈希表结构,仅需对所有待检空域进行一轮前向遍历,即可完成所有空域对之间的冲突检测,完全避免了传统方法中计算开销巨大的空域间两两比对循环。
42、4.本发明主要依赖总空域网格剖分、体素编码及哈希表插入与查询等基础计算操作,在各类编程语言和开发环境中均有支持库,技术实现门槛低,易于编程实现、调试和性能优化。
1.一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,包括:
2.根据权利要求1所述的一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,所述依据总空域的空域范围和预设的体素尺寸,将总空域剖分为多个体素,包括:
3.根据权利要求2所述的一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,为每个体素建立对应的体素索引,包括:
4.根据权利要求3所述的一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,输出所有发生冲突的体素索引及其对应的待检空域编码列表,还包括输出体素索引所对应的体素编码。
5.根据权利要求4所述的一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,所述通过体素索引获取体素编码,包括:
6.根据权利要求1所述的一种基于网格划分和哈希表索引的空域冲突检测方法,其特征在于,计算该待检空域所覆盖的体素,包括:
7.一种基于网格划分和哈希表索引的空域冲突检测装置,用于实现权利要求1-6任一项所述的方法,其特征在于,包括:
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com