H. Sorted Sets
数学大学
H. Sorted Sets
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
H. Sorted Sets
计算几何 · 04. Voronoi Diagram
Convex Hull Made Easier
借助 Delaunay 对偶：凸包恰是 Delaunay 三角剖分中落在无限区域边界的部分。
对偶读出
Voronoi 的无穷边对应的站点即凸包顶点
顺序
凸包顶点在边界上自然有序
Convex Hull As A Combina
凸包作为组合结构：顶点的循环次序与邻接关系是它的全部信息。
循环序
顶点沿边界绕行的次序
邻接
相邻顶点对即凸包的边
Voronoi Diagram As A Geo
Voronoi 图作为几何结构：顶点、半边、胞腔在 DCEL 中精确定位。
几何对象
顶点是外接圆圆心，边是平分线段
结构价值
结构化存储让最近邻等查询系统化
本节要点
- ✓Delaunay 无界三角形对应凸包边
- ✓凸包 = 循环顶点序 + 邻接关系
- ✓Voronoi 图在 DCEL 中结构化存储
延伸主题：从 Delaunay 读出凸包对照两种结构存储同一信息
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1「凸包作为组合结构」与「几何结构」的表述差别是什么？
参考答案组合结构只记顶点的循环次序与邻接，不含坐标；几何结构再补上精确位置。前者适合做离散推理（如翻转操作），后者服务数值计算——两个层次各司其职。
2Delaunay 三角剖分与 Voronoi 图的对偶关系具体指什么？
参考答案Delaunay 边对应 Voronoi 边（垂直平分线段），Delaunay 顶点对应 Voronoi 胞腔，Delaunay 三角形对应 Voronoi 顶点。知道其一即可在 O(n) 内构造另一。
3为什么「无限边的 Voronoi 边」能定位凸包顶点？
参考答案Voronoi 边延伸到无穷远，说明其对应站点的胞腔无界——无界胞腔的站点必在站点集凸包的边界上。沿无界边遍历站点，就是按序枚举凸包顶点。