什么是DCEL
在 「计算几何」Fortune 算法生成维诺图（Voronoi Diagram） 这篇文章中，我们已经了解了如何使用扫描线算法计算一个平面的维诺图（Voronoi Diagram）。其中曾提到了一种数据结构 DCEL，那么 DCEL 到底是什么？它又有哪些用途呢？
事实上，维诺图的最终结果是一种平面划分（planar subdivision），它把整个二维平面根据一系列点的影响范围，分割成了若干不相交的多边形区域。这种划分不仅有点、边、面的几何信息，更重要的是，它还隐含着丰富的拓扑结构——比如哪两个区域是相邻的，某条边是哪个面的一部分，某个顶点连接了哪些边等等。
而 DCEL（Doubly Connected Edge List，双向链接边表）就是为了表达这种平面划分而生的数据结构。它把每条边拆成两条方向相反的半边（half-edges），通过各种指针把点、边、面有机地串联在一起。 DCEL 的核心思想很简单：把「平面上的拓扑关系」拆解成 3 个主要的结构单元：顶点（Vertex）、半边（Half-Edge） 和 面（Face）。每一个单元都不单是几何上的“点”“边”“区域”，更关键的是，它们通过彼此的引用关系，构成了整个划分结构的骨架。
- 顶点（Vertex）
一个顶点代表平面上的一个几何点，如下图所示，它通常包含：
- 这个点的坐标 (x, y)；
- 指向一条从该顶点出发的半边的指针。
注意：一个顶点可能连接好几条边（例如在一个多边形的交点），所以这个“出发的半边”只是其中任意一条。我们可以通过接下来的结构去找到其它邻接的边。
- 半边（Half-Edge）
半边是 DCEL 的核心单元。每条边都会被拆成两个方向相反的半边，它们彼此称为 twin。以下图红色边为例，每个半边会存下这些信息：
origin：这个半边的起点（是一个顶点）；twin：它的“反向半边”，也就是同一条边的另一半；next：下一个半边，沿着当前面逆时针方向；prev：上一个半边，逆时针方向的前一条；incident_face：这个半边所围成的那个面（即它“左侧”的面）。
想象一下：站在一条半边上，看着它指向的方向，你的左手边就是 incident_face，前方是 next，后方是 prev，你对面那个倒着来的半边就是 twin。
- 面（Face）
一个面代表平面划分中的一个区域（比如维诺图中的某个 cell）。如下图所示，它主要包含：
- 指向这个面边界上的某条半边的指针；
有了指向某条半边的引用，我们就可以通过 next 指针，把整个边界绕一圈走下来，从而获取这个面的完整轮廓。
所以，DCEL 是靠一套彼此引用的结构去组织和查询这些拓扑关系。不需要每次都全局扫一遍找邻接元素，只要顺着这些指针走几步，就能定位要找的邻接面、相邻边，或者围绕一个顶点的所有出边。
DCEL 的查询
如何从一个面出发，遍历它的边界？
每个 Face 结构体中，都会保存一条它边界上的半边。我们可以从这条半边出发，一直顺着 next 指针走，直到绕一圈回到起点。
如何找出某个顶点的所有出边？
每个 Vertex 都有一条出发的半边 incident_edge。但我们怎么找到所有从这个顶点出发的半边？
方法是这样的：从任意一条出边出发，顺着 twin.next 一直绕一圈回来。这就等于“围绕这个顶点的所有边扫一圈”。示意图如下：
如何找某条边相邻的两个面？
每条半边的 incident_face 是它左侧的面，而它的 twin.incident_face 就是右侧的面（或外部区域）。示意图如下：
参考资料
M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars, Computational Geometry: Algorithms and Applications, 3rd ed. Berlin, Germany: Springer, 2008, ISBN 978-3-540-77973-5.