双向连接边表（DCEL）

形式陈述

在一张地图中，“从这个街区绕一圈”“越过这条边到隔壁”“列出一个路口周围的街区”需要三种不同的邻接关系。普通邻接表知道哪些顶点相连，却没有记录边在平面上的环绕次序，也没有直接记录面。双向连接边表（DCEL）为一个已经嵌入平面的平面图保存这些信息。

输入是有限直线细分：不同边的内部不相交，交点已拆成顶点；几何坐标与拓扑关联必须相容。每条无向边拆成方向相反的两条半边。半边 $h$ 保存起点 $\operatorname{origin}(h)$ 、反向半边 $\operatorname{twin}(h)$ 、同一面边界上的前后半边 $\operatorname{prev}(h),\operatorname{next}(h)$ ，以及位于它左侧的面 $\operatorname{face}(h)$ 。

最基本的不变量是

\operatorname{twin}(\operatorname{twin}(h))=h, \qquad \operatorname{prev}(\operatorname{next}(h))=h, \qquad \operatorname{next}(\operatorname{prev}(h))=h,

以及

\operatorname{origin}(\operatorname{next}(h)) =\operatorname{origin}(\operatorname{twin}(h)), \qquad \operatorname{face}(\operatorname{next}(h))=\operatorname{face}(h).

因此反向半边的起点也是本半边的终点。顶点保存任意一条从它出发的半边；面保存外边界的一条半边，以及每个孔洞边界的一条半边。无界面没有有限的外边界，却可以有多个内边界环；孤立顶点另外记录所在面，不能硬造一条零长度边。

边界始终把所属面留在左侧。有界面的外环逆时针，孔洞环顺时针。这是有向边界的约定，不要求所有 next 环都逆时针。把孔洞反向标成外环，会使局部指针看似成环，却表示了错误的面。

直觉

同一条几何边需要被两侧的面分别走过。半边相当于给道路的两侧各发一张通行证：沿 next 继续绕当前面，沿 twin 则跨过边换到另一侧。一个 next 环就是一条双向循环链表，但所有环又通过 twin 配成整张细分。

从起点为 $v$ 的半边 $h$ 出发，反复执行 $h\leftarrow\operatorname{next}(\operatorname{twin}(h))$ ，每次仍得到一条从 $v$ 出发的半边。在通常的二维流形型细分中，这会按环绕次序遍历 $v$ 的 incident 半边。坐标没有参与这次导航：几何已在构建时决定拓扑，之后局部查询只跟指针走。

正方形沿对角线分成两面；两条对角半边分别属于不同边界环；删除后两环接成一个 — 半边与删边合面

例子与边界

一条对角线占两个位置

取正方形 $A=(0,0),B=(4,0),C=(4,4),D=(0,4)$ ，加入对角线 $AC$ 。三个 next 环是

\begin{aligned} f_1 &: AB\to BC\to CA\to AB,\\ f_2 &: AC\to CD\to DA\to AC,\\ f_\infty &: BA\to AD\to DC\to CB\to BA. \end{aligned}

这里 $AB$ 表示从 $A$ 指向 $B$ 的半边；其 twin 是 $BA$ 。几何边共有五条，半边有十条。若只存一条 $AC$ 记录，就无法同时记录它在 $f_1$ 中以 $CA$ 方向、在 $f_2$ 中以 $AC$ 方向出现。

现在删除对角线、合并 $f_1,f_2$ 。先保存待删半边两侧的前后指针，再把

BC\to CA\to AB,\qquad DA\to AC\to CD

改接成

BC\to CD,\qquad DA\to AB.

对应的两个 prev 指针也一起改写。删除 $AC,CA$ ，将四条内部半边的面标识改成同一个新面，外面环保持不动。最后重新检查上述不变量，并验证新环恰为 $AB,BC,CD,DA$ 。

这说明“局部接链只要常数次写指针”与“整个操作必为常数时间”不是同一句话。若每条半边直接存面对象，合并面时重标边界可能要走过许多半边；更新孔洞归属、删除失效顶点关联也要计入。不能只数那四次 next/prev 改写。

指针正确还不等于几何正确

把 $C$ 移到一条不相邻边的另一侧而不修改关联，所有 twin 和 next 等式仍可能成立，但图形已经自交。因此 DCEL 的校验有两层：拓扑链接校验，以及坐标是否真的实现该嵌入的几何校验。

一条桥的两侧可能属于同一个面，沿面边界会以两个方向遇到它；“两条半边属于不同面”并不是通用不变量。若边界含桥或多个连通分支，面记录必须容纳相应边界游走，不能只接受简单多边形环。用于三角剖分的无孔连通输入较简单，却不应把这些额外性质写进一般 DCEL 定义。

推论与应用

存储量为 $O(V+E+F)$ ；每条边仅增加常数个关联。绕一个含 $k$ 条半边的边界走一圈花 $O(k)$ ，跨一条边为 $O(1)$ ，枚举一个度数为 $d$ 的顶点周围半边为 $O(d)$ 。从任意坐标寻找所在面则不是 DCEL 自带的操作，需要另建点定位结构。

单调多边形划分和耳切会插入或删除对角线。DCEL 可以保存修改后的面，但算法还必须证明新对角线位于正确区域、不会穿过旧边。数据结构负责忠实记录一次合法修改；合法性的几何证明由修改算法负责。

参考资料

Mark de Berg 等，Computational Geometry: Algorithms and Applications，第 3 版，2008，§2.2，平面细分与 DCEL。大学课程所用原书
Dave Mount，CMSC 754，2020，Lecture 10: The Doubly-Connected Edge List，pp.1–4。该讲义通过辅助边简化带孔面的边界；本页采用显式保存多个边界环的接口。

形式陈述 ​

一条对角线占两个位置 ​

指针正确还不等于几何正确 ​

反向链接

形式陈述

一条对角线占两个位置

指针正确还不等于几何正确