M. Plane-Sweep
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
M. Plane-Sweep
计算几何 · 04. Voronoi Diagram
A First Glance
Fortune 扫描线算法一览：扫描线自上而下推进，海滩线记录当前最近边界。
Backtracking
为什么朴素直接法会走回头路：早期决策可能被后续站点推翻。
Fortune's Trick
Fortune 的魔法：把站点向上「膨胀」一个与扫描线等距的量，遮挡未定区域。
Frozen Region
冻结区域：扫描线以上、海滩线以下的部分——其内部形状尚未定局。
Beach Line
海滩线：各站点抛物线（焦点在站点、准线是扫描线）的下包络线。
Lower Envelope
海滩线是抛物线族的下包络：任一 x 处取最低的弧。
Break Points
断点：相邻两弧的交点，恰好落在某对站点的平分线上。
Events
驱动扫描的两类事件：站点事件与圆事件，各有确定的产生与消失时机。
Circle Event: What, When
圆事件三问：什么（弧消失）、何时（外接圆最低点被扫到）、何地（外接圆最低点处）。
Circle Event: Why
为什么弧会消失：相邻两弧的断点追上了本弧与另一侧的断点。
Circle Event: How
圆事件的实现：三弧组合注册、失效即删除——优先队列管理。
Site Event: What
站点事件：扫描线到达一个新站点，海滩线上长出一株新抛物线弧。
Site Event: How
站点事件的处理：定位新弧所在弧段、分裂、注册新的潜在圆事件。
本节要点
- ✓Fortune 技巧：膨胀遮挡未定区域
- ✓海滩线 = 抛物线下包络，断点轨迹即边
- ✓站点事件长弧，圆事件消弧
- ✓优先队列 + 平衡树 = O(n log n)
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
参考答案把欧氏距离换成「到站点与到扫描线的距离之差」：扫描线以下的部分因未确定而不参与比较，海滩线恰是两种距离相等的点的轨迹。变形让「不确定」自动被遮挡，算法不需要回溯。
参考答案弧消失的原因是两侧断点相遇夹缩，而断点只存在于相邻弧之间。三弧相邻才能形成「两侧夹中间」的收缩结构；不相邻的弧组合对应的圆内必有其他站点，不是空圆。
参考答案事件总数 O(n)（n 个站点事件 + O(n) 个圆事件），每个事件的处理涉及平衡树定位与优先队列操作，均为 O(log n)；断点轨迹总长（即输出边长）线性。三者合计 O(n log n)。