# 终结任务：从房间轮廓到最短路与碰撞证书

## 题目

房间按逆时针次序有十个顶点：

| 编号 | 坐标 |
|---:|---|
| 0 | (0,0) |
| 1 | (8,0) |
| 2 | (8,6) |
| 3 | (6,6) |
| 4 | (6,2) |
| 5 | (4,2) |
| 6 | (4,5) |
| 7 | (2,5) |
| 8 | (2,6) |
| 9 | (0,6) |

点机器人从 s=(1,5) 走到 t=(7,5)，允许贴墙，不能离开房间。完成以下任务：

1. 说明为什么凸顶点 0 不是耳，给一份合法三角剖分并检查覆盖
2. 用 h=y+x/1000 的扫描方向划分单调块，记录每个 merge 义务何时解决
3. 在第三个单调块上执行栈剖分，并给出一次允许弹栈的方向值
4. 从第一份剖分提取 s 到 t 的三角形通道，按门户次序执行双链漏斗
5. 给出最短折线、精确长度和独立可见图核验
6. 对障碍 O=[4,7]×[2,4]、固定姿态机器人 B=conv{(0,0),(2,0),(0,1)}，构造参考点碰撞禁区；判断参考点 (3,2) 是否安全

可选核验：把倾斜四边形 ((−1,1),(2,−1),(5,2),(2,4)) 裁到 [0,3]×[0,2]，验证面积 71/12；计算六边形 ((−1,3),(0,0),(4,0),(6,2),(4,5),(1,6)) 的直径。

## 解答

### 1. 耳与覆盖

顶点 0 的邻居是 9、1，三角形 (9,0,1) 内含顶点 5=(4,2)，因此凸性并不足以让它成为耳。

依次输出：

(1,2,3)、(1,3,4)、(0,1,4)、(0,4,5)、(9,0,5)、(5,6,7)、(9,5,7)、(7,8,9)

每一片方向为正。八片面积和为 38，原多边形鞋带面积也为 38。每条原边只出现一次，每条内部对角线恰出现两次且方向相反。独立可见性检查确认所有对角线均在房间内。这几项一起构成覆盖证书；单独面积相等不排除重叠和遗漏。

### 2. helper 的两次待办

事件顺序为 2,3,8,9,6,7,4,5,1,0。

- 顶点 7 是 merge；处理后 e9 的 helper=7，等待下方连接
- 顶点 5 也是 merge；它先连接旧 helper 7，得到对角线 (5,7)，然后成为新 helper
- 顶点 1 是 regular；它替换 helper 前连接 (1,5)

最终面为 (5,6,7)、(1,2,3,4,5)、(5,7,8,9,0,1)。逐面从最高点沿两侧走到最低点，h 都严格下降。

### 3. 栈的状态

第三面的高度顺序是 8,9,7,5,1,0。

| 新点 | 原栈 | 动作 | 新栈 |
|---|---|---|---|
| 7 | [8,9] | 异链，输出 (7,8,9) | [9,7] |
| 5 | [9,7] | 同右链，方向值 orient(v5,v7,v9)=4>0，输出 (5,7,9) | [9,5] |
| 1 | [9,5] | 不能继续弹出 | [9,5,1] |
| 0 | [9,5,1] | 最低点收尾，输出 (0,1,5)、(0,5,9) | 完成 |

这里有四个三角形，符合六边形的 n−2 计数。

### 4. 门户与漏斗

把第一份剖分的三角形按输出顺序编号 0–7。通道的三角形编号为 4→3→2→1→0。门户按左、右端点写为：

1. ((4,2),(0,0))
2. ((6,2),(0,0))
3. ((6,2),(8,0))
4. ((6,6),(8,0))

初始 tail=[s]，L=[s,(4,2)]，R=[s,(0,0)]。

第二门户把 (6,2) 加入 L。第三门户替换右端，先删 R 的 (0,0)，然后越过左侧第一条射线，确认必须经过 (4,2)。此时 tail=[s,(4,2)]，L=[(4,2),(6,2)]，R=[(4,2),(8,0)]。

第四门户把 (6,6) 加入 L；插入目标 t 时又删掉这个可直连绕过的顶点，L 变为 [(4,2),(6,2),t]。没有重新访问任何旧门户。

### 5. 最短路证书

最终路线：

s→(4,2)→(6,2)→t

长度为 3√2+2+√10≈9.404918347287664。每条线段都在房间内。独立建立全部角点可见图后，Dijkstra 给出相同长度。

双链执行记录为六次新记录插入、三次删除、一次 apex 前移、零次旧门户重扫。总链记录数随门户数线性增长，符合正文的摊还证明。用重扫门户的实现作对照时，必须单独计数，不能继承这份界。

### 6. 机器人禁区

碰撞条件 x+B 与 O 相交等价于 x∈O⊕(−B)，不是 O⊕B。

反射后的 −B 有顶点 (−2,0),(0,−1),(0,0)。归并边方向得到五边形：

(2,2),(4,1),(7,1),(7,4),(2,4)

参考点 x=(3,2) 在禁区内，机器人顶点 (2,0) 平移到 (5,2)，触及障碍下边，因而不安全。枚举十二个顶点和再取凸包，会得到同一五边形，可独立核验边归并结果。

### 可选核验答案

裁剪输出可取 (3,2),(0,2),(0,1/3),(1/2,0),(3,0)，面积为 71/12。六边形最远点为 (−1,3) 与 (6,2)，平方距离 50，直径 √50。

## 验收标准

- 顶点顺序、每条边的方向、所有三角形方向与面积全部一致
- 不能只给最终对角线；必须给两次 merge 义务与一次同链弹栈的具体证据
- 门户左右标记前后一致，funnel 不回退处理旧门户，最短路长度与独立图解相符
- 明确点机器人贴边允许，有限机器人碰撞例的闭集相交禁止接触，两个模型不得混用
- Minkowski 和先反射 B；非凸、旋转姿态与膨胀后障碍合并的额外工作不能被遗漏

## 可运行核验

下载 foundation-geometry-capstone.py 后，运行 python foundation-geometry-capstone.py。仅使用 Python 3 标准库，精确方向与求交使用 Fraction；Euclidean 长度最后用浮点平方根。结果写到当前目录的 foundation-geometry-capstone-results.json。

脚本还对固定随机种子生成的 100 个候选轮廓做独立输入检查：99 个为有效简单多边形；第 62 个候选的边 1 与边 5 严格相交，被输入检查拒绝。99 个有效输入全部通过漏斗/可见图、单调剖分/面积计数和卡壳/穷举交叉检查；另外 40 组凸多边形和通过全部顶点和凸包核验。

速度说明：耳候选实现只复查两个邻居；funnel 不重扫门户；Minkowski 归并不调用凸包来修正输出。单调分块参考实现用直接活动边扫描，单调栈参考实现用通用排序，退化可见性参考实现用分段点内检查；这些慢核验实现的成本已在正文与脚本分别说明。