数学大学
F. DCEL
计算几何 · 04. Voronoi Diagram
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
F. DCEL
计算几何 · 04. Voronoi Diagram
Twin Edges
孪生边（twin）：Voronoi 边是两胞腔的共享边界，每条边有方向相反的两份记录。
成对
每条边存两份半边，互为孪生
两侧面
半边与孪生边各自贴着不同的胞腔
Half-Edge
半边（half-edge）：带方向的边记录，存起点、孪生指针、所在面与下一条半边。
字段
origin、twin、incidentFace、next 等指针
环形遍历
沿 next 指针绕面一圈
Vertex & Face
顶点与面的记录：顶点存一条射出半边，面存一条边界半边。
顶点记录
坐标 + 一条以其为起点的半边指针
面记录
站点信息 + 边界上任意一条半边
Traversal
遍历：绕面、跨面、绕点三类基本遍历支撑一切邻接查询。
绕面
沿 next 环游面边界
跨面
经 twin 跳到邻面继续
绕点
沿 twin-next 组合环游入射半边
True Or False
概念辨析题：半边方向、twin 指向、面归属的真假判断练习。
方向
半边方向与绕面方向一致
孪生
twin 的 incidentFace 是对面的胞腔
Application
应用：最近邻查询沿半边结构从当前胞腔跳向邻胞腔，逐近排序。
最近邻
从查询点所在胞腔出发向邻胞腔扩展
效率
利用局部性避免全图扫描
本节要点
- ✓半边结构：方向化的边记录
- ✓twin 连接两胞腔，next 绕面
- ✓遍历原语支撑全部邻接查询
延伸主题：实现 DCEL 的三类遍历在 DCEL 上做最近邻查询
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1半边结构为什么比「每条边存左右面」更适合遍历？
参考答案半边把方向信息下沉到边记录本身：沿 next 走就是绕面，跨 twin 就是换面——遍历不需要任何搜索。存左右面虽省一半空间，但每次换面都要全表查找。
2绕点遍历的指针组合为什么是「twin 后再 next」？
参考答案从射出半边出发，先跨 twin 到对侧、再沿 next 前进，恰好落到下一条以该点为起点的半边。循环执行即枚举所有以该点为起点的半边，实现绕点一圈。
3DCEL 如何支持「删除一条边」的更新？
参考答案删除边需把其两条半边从各自的面环中摘除：前驱的 next 直接指向后继，两面的边界随之变化。若某面环缩为零则该面消失。指针一致性是更新的全部难点。