PythonRobotics 可视性路图Visibility Road Map规划器源码解析与实战指南【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics本文基于 PythonRobotics 仓库中docs/modules/5_path_planning/visibility_road_map_planner/的可视性路图规划器文档结合 visibility_road_map.py 源码、geometry.py 线段相交判定与 dijkstra_search.py 图搜索实现系统讲解该规划器从“障碍物多边形”到“无碰撞最短路径”的完整算法链路、关键参数与可运行示例帮助你掌握如何用“先构图、再搜索”的经典两阶段思路实现机器人全局路径规划。一、概述什么是可视性路图规划可视性路图Visibility Road Map是机器人路径规划中的一种经典全局规划方法。它的核心思想非常直观在多边形障碍物环境中把“可互相看见”且“连线不穿过障碍物”的点连接起来构成一张无碰撞的图Road Map然后在这张图上搜索最短路径。在 PythonRobotics 中该规划器的定位是基于多边形的几何路径规划输入为起点、终点和一组多边形障碍物输出为一条从起点到终点的无碰撞折线路径。从源码结构看它与同仓库的 VoronoiRoadMap 共享同一套 DijkstraSearch 图搜索库二者的区别仅在于“如何生成路图节点与边”Voronoi 路图基于采样与维诺图而可视性路图基于障碍物多边形的顶点扩展。原文档中用动画直观描述了算法结果黑色线条是障碍物多边形红色叉号是可视性节点visibility nodes蓝色线条是无碰撞的可视性图collision free visibility graphs红色线条是最终由 Dijkstra 算法在可视性图上搜索出的路径。如上图所示规划器假设可以获得三类输入信息起点Start point图中红点终点Goal point图中蓝点障碍物多边形Obstacle polygons图中黑色线条注原文档在讲解算法时引用的动画图位于仓库外部本文改用仓库内docs/modules/5_path_planning/visibility_road_map_planner/目录下同主题的step0.png~step3.png四张过程图来对应算法各阶段。二、算法核心流程三步构建无碰撞路径原文档将整个算法拆解为三个步骤这也是理解可视性路图规划的标准框架。下面逐一展开并同步给出源码层面的印证。Step 1基于多边形障碍物生成可视性节点第一步是把多边形障碍物的顶点向外扩展生成可视性节点原文档明确指出Each polygon vertex is expanded outward from the vector of adjacent vertices. The start and goal point are included as nodes as well.即每个多边形顶点都沿着其相邻顶点所构成向量的方向向外扩展一段距离同时起点和终点也被作为节点纳入图中。在源码 visibility_road_map.py 中这一过程由generate_visibility_nodes()与calc_vertexes_in_configuration_space()实现generate_visibility_nodes()首先把起点和终点构造成DijkstraSearch.Node加入节点列表然后对每个障碍物调用calc_vertexes_in_configuration_space()将扩展后的顶点逐一追加为节点calc_vertexes_in_configuration_space()遍历多边形的每一条边对每个顶点调用calc_offset_xy()计算扩展偏移坐标。顶点扩展的几何计算位于 calc_offset_xy()取该顶点前后两条相邻边向量分别用math.atan2得到方位角p_vec与n_vec求出二者方向的角平分线方向再旋转π/2作为外扩方向最后叠加expand_distance扩展距离得到新顶点坐标。这正是“沿相邻顶点向量向外扩展”的数学实现其作用等价于把障碍物顶点在配置空间configuration space中“膨胀”出来为具有一定尺寸的机器人留出安全余量。Step 2生成无碰撞的可视性图第二步是把上一步生成的所有节点两两连接并进行碰撞检测只保留无碰撞的边原文档的表述为When connecting the nodes, the arc between two nodes is checked to collided or not to each obstacles. If the arc is collided, the graph is removed.在源码中这一步由 generate_road_map_info() 完成对每个目标节点遍历其余所有节点若两点间距离小于等于 0.1视为同一节点则跳过否则对该候选边逐一调用is_edge_valid()与每个障碍物做碰撞检查只有通过全部检查的边才会记录到该节点的邻接列表中。is_edge_valid()是碰撞检测的核心visibility_road_map.py它把候选边抽象为线段p1-p2把障碍物的每条边抽象为线段p3-p4调用 geometry.py 中的Geometry.is_seg_intersect()判断两线段是否相交。若与障碍物任一条边相交则该候选边不合法从图中剔除。is_seg_intersect()采用了计算几何中标准的跨立试验orientation test on_segment 特例处理通过叉积符号判断两条线段端点的相对方位orientation 为 1、2、0 分别表示顺时针、逆时针、共线若四条方位判定满足跨立条件则相交对于共线情况再通过on_segment()判断端点是否落在对方线段上。这一实现对“边恰好擦过障碍物顶点”等退化情形也能给出正确判定。Step 3在可视性图上用 Dijkstra 算法搜索最短路径第三步是在生成的无碰撞图蓝色线条上运行 Dijkstra 算法得到从起点到终点的最短路径红色线条原文档特别说明该可视性路图规划器使用 Dijkstra 方法进行图搜索This visibility road-map planner uses Dijkstra method for graph search并给出了 Dijkstra 算法的细节索引对应仓库内 grid_base_search 文档 中的_dijkstra锚点。在源码中planning()的末尾visibility_road_map.py将节点坐标列表与邻接表road_map_info交给 DijkstraSearch.search()使用open_set待扩展与close_set已扩展两个字典维护搜索过程每次从open_set中取出累计代价最小的节点进行扩展边的代价为两端点的欧氏距离math.hypot(dx, dy)节点代价沿路径累加因此最终得到的是一条几何意义上的最短折线路径搜索结束后由generate_final_path()沿parent指针回溯并反转得到从起点到终点的完整路径点序列rx, ry。三、源码结构从输入到输出的完整调用链为方便对照阅读下表整理了该模块涉及的核心文件与职责文件职责PathPlanning/VisibilityRoadMap/visibility_road_map.pyVisibilityRoadMap规划器主类与ObstaclePolygon障碍物多边形类PathPlanning/VisibilityRoadMap/geometry.pyGeometry.Point点结构与is_seg_intersect()线段相交判定PathPlanning/VoronoiRoadMap/dijkstra_search.py通用的DijkstraSearch图搜索库含Node数据结构PathPlanning/VisibilityRoadMap/init.py模块包标记文件tests/test_voronoi_road_map_planner.py针对该规划器的自动化冒烟测试3.1 VisibilityRoadMap 主类class VisibilityRoadMap: def __init__(self, expand_distance, do_plotFalse): self.expand_distance expand_distance self.do_plot do_plot def planning(self, start_x, start_y, goal_x, goal_y, obstacles): nodes self.generate_visibility_nodes(start_x, start_y, goal_x, goal_y, obstacles) road_map_info self.generate_road_map_info(nodes, obstacles) if self.do_plot: self.plot_road_map(nodes, road_map_info) plt.pause(1.0) rx, ry DijkstraSearch(show_animation).search( start_x, start_y, goal_x, goal_y, [node.x for node in nodes], [node.y for node in nodes], road_map_info) return rx, ry节选自 visibility_road_map.pyexpand_distance顶点外扩距离单位 m是决定路径与障碍物安全间距的核心参数取值越大路径离障碍物越远但可行通道可能变窄甚至无法找到路径do_plot是否绘制可视性路图蓝色边与节点分布planning()返回rx, ry两个列表即最终路径的 x、y 坐标序列。3.2 ObstaclePolygon 障碍物多边形类ObstaclePolygon 负责把用户传入的顶点列表规范化为“首尾闭合”且“按顺时针排序”的多边形close_polygon()若首尾顶点不重合则自动追加第一个顶点实现闭合make_clockwise()/is_clockwise()通过鞋带公式shoelace formula求多边形有向面积判断顶点绕向若不是顺时针则反转顶点顺序。这一规范化保证了后续顶点扩展与边碰撞检测的方向一致性plot()以黑色线条绘制障碍物多边形。3.3 DijkstraSearch 复用可视性路图规划器并没有自己实现图搜索而是直接复用了 VoronoiRoadMap/dijkstra_search.py 中的DijkstraSearch类。这一点从 visibility_road_map.py 的导入语句from VoronoiRoadMap.dijkstra_search import DijkstraSearch可以确认也再次说明该仓库在算法模块间强调组件复用路图生成策略可视性/维诺与图搜索算法Dijkstra是解耦的。四、运行示例与关键参数4.1 直接运行在仓库根目录下直接运行示例需已安装 requirements.txt 中的 numpy 与 matplotlib 依赖python PathPlanning/VisibilityRoadMap/visibility_road_map.py运行后会依次弹出三幅动画窗口先绘制起点红点、终点蓝点与障碍物多边形黑线随后显示生成的可视性图蓝线最后叠加 Dijkstra 搜索出的最终路径红线。4.2 示例中的默认场景与参数示例main()visibility_road_map.py默认配置如下参数默认值说明sx, sy10.0, 10.0起点坐标 [m]gx, gy50.0, 50.0终点坐标 [m]expand_distance5.0多边形顶点外扩距离 [m]障碍物 1三角形(20,30,15), (20,20,30)多边形顶点 x/y 列表障碍物 2四边形(40,45,50,40), (50,40,20,40)多边形顶点 x/y 列表障碍物 3四边形(20,30,30,20), (40,45,60,50)多边形顶点 x/y 列表自定义场景时只需修改起点、终点坐标调整expand_distance并按同样的“顶点列表”方式构造ObstaclePolygon对象加入obstacles列表即可。4.3 在代码中调用from PathPlanning.VisibilityRoadMap.visibility_road_map import ( VisibilityRoadMap, ObstaclePolygon) planner VisibilityRoadMap(expand_distance5.0, do_plotFalse) rx, ry planner.planning( 10.0, 10.0, # start x, y 50.0, 50.0, # goal x, y [ ObstaclePolygon([20.0, 30.0, 15.0], [20.0, 20.0, 30.0]), ObstaclePolygon([40.0, 45.0, 50.0, 40.0], [50.0, 40.0, 20.0, 40.0]), ObstaclePolygon([20.0, 30.0, 30.0, 20.0], [40.0, 45.0, 60.0, 50.0]), ], )4.4 测试验证仓库通过 tests/test_voronoi_road_map_planner.py 对该规划器做冒烟测试测试中先把模块级开关m.show_animation置为False关闭绘图再调用m.main()完整跑一遍默认场景。可手动执行python tests/test_voronoi_road_map_planner.py测试能顺利结束即说明节点生成、可视性图构建与 Dijkstra 搜索三个环节在默认场景下可正常闭环。从代码看main()中并未显式断言路径非空因此实际使用时建议参考 VoronoiRoadMap 示例 的做法对返回的rx增加assert rx之类的非空校验以应对“外扩距离过大导致无可通行路径”的失败场景。五、方法特性与适用边界综合原文档与源码可视性路图规划器具备以下特点理解这些有助于在工程中正确选型完整性与最优性只要路图构建完备顶点外扩合理、碰撞检测正确在可视性图上用 Dijkstra 搜索得到的是一条长度意义上的最短无碰撞路径这一点优于基于采样的 RRT 类方法后者只能保证概率完备几何精确、无采样随机性节点完全由障碍物多边形顶点决定同一场景下多次运行结果确定易于复现与调试适用前提是“多边形障碍物”输入必须能表示为凸/凹多边形顶点列表。从源码看is_edge_valid()对凹多边形同样按逐边检测处理但顶点外扩方向仅由相邻两条边决定凹多边形的凹顶点处外扩效果需要结合场景验证计算开销集中于全连接建图generate_road_map_info()对每对节点都做一次逐边碰撞检测复杂度随节点数≈多边形顶点数与边数增长顶点数量多或障碍物边数多时建图成本显著上升适合顶点规模适中的结构化场景存在解的前提expand_distance过大可能导致相邻障碍物间的可行通道被“封死”此时图不连通Dijkstra 搜索会打印 Cannot find path 并返回空路径需要适当调小外扩距离。六、扩展阅读原文档中关于 Dijkstra 算法细节的索引对应仓库内 PathPlanning/Dijkstra/dijkstra.py 及 grid_base_search 文档 的_dijkstra一节使用同一套DijkstraSearch库但采用采样建图策略的 VoronoiRoadMap 规划器可与本文的可视性建图形成对照学习本文档所在章节的更多路径规划方法RRT、A*、Dijkstra、样条曲线等可浏览 path_planning_main.rst 目录总览关于可视性图方法本身的理论背景可参考计算几何与机器人学教材中 “Visibility graph” 相关章节原文档引用了维基百科同名条目此处不再赘述外部链接。【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
PythonRobotics 可视性路图（Visibility Road Map）规划器源码解析与实战指南
PythonRobotics 可视性路图Visibility Road Map规划器源码解析与实战指南【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics本文基于 PythonRobotics 仓库中docs/modules/5_path_planning/visibility_road_map_planner/的可视性路图规划器文档结合 visibility_road_map.py 源码、geometry.py 线段相交判定与 dijkstra_search.py 图搜索实现系统讲解该规划器从“障碍物多边形”到“无碰撞最短路径”的完整算法链路、关键参数与可运行示例帮助你掌握如何用“先构图、再搜索”的经典两阶段思路实现机器人全局路径规划。一、概述什么是可视性路图规划可视性路图Visibility Road Map是机器人路径规划中的一种经典全局规划方法。它的核心思想非常直观在多边形障碍物环境中把“可互相看见”且“连线不穿过障碍物”的点连接起来构成一张无碰撞的图Road Map然后在这张图上搜索最短路径。在 PythonRobotics 中该规划器的定位是基于多边形的几何路径规划输入为起点、终点和一组多边形障碍物输出为一条从起点到终点的无碰撞折线路径。从源码结构看它与同仓库的 VoronoiRoadMap 共享同一套 DijkstraSearch 图搜索库二者的区别仅在于“如何生成路图节点与边”Voronoi 路图基于采样与维诺图而可视性路图基于障碍物多边形的顶点扩展。原文档中用动画直观描述了算法结果黑色线条是障碍物多边形红色叉号是可视性节点visibility nodes蓝色线条是无碰撞的可视性图collision free visibility graphs红色线条是最终由 Dijkstra 算法在可视性图上搜索出的路径。如上图所示规划器假设可以获得三类输入信息起点Start point图中红点终点Goal point图中蓝点障碍物多边形Obstacle polygons图中黑色线条注原文档在讲解算法时引用的动画图位于仓库外部本文改用仓库内docs/modules/5_path_planning/visibility_road_map_planner/目录下同主题的step0.png~step3.png四张过程图来对应算法各阶段。二、算法核心流程三步构建无碰撞路径原文档将整个算法拆解为三个步骤这也是理解可视性路图规划的标准框架。下面逐一展开并同步给出源码层面的印证。Step 1基于多边形障碍物生成可视性节点第一步是把多边形障碍物的顶点向外扩展生成可视性节点原文档明确指出Each polygon vertex is expanded outward from the vector of adjacent vertices. The start and goal point are included as nodes as well.即每个多边形顶点都沿着其相邻顶点所构成向量的方向向外扩展一段距离同时起点和终点也被作为节点纳入图中。在源码 visibility_road_map.py 中这一过程由generate_visibility_nodes()与calc_vertexes_in_configuration_space()实现generate_visibility_nodes()首先把起点和终点构造成DijkstraSearch.Node加入节点列表然后对每个障碍物调用calc_vertexes_in_configuration_space()将扩展后的顶点逐一追加为节点calc_vertexes_in_configuration_space()遍历多边形的每一条边对每个顶点调用calc_offset_xy()计算扩展偏移坐标。顶点扩展的几何计算位于 calc_offset_xy()取该顶点前后两条相邻边向量分别用math.atan2得到方位角p_vec与n_vec求出二者方向的角平分线方向再旋转π/2作为外扩方向最后叠加expand_distance扩展距离得到新顶点坐标。这正是“沿相邻顶点向量向外扩展”的数学实现其作用等价于把障碍物顶点在配置空间configuration space中“膨胀”出来为具有一定尺寸的机器人留出安全余量。Step 2生成无碰撞的可视性图第二步是把上一步生成的所有节点两两连接并进行碰撞检测只保留无碰撞的边原文档的表述为When connecting the nodes, the arc between two nodes is checked to collided or not to each obstacles. If the arc is collided, the graph is removed.在源码中这一步由 generate_road_map_info() 完成对每个目标节点遍历其余所有节点若两点间距离小于等于 0.1视为同一节点则跳过否则对该候选边逐一调用is_edge_valid()与每个障碍物做碰撞检查只有通过全部检查的边才会记录到该节点的邻接列表中。is_edge_valid()是碰撞检测的核心visibility_road_map.py它把候选边抽象为线段p1-p2把障碍物的每条边抽象为线段p3-p4调用 geometry.py 中的Geometry.is_seg_intersect()判断两线段是否相交。若与障碍物任一条边相交则该候选边不合法从图中剔除。is_seg_intersect()采用了计算几何中标准的跨立试验orientation test on_segment 特例处理通过叉积符号判断两条线段端点的相对方位orientation 为 1、2、0 分别表示顺时针、逆时针、共线若四条方位判定满足跨立条件则相交对于共线情况再通过on_segment()判断端点是否落在对方线段上。这一实现对“边恰好擦过障碍物顶点”等退化情形也能给出正确判定。Step 3在可视性图上用 Dijkstra 算法搜索最短路径第三步是在生成的无碰撞图蓝色线条上运行 Dijkstra 算法得到从起点到终点的最短路径红色线条原文档特别说明该可视性路图规划器使用 Dijkstra 方法进行图搜索This visibility road-map planner uses Dijkstra method for graph search并给出了 Dijkstra 算法的细节索引对应仓库内 grid_base_search 文档 中的_dijkstra锚点。在源码中planning()的末尾visibility_road_map.py将节点坐标列表与邻接表road_map_info交给 DijkstraSearch.search()使用open_set待扩展与close_set已扩展两个字典维护搜索过程每次从open_set中取出累计代价最小的节点进行扩展边的代价为两端点的欧氏距离math.hypot(dx, dy)节点代价沿路径累加因此最终得到的是一条几何意义上的最短折线路径搜索结束后由generate_final_path()沿parent指针回溯并反转得到从起点到终点的完整路径点序列rx, ry。三、源码结构从输入到输出的完整调用链为方便对照阅读下表整理了该模块涉及的核心文件与职责文件职责PathPlanning/VisibilityRoadMap/visibility_road_map.pyVisibilityRoadMap规划器主类与ObstaclePolygon障碍物多边形类PathPlanning/VisibilityRoadMap/geometry.pyGeometry.Point点结构与is_seg_intersect()线段相交判定PathPlanning/VoronoiRoadMap/dijkstra_search.py通用的DijkstraSearch图搜索库含Node数据结构PathPlanning/VisibilityRoadMap/init.py模块包标记文件tests/test_voronoi_road_map_planner.py针对该规划器的自动化冒烟测试3.1 VisibilityRoadMap 主类class VisibilityRoadMap: def __init__(self, expand_distance, do_plotFalse): self.expand_distance expand_distance self.do_plot do_plot def planning(self, start_x, start_y, goal_x, goal_y, obstacles): nodes self.generate_visibility_nodes(start_x, start_y, goal_x, goal_y, obstacles) road_map_info self.generate_road_map_info(nodes, obstacles) if self.do_plot: self.plot_road_map(nodes, road_map_info) plt.pause(1.0) rx, ry DijkstraSearch(show_animation).search( start_x, start_y, goal_x, goal_y, [node.x for node in nodes], [node.y for node in nodes], road_map_info) return rx, ry节选自 visibility_road_map.pyexpand_distance顶点外扩距离单位 m是决定路径与障碍物安全间距的核心参数取值越大路径离障碍物越远但可行通道可能变窄甚至无法找到路径do_plot是否绘制可视性路图蓝色边与节点分布planning()返回rx, ry两个列表即最终路径的 x、y 坐标序列。3.2 ObstaclePolygon 障碍物多边形类ObstaclePolygon 负责把用户传入的顶点列表规范化为“首尾闭合”且“按顺时针排序”的多边形close_polygon()若首尾顶点不重合则自动追加第一个顶点实现闭合make_clockwise()/is_clockwise()通过鞋带公式shoelace formula求多边形有向面积判断顶点绕向若不是顺时针则反转顶点顺序。这一规范化保证了后续顶点扩展与边碰撞检测的方向一致性plot()以黑色线条绘制障碍物多边形。3.3 DijkstraSearch 复用可视性路图规划器并没有自己实现图搜索而是直接复用了 VoronoiRoadMap/dijkstra_search.py 中的DijkstraSearch类。这一点从 visibility_road_map.py 的导入语句from VoronoiRoadMap.dijkstra_search import DijkstraSearch可以确认也再次说明该仓库在算法模块间强调组件复用路图生成策略可视性/维诺与图搜索算法Dijkstra是解耦的。四、运行示例与关键参数4.1 直接运行在仓库根目录下直接运行示例需已安装 requirements.txt 中的 numpy 与 matplotlib 依赖python PathPlanning/VisibilityRoadMap/visibility_road_map.py运行后会依次弹出三幅动画窗口先绘制起点红点、终点蓝点与障碍物多边形黑线随后显示生成的可视性图蓝线最后叠加 Dijkstra 搜索出的最终路径红线。4.2 示例中的默认场景与参数示例main()visibility_road_map.py默认配置如下参数默认值说明sx, sy10.0, 10.0起点坐标 [m]gx, gy50.0, 50.0终点坐标 [m]expand_distance5.0多边形顶点外扩距离 [m]障碍物 1三角形(20,30,15), (20,20,30)多边形顶点 x/y 列表障碍物 2四边形(40,45,50,40), (50,40,20,40)多边形顶点 x/y 列表障碍物 3四边形(20,30,30,20), (40,45,60,50)多边形顶点 x/y 列表自定义场景时只需修改起点、终点坐标调整expand_distance并按同样的“顶点列表”方式构造ObstaclePolygon对象加入obstacles列表即可。4.3 在代码中调用from PathPlanning.VisibilityRoadMap.visibility_road_map import ( VisibilityRoadMap, ObstaclePolygon) planner VisibilityRoadMap(expand_distance5.0, do_plotFalse) rx, ry planner.planning( 10.0, 10.0, # start x, y 50.0, 50.0, # goal x, y [ ObstaclePolygon([20.0, 30.0, 15.0], [20.0, 20.0, 30.0]), ObstaclePolygon([40.0, 45.0, 50.0, 40.0], [50.0, 40.0, 20.0, 40.0]), ObstaclePolygon([20.0, 30.0, 30.0, 20.0], [40.0, 45.0, 60.0, 50.0]), ], )4.4 测试验证仓库通过 tests/test_voronoi_road_map_planner.py 对该规划器做冒烟测试测试中先把模块级开关m.show_animation置为False关闭绘图再调用m.main()完整跑一遍默认场景。可手动执行python tests/test_voronoi_road_map_planner.py测试能顺利结束即说明节点生成、可视性图构建与 Dijkstra 搜索三个环节在默认场景下可正常闭环。从代码看main()中并未显式断言路径非空因此实际使用时建议参考 VoronoiRoadMap 示例 的做法对返回的rx增加assert rx之类的非空校验以应对“外扩距离过大导致无可通行路径”的失败场景。五、方法特性与适用边界综合原文档与源码可视性路图规划器具备以下特点理解这些有助于在工程中正确选型完整性与最优性只要路图构建完备顶点外扩合理、碰撞检测正确在可视性图上用 Dijkstra 搜索得到的是一条长度意义上的最短无碰撞路径这一点优于基于采样的 RRT 类方法后者只能保证概率完备几何精确、无采样随机性节点完全由障碍物多边形顶点决定同一场景下多次运行结果确定易于复现与调试适用前提是“多边形障碍物”输入必须能表示为凸/凹多边形顶点列表。从源码看is_edge_valid()对凹多边形同样按逐边检测处理但顶点外扩方向仅由相邻两条边决定凹多边形的凹顶点处外扩效果需要结合场景验证计算开销集中于全连接建图generate_road_map_info()对每对节点都做一次逐边碰撞检测复杂度随节点数≈多边形顶点数与边数增长顶点数量多或障碍物边数多时建图成本显著上升适合顶点规模适中的结构化场景存在解的前提expand_distance过大可能导致相邻障碍物间的可行通道被“封死”此时图不连通Dijkstra 搜索会打印 Cannot find path 并返回空路径需要适当调小外扩距离。六、扩展阅读原文档中关于 Dijkstra 算法细节的索引对应仓库内 PathPlanning/Dijkstra/dijkstra.py 及 grid_base_search 文档 的_dijkstra一节使用同一套DijkstraSearch库但采用采样建图策略的 VoronoiRoadMap 规划器可与本文的可视性建图形成对照学习本文档所在章节的更多路径规划方法RRT、A*、Dijkstra、样条曲线等可浏览 path_planning_main.rst 目录总览关于可视性图方法本身的理论背景可参考计算几何与机器人学教材中 “Visibility graph” 相关章节原文档引用了维基百科同名条目此处不再赘述外部链接。【免费下载链接】PythonRoboticsPython sample codes and textbook for robotics algorithms.项目地址: https://gitcode.com/GitHub_Trending/py/PythonRobotics创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
