一种基于优化A-star算法的室内外一体化寻径方法研究  

An integrated indoor and outdoor routing method for optimizing A-star algorithm

作　　者：姚俊臣 张福浩[1] 王亮[1] 何望君[1] YAO Junchen;ZHANG Fuhao;WANG Liang;HE Wangjun(Chinese Academy of Surveying&Mapping,Beijing 100036,China)

机构地区：[1]中国测绘科学研究院,北京100036

出　　处：《测绘科学》2024年第8期121-130,共10页Science of Surveying and Mapping

基　　金：国家重点研发计划项目(2022YFC3003604);中国测绘科学研究院基本科研业务费项目(AR2204)。

摘　　要：针对A-star(A*)算法在室内外一体化三维路径分析上存在搜索精度差、空间查询效率低的问题,该文提出一种改进A*算法的室内外一体化路径搜索方法。首先从包含室内外场景的三维模型中提取用于路径搜索的导航网格,并采用耳裁剪(ear clipping)算法进行优化,实现导航网格自适应性剖分,大幅提高导航网格空间精度。然后,引入布尔(boolean)数组和弱堆(weak heap)等数据结构,融合地形复杂度控制变量,对A*算法进行计算效率和精度方面改进,并通过漏斗算法进行路径平滑处理,使之更好地适应室内外一体化三维路径搜索场景。最后,基于某校园室内外一体化三维场景,完成算法效率和精度对比和验证。Aiming at problems with poor search accuracy and low spatial query efficiency of A-star(A*)algorithm in integrated 3D path analysis of indoor and outdoor environments,an improved A*algorithm for indoor and outdoor integrated path search was proposed in this paper.Firstly,the navigation mesh for path search was extracted from the 3D model containing indoor and outdoor scenes,and the ear clipping algorithm was used to achieve adaptive meshing of the navigation mesh,greatly improving the spatial accuracy of the navigation mesh.Then,by introducing data structures such as Boolean arrays and weak heaps,and integrating terrain complexity control variables,the A*algorithm was improved in terms of computational efficiency and accuracy.The funnel algorithm was used for path smoothing to better adapt to indoor and outdoor integrated 3D path search scenes.Finally,based on the integration of indoor and outdoor 3D scenes in a certain campus,a comparison and verification of algorithm efficiency and accuracy were completed.

关 键 词：导航网格 改进A*算法 最短路径搜索 室内外一体化 

分 类 号：P208[天文地球—地图制图学与地理信息工程]