可见图与多边形障碍最短路

把一根细绳绕过障碍拉紧。没有碰到障碍的位置不可能保留弯折，因为两点之间的直线更短。落在一条障碍边中间的弯折也不是必要的：附近自由空间是一个半平面，仍可把两小段替成更短的直段。真正卡住绳子的只能是障碍角点。

严格说，取路径上一段没有障碍角点的局部区域。若它在自由内部，这里有一个小圆盘；若贴着边内部，则有一个自由半圆盘。两者均凸，把局部折线换成弦不离开自由空间。三角不等式说明，非共线折弯会严格缩短。因此最短路除了沿边界直行外，只能在角点改变方向。

每个相邻转弯点之间的直段可见，故一条连续最短路也是可见图中的路径。反过来，每条图边都经过自由性检查，图路径一定合法。两个最优值分别不大于对方，从而相等。对于有可行路的有限多边形环境，可以限制在某条已知可行路长度给出的有界区域内，利用有界长度曲线的紧性取得最短路；结论不是只对一个未必达到的下确界成立。

取 $s=(0,0),t=(8,0)$，两个矩形障碍为

直达线段穿过两个障碍，不可加入图。第一块上方与第二块下方之间存在一条斜向通道。可见图的最短路径是

长度

其中两条水平边沿障碍边界行走，必须保留；把“接触任何边都算碰撞”作为统一规则，就会错误删除这份最优解。若任务真的要求严格正安全间距，应该先膨胀障碍或改变自由空间，而不是在一个允许贴边的模型中临时删边。

路线也不能根据每个障碍单独选择“较近的一侧”。绕第一块的方向会改变到第二块的到达方向；可见图让所有角点选择一起参加最短路比较。按原始图边长排序贪心连线并不保存最优子结构。

怎样核验一条擦边线段 ​

一般位置下，可检查所有障碍边的严格交叉，再检查候选线段端点附近是否进入障碍，或用适当的内部点测试处理穿过障碍的弦。判断相交的符号来自方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。，分类内部/边界则使用点内判定公理库点在多边形内判定Point in polygon · Point-in-polygon test先识别边界，再以射线横截奇偶或绕数把查询点分类为简单多边形内部、外部或边界。。

为使共线和多顶点接触也可审计，本单元的参考检查更直接：把候选线段与所有边界的交点写成参数 $0\le \tau \le 1$，连同共线边的端点一起排序。在每两个相邻参数之间取一个中点；边界没有在该区间内被穿过，所以整个开子段的内外类型不变。每段都在自由区域中，线段才可见。这能正确处理“穿过一个顶点后进入障碍”以及沿一条边滑行的区别。

设障碍总顶点数为 $n$，单次完整可见性判断成本为 $C_{\mathrm{v}\mathrm{i}\mathrm{s}}(n)$。枚举所有顶点对需要 $O(n^2{C}_{\mathrm{v}\mathrm{i}\mathrm{s}}(n))$，最多保存 $O(n^2)$ 条边。随后使用Dijkstra 算法公理库Dijkstra 算法Dijkstra's algorithm在非负边权图中逐次确定最短距离的单源最短路算法。；稠密矩阵实现为 $O(n^2)$，二叉堆实现为 $O((n+E)\log n)$。

在明确的一般位置合约下，逐边检查可做 $C_{\mathrm{v}\mathrm{i}\mathrm{s}}=O(n)$，得到常见的 $O(n^3)$ 朴素建图界。上述分段参考检查有 $O(n)$ 个测试区间，每次点内分类再扫 $O(n)$ 条边，因此采用的是 $O(n^2)$ 可见性上界、$O(n^4)$ 建图上界。它是独立核验器，不冒称已经实现更快的旋转扫描可见图算法。

对于无孔房间，可以先三角剖分，再用漏斗算法公理库简单多边形最短路的漏斗算法Funnel algorithm在三角形通道上保存两条凹边界链，单向删点与移动 apex，在线性工作量内拉紧欧氏最短路。避开整张二次大小可见图。有限面积机器人则先通过Minkowski 和公理库凸多边形 Minkowski 和的边归并Minkowski sum of convex polygons归并两个凸多边形的边方向构造逐点和，并用反射后的机器人轮廓精确表达平移碰撞禁区。把碰撞转成参考点的禁区；转动机器人还增加姿态维度，不能继续只用本页二维点图。