一种截窗查询的多障碍物快速碰撞检测算法  

Method Based on Windowing Query for Rapid Multi-obstacles Collision Free Test

作　　者：张蔚[1] 李文伟 任振华[3] 李增路 

机构地区：[1]装甲兵工程学院控制系火控室,北京100072 [2]兵器科学院,北京100083 [3]重庆通信学院,重庆400035

出　　处：《系统仿真学报》2010年第11期2489-2491,共3页Journal of System Simulation

基　　金：十一五装备重点预言(513040102)

摘　　要：依赖于地理信息系统的越野路径规划,由于存在大量分布不规律的环境障碍物,严重影响路径规划的计算速度,借鉴截窗查询的思想,给出了基于一维数据结构的矩形截窗查询算法,该算法有效减少了规划过程所需碰撞检测的障碍物个数,大幅提高规划速度,在环境障碍物动态更新的情况下,其性能优于区间树的截窗查询方法。Path planning based on GIS is a fundamental problem in many applications. It is the main problem affecting the planning time because of the multi-obstacles in field environment. A novel rectangle windowing query method was proposed in order to improve the compute efficiency of collision free test. The method reduces the numbers of obstacles needed to test and speeds the planning process, and is more suitable with the dynamic environment of obstacles changing than the interval tree method.

关 键 词：路径规划 碰撞检测 截窗查询 计算几何 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]