Fortunes Algorithm for Voronoi diagrams. Part 2. Where reader meets DCEL (Doubly Connected Edge List)
Geography lesson. Alice is asked to list all neighbour countries of Switzerland. Alice is a smart girl and she responds: “Germany, France, Austria and Italy”. Few years after Alice goes to the University to study Computer Science. She receives similar question.
How to store political map of the World (where each country is represented by a polygon) in a way to be able to efficiently perform the following operations:
 Given a country be able to draw this country contour
 Given a country be able to tell all it’s neighbours
 Given a coordinate be able to tell which country are you in
Little bit of library research, and Alice exclaims “Eureka!” and notes “DCEL” in her little black notebook.
DCEL fully satisfied Alices requirements and is useful in many other situation where we should store planar subdivisions.
Linked list and doubly linked list
For better understanding what is DCEL, let’s have a little recap and recall what is linked list and doubly linked list.
A linked list is a linear data structure where each element is a separate object. Linked list elements are linked using pointers. Unlike an Array, linked list is not stored as contiguos location. Linked list node cannot be accessed by index (it is not random access collection)
Linked list consists of nodes. Each node holds the data and the reference to the next node.
The last node has a reference to null. The reference to the first node is called head. Empty linked list is a reference to null
. Last element of the linked list holds reference to null
(tail).
To find an element in linked list you start from the head and follow references to the next
until your requirement is satisfied or you reach the last element. To iterate through all elements you can use while
loop until the reference to the next
pointer will be null
.
Doubly linked list (DLL) is very similar to the Linked list except one crucial difference. Each element of Doubly linked list holds the data and two references. One to the next
element and another to the previous
element. First element of DLL holds reference to next
and null
(because it has no previous node). Last element vice versa.
Doubly linked list is convenient data structure to store polygon (each linked list node represents a Point. previous
and next
are holding references to the previous and next vertex in selected order. Usually Counter Clockwise (CCW).
The anatomy of DCEL
A doublyconnected edge list contains a record for each Face, Edge and Vertex of the subdivision.
Pseudocode:
Vertex stores the coordinates of the point (x
, y
) and the pointer to incidentHalfEdge
(HalfEdge originating in this point)
Pseudocode:
Half edge Holds references to it’s prev
and next
 Inorder elements in a doubly connected linked list, reference to the twin
and to the incidentFace
. We will discuss twin and incident face a bit later. There is no point to store destination as it can be taken from twin
origin. Yet you can do it if you want :).
Pseudocode:
Edge is formed by two Half edges called twins.
In DCEL, half edges ${a}$ and ${b}$ are twins when:
 They hold a pointer
twin
to each other origin
of ${a}$ is adestination
of ${b}$ and vice versa.
Two twin half edges form an Edge.
Edge is not explicitly defined in the DCEL data structure.
Face models closed (in most cases) region represented by Doubly linked list of half edges. Face holds the reference to the arbitrary half edge. Half edges of the Face are organised into looped Doubly linked list. In looped doubly linked list last element holds the reference to the firs and vice versa. You can iterate through half edges both ways. Each element can be visited. Be careful! It is very easy to create an infinite loop! Also keep an eye on memory leaks.
Pseudocode:
Each of the DCEL elements can hold one more reference to the satellite data of any kind. For instance – color, population number or anything else.
Some common operations on DCEL
 Visit all vertices for a given Face (often called Face Hull)
 Visit all edges for a given Face
 Find all neighbours of a given Face (this is how Alice solved her problem)
And many more. Given a DCEL implementation it is fairly easy to implement basic operations.
Conclusion
DCEL without any additional operations is literally a way of data organization. It is fairly simple data structure, yet it is fundamental if you are trying to work with Planar subdivisions.
It is also worth of saying that you can modify it for the sake of convenience and sacrifice a very little of memory resources.
If you will follow me on twitter @fewlinesofcode and read next articles in Fortunes Algorithm series, you will see the simple power of DCEL.
Swift code and Homework
Here is a naive DCEL implementation in Swift:
Homework for the curious ones:
 Name faces, edges, half edges as it is on the image
 Fix memory leaks

Implement basic DCEL operations:
 Visit all vertices for a given Face (often called Face Hull)
 Visit all edges for a given Face
 Find all neighbours of a given Face (this is how Alice solved her problem)
 This implementation uses reference types (classes). Can you reimplement it in Swift using value types (structs)?
How is it related to Fortunes algorithm?
The result of Fortunes algorithm is a Doubly Connected Edge List storing Voronoi diagram.
Where to go from here
This article is based on the third edition of amazing book “Computational Geometry. Algorithms and applications” by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars.
I highly recommend this book for reading.