可视图法：让机器人在多边形世界里找到最短路径
说实话，我第一次接触可视图法时，觉得这名字起得真贴切——就是把障碍物之间的「可见关系」画成一张图。你想想看，机器人要避开障碍物走最短路径，本质上就是在这些障碍物之间找一条「看得见」的直线通道。
我在做仓储机器人项目时，遇到过这样一个场景：仓库里堆满了各种形状的货架，机器人需要从A点走到B点。如果用栅格法，地图分辨率高了计算量太大，分辨率低了又容易撞到货架角。后来我换成了可视图法，问题一下子就清晰了。
可视图法的核心思想
可视图法的原理其实很直观。我们把机器人的起点、终点，以及所有多边形障碍物的顶点都看作「节点」。如果两个节点之间的连线不穿过任何障碍物内部，那这条线就是「可见的」，我们就在这两个节点之间连一条边。
为什么要这么做？因为最短路径一定是由这些可见线段组成的。说白了，机器人贴着障碍物顶点走直线，就是最短路径。这个结论在数学上叫「最短路径的顶点性质」，我在实际项目中验证过无数次，确实如此。
核心要点：可视图法将路径规划问题转化为图论中的最短路径问题。节点是起点、终点和障碍物顶点，边是可见线段，权重是欧氏距离。
构建可视图的步骤
构建可视图听起来复杂，其实就三步。我习惯用伪代码先理清思路，再动手写实现。
- 提取所有节点：起点S、终点T、每个多边形障碍物的所有顶点
- 判断可见性：对每一对节点，检查连线是否与任何障碍物相交（不包括在顶点处接触）
- 构建图结构：如果可见，则添加一条边，权重为两点间的欧氏距离
这里有个坑，我踩过好几次。判断线段是否与多边形相交时，要特别注意「共线」的情况。如果线段恰好贴着障碍物的边，或者穿过顶点，这算不算可见？
注意：线段穿过障碍物顶点时，通常视为「可见」。但贴着障碍物边的情况要小心处理——如果线段与障碍物的边重合，那这条路径实际上是不可行的，因为机器人会撞到障碍物。
可见性判断的几何算法
判断两条线段是否相交，我推荐用「跨立实验」。这个方法计算量小，而且容易处理边界情况。
def is_visible(p1, p2, obstacles):
"""
判断p1和p2之间是否可见
obstacles: 多边形障碍物列表，每个多边形由顶点列表表示
"""
# 检查是否与任何障碍物相交
for polygon in obstacles:
vertices = polygon.vertices
n = len(vertices)
# 遍历多边形的每条边
for i in range(n):
a = vertices[i]
b = vertices[(i + 1) % n]
# 如果p1或p2在多边形内部，不可见
if point_in_polygon(p1, polygon) or point_in_polygon(p2, polygon):
return False
# 检查线段p1p2与边ab是否相交
if segments_intersect(p1, p2, a, b):
# 排除在顶点处接触的情况
if not (p1 == a or p1 == b or p2 == a or p2 == b):
return False
return True嗯，这里要注意segments_intersect函数的实现。我习惯用向量叉积来判断，这样能避免浮点数精度问题。
在简单多边形障碍物中的应用
简单多边形障碍物，说白了就是不自交的多边形。这类障碍物在实际场景中最常见，比如房间的墙壁、办公桌的轮廓。
我记得有一次做室内机器人导航，房间里有张L型办公桌。用可视图法处理时，我把桌子的四个顶点都作为节点。结果发现，起点到终点的最短路径竟然贴着桌角走——这在物理上是可行的，因为机器人可以刚好擦着桌角转弯。
但这里有个实际问题：机器人的尺寸。如果机器人有半径r，那我们不能真的贴着障碍物走。我通常的做法是：
- 对障碍物进行「膨胀」处理，把每个顶点向外偏移r
- 或者直接在可见性判断时，给线段加上一个安全距离阈值
我的经验：对于简单多边形，可视图法的计算复杂度是O(n²)，其中n是顶点总数。如果障碍物数量不多（比如少于50个），这个方法是实时可用的。但如果障碍物很多，建议先用凸包简化，或者改用其他方法。
一个完整的例子
假设有一个矩形障碍物，顶点为A(0,0), B(4,0), C(4,3), D(0,3)。起点S(-1,1)，终点T(5,2)。
构建可视图的过程：
- 节点集合：{S, T, A, B, C, D}
- 检查可见性：
- S→A：可见，因为连线不穿过矩形
- S→B：不可见，因为穿过矩形
- S→C：不可见
- S→D：可见
- ...以此类推
- 最终得到图结构，用Dijkstra算法求最短路径
结果你会发现，最短路径是S → A → B → T，或者S → D → C → T。这两条路径长度相同，都是贴着障碍物的两个角走。
可视图法的优缺点
| 优点 | 缺点 |
|---|---|
| 能找到全局最短路径 | 计算复杂度高，障碍物多时慢 |
| 适合多边形障碍物 | 不适用于凹多边形（需要先分解） |
| 路径平滑，没有锯齿 | 路径紧贴障碍物，不够安全 |
| 理论成熟，实现简单 | 动态环境需要重新构建 |
总结一下：可视图法是我个人非常喜欢的一种路径规划方法。它把几何问题转化为图论问题，思路清晰，实现起来也不复杂。虽然现在有很多更先进的算法，但在处理多边形障碍物的场景下，可视图法依然是最直观、最可靠的选择之一。
我曾经在一个项目中，用可视图法配合A*算法，实现了机器人在复杂办公室环境下的实时导航。效果出奇的好，连客户都惊讶于路径的「聪明」——机器人知道贴着墙角走，而不是在空旷地带绕远路。
当然，可视图法不是万能的。如果你遇到的是凹多边形障碍物，或者障碍物数量特别多，我建议考虑其他方法。但作为路径规划的基础知识，可视图法值得你花时间好好掌握。
可可精品资料库