三维最短路径分析算法的实现及其可视化

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (33): 105-107.

三维最短路径分析算法的实现及其可视化

朱耿青,陈崇成,唐丽玉,林定

福州大学福建省空间信息工程研究中心空间数据挖掘与信息共享教育部重点实验室,福州 350002

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-21 发布日期:2007-11-21
通讯作者: 朱耿青

Realization of shortest path on raster terrain data and 3D visualization

ZHU Geng-qing,CHEN Chong-cheng,TANG Li-yu,LIN Ding

Key Lab of Spatial Data Mining and Information Sharing of Ministry of Education（Fuzhou University）,Spatial Information Research Center of Fujian Province,Fuzhou 350002,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-11-21 Published:2007-11-21
Contact: ZHU Geng-qing

摘要/Abstract

摘要： 最短路径算法是路径搜索领域的重要问题,也是最优路径分析算法的基础。论文设计并实现了适用于栅格地形数据的数据存储结构。在分析A*算法思想的前提下,将计算机图形学中的直线求交算法应用到启发函数的计算中,实现了针对规则栅格地形数据计算最短路径的算法并将其进行了三维可视化显示。

关键词: A*算法, Bresenham算法, 栅格, 最短路径

Abstract: The shortest path algorithm is one of the important question in pathfinding,and it is the base of the best path finding algorithm.This paper explains the design of the data structure for storaging the raster terrain data.By analyzing A* algorithm,we apply the Bresenham line-drawing algorithm into calculating the heuristic function and realize the shortest path finding algorithm on raster terrain data.Also,we show the shortest path in three-dimensional terrain.

Key words: A* algorithm, Bresenham line-drawing algorithm, raster, shortest path

朱耿青,陈崇成,唐丽玉,林定. 三维最短路径分析算法的实现及其可视化[J]. 计算机工程与应用, 2007, 43(33): 105-107.

ZHU Geng-qing,CHEN Chong-cheng,TANG Li-yu,LIN Ding. Realization of shortest path on raster terrain data and 3D visualization[J]. Computer Engineering and Applications, 2007, 43(33): 105-107.

[1]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[2]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[3]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[4]	韩晓微，韩震，岳高峰，崔建江. 救灾无人机的优化A*航迹规划算法[J]. 计算机工程与应用, 2021, 57(6): 232-238.
[5]	朱佳莹，高茂庭. 融合粒子群与改进蚁群算法的AUV路径规划算法[J]. 计算机工程与应用, 2021, 57(6): 267-273.
[6]	赵伟，吴子英. 双层优化A*算法与动态窗口法的动态路径规划[J]. 计算机工程与应用, 2021, 57(22): 295-303.
[7]	刘子豪，赵津，刘畅，赖坤城，王玺乔. 基于改进A*算法室内移动机器人路径规划[J]. 计算机工程与应用, 2021, 57(2): 186-190.
[8]	刘建娟，薛礼啟，张会娟，刘忠璞. 融合改进A*与DWA算法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(15): 73-81.
[9]	王晓军，王博，杨春霞，晋民杰，陈海波. 紧致密集Auto Store系统AGV路径规划与避碰策略[J]. 计算机工程与应用, 2021, 57(15): 259-270.
[10]	王保剑，胡大裟，蒋玉明. 改进A*算法在路径规划中的应用[J]. 计算机工程与应用, 2021, 57(12): 243-247.
[11]	华洪，张志安，施振稳，陈冠星. 动态环境下多重A*算法的机器人路径规划方法[J]. 计算机工程与应用, 2021, 57(10): 173-180.
[12]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[13]	袁洋，叶峰，赖乙宗，赵雨亭. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251-256.
[14]	周睿慜，李辉. 改进动态规划算法的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(21): 20-24.
[15]	王磊，孙力帆. 引入必经点约束的路径规划算法研究[J]. 计算机工程与应用, 2020, 56(21): 25-29.