简单多边形最短路的漏斗算法

维护三份状态：已经确定的共同路径 tail，以及从其末点 $a$ 分别通到当前门户左右端点的链 $L,R$。$a$ 称为 apex。沿 $L$ 的内部转弯向左，沿 $R$ 的内部转弯向右；这两条链和门户围成一个扇状可见区域。到门户任意一点的最短路，先走共同 tail，再沿其中一条边界链走一段，最后直达该点。

新门户只替换一个端点。若新端点还能由当前 apex 看见，便收紧相应一侧；如果越过另一侧的第一条射线，就必须先绕过那一侧的第一个拐点。这个拐点从“可能要经过”变成“所有后续路径都必须经过”，于是移入 tail，成为新 apex。

不重新扫描旧门户的链算法 ​

两条链用双端队列公理库双端队列Deque · Double-ended queue在同一有序序列的首尾两端都支持插入与删除的抽象数据类型。保存：链尾按后进先出顺序弹出，链首用于移动 apex。tail 最后一项与两链首项是同一个点。以下是替换左端为 $v$ 的完整规则；右端规则镜像对称。

1. 只要 $L$ 至少有两点，且 $\mathrm{orient}(L_{-2},L_{-1},v)\le 0$，弹掉 $L$ 的尾点
2. 若 $L$ 只剩 apex，检查另一链：只要 $R$ 至少有两点，且 $\mathrm{orient}(R_0,R_1,v)<0$，删除 $R$ 的旧首点，把新首点加入 tail，并让 $L$ 的唯一点改成新 apex
3. 若 $v$ 不等于当前左端，将 $v$ 加到 $L$ 尾部

替换右端时，第一步条件改为 $\mathrm{orient}(R_{-2},R_{-1},v)\ge 0$；第二步改为 $\mathrm{orient}(L_0,L_1,v)>0$，从 $L$ 首端推进 apex。完全相同的端点不重复插入。共线时合并不必要的链尾点，只有严格越过另一侧才移动 apex。

这些方向判断公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。对应两种几何修复：尾端弹出删掉已经可以直连跨越的旧拐点；首端弹出则确认必须绕过的拐点。后者是推进最短路共同前缀，不是把所有已处理门户退回去再算一遍。

四个门户与两个真正拐点 ​

仍用耳切页的十边形，取 $s=(1,5),t=(7,5)$。那份剖分给出的门户依次为

第一步 $L=[s,(4,2)]$、$R=[s,(0,0)]$。第二门户把 $(6,2)$ 压到左链，得到 $L=[s,(4,2),(6,2)]$，右链不变。

第三门户把右端改成 $(8,0)$。先弹掉旧右端 $(0,0)$，再发现新右端越过左链第一条射线，必须先经过 $(4,2)$。于是 tail 变为 $[s,(4,2)]$，两链变为

第四门户把 $(6,6)$ 加入左链。处理最终目标 $t$ 时，$(6,6)$ 被弹掉，而 $(6,2)$ 留下。输出 tail 去掉重复 apex 后接最终左链，得到

核验程序记录六次新链点插入、三次删除、一次 apex 前移，旧门户重扫次数为零。独立可见图公理库可见图与多边形障碍最短路Visibility graph shortest path证明欧氏避障最短路只在多边形角点转弯，再把连续路径问题精确化为带几何可见边的图最短路。给出相同长度；每段也通过精确的自由区域检查。

链不变量说明每次删除都不会丢掉最短路：同侧非凸拐弯可由弦缩短，跨到另一侧则由通道边界强迫经过旧链的下一个拐点。剩余的尾与两条凹链继续描述到整个门户的最短路族，故归纳到目标点时得到最短路。

设通道有 $k$ 个门户。每个新门户只带来一个新端点；它在对应链中插入一次，之后至多从尾端删除一次，或随着 apex 推进从首端删除。已删记录不再插回。这一按记录计费的摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。给出总链操作为 $O(k)$，最终输出另花 $O(h)$，其中 $h\le k+2$ 是路径顶点数。状态空间为 $O(k)$。

从头计时，还需三角剖分、定位起终点、搜索对偶树。用单调划分剖分为 $O(n\log n)$，线性扫描定位与树搜索为 $O(n)$，漏斗也为 $O(n)$；采用简单耳切，前置成本则为 $O(n^2)$。不能把“漏斗线性”写成任何剖分实现的端到端线性。

只保存左右两条射线、换 apex 后从某个旧门户重新开始的短实现，可能多次处理同一门户。它并不自动继承上述链记录的摊还证明。本页实现显式保留两条链，用删除计数证明线性。带孔区域的对偶图有环，任取一条通道只能得到该通道或同伦类别内的解，不能直接声称是全局最短。