Computational Geometry experiment

Delaunay triangulation of a set of points it the plan

November 2009

Introduction : problem presentation

Triangulation

Given a set of points S in the plane, the triangulation T of S consists in the subdivision of the convex hull of S, CH(S) into triangles whose vertices corresponds to points of S.

It has been demonstrated that any set containing 3 points or more admits at least one triangulation.

Triangulation of a set of 14 points

Common application : relief representation

In order to represent the relief of a piece of the earth's surface, the height of a few points are measured. One option consists in triangulating the set of measured points and represent the relief as a the polyhedral made of the triangles obtained, every vertex being affected with the height measured before.

Polyhedral representation of the relief

Therefore the height z of an arbitrary point P(x, y, z) of the map is obtained by detecting the triangle the point belongs to and solving a linear system comporting to the coordinates of the vertices of this triangle and x and y coordinates of P in the plane x and y.

Delaunay triangulation

A Delaunay triangulation is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

At least one Delaunay triangulation is guaranteed to exist for a set of point S.

An interesting property of a Delaunay triangulation is that it maximize the minimum edge of the set of triangles, avoiding the presence of “skinny” triangles.

Ordinary triangulation                              Delaunay triangulation
for the same set of points

In the case of relief representation, these skinny triangles can provide a poor representation of the local relief and should be avoided as much as possible. Hence, a Delaunay triangulation would fit well for that purpose.

Algorithms presentation : computing a Delaunay triangulation

Triangulation data structure : Doubly-Connected Edge List

In order to represent a triangulation, we have been using a structure named Doubly-Connected Edge List. The triangulation is represented by the lists of its vertices, half-edges and faces.

A vertex is characterized by its coordinates and is linked to one incident half-edge.

A face is linked to one half-edge on its outer boundary. It also is linked to a list of half-edges for each holes the face has.
Note: in the triangulation case, while the outer face is only linked to an half-edge on its inner boundary, the inner faces are only linked to an half-edge on their outer boundary.

Each edge is stored as two twin half-edges. An half-edge e is linked to:

Twin(e) the corresponding twin edge

Origin(e) the vertex it originates from

IncidentFace(e) the faces on its left

Next(e) and Prev(e) the successor and predecessor of e sharing the same incident face.

Relation of an half-edge e
in a Doubly Connected Edge List

Illustration of the different elements
composing a Doubly-Connected Edge List

Algorithm: Ordinary triangulation

This method allows us to create an ordinary triangulation based on a set of points.

Considering a set S of n points, we decide to order the points according to

The x coordinate

The y coordinate

We obtain a list of sorted points L.

Then we apply a divide and conquer algorithm to L.

L is recursively divided in smaller ans smaller lists l until each elementary list contains only 2 or 3 points.

An elementary triangulation of each elementary list is performed, it contains:

3 points case
3 vertices, 2 faces and 6 half-edges for the 3 points case

2 vertices, 1 faces and 2 half-edges for the 2 points case

2 points case

Finally, the recursive function returns triangulations of those small lists and merges them into bigger

triangulations.

Merging two triangulations

As the points were sorted according to their abscissa, this implies that the rightmost point of the left triangulation T1 will be situated on the left of the leftmost point of the right triangulation T2.

Hence, we can draw an edge between those two points. The DCEL structure of T1 allows us to go cross the exterior vertices of T1 by using the Next and Previous functions applied to the half-edge of the inner boundary of the exterior face. We use this possibility in order to create new triangles between T1 and T2 as shown in the diagram below.

Edges are progressively added from the first edge upwards from one vertex on T1. Once we can't trace an edge upwards with the next vertex on T2 (that is when the angle between those two points and the abscissa ax start to decrease), we will start to trace edges upwards from the last vertex on T2 that we connected. Finally, we go through the same process downwards from the first edge.

After all the points have been recursively merged, we obtain an “ordinary” triangulation of the whole set of points.

Algorithm: Delaunay triangulation

As defined earlier, a Delaunay triangulation DT(S) does not contains any point situated inside the circumcircle of any triangle of DT(S).

Every edge can be associated to 2 triangles, if the condition above is not satisfied for the triangles, a flip of the edge to the diagonal edge will generate a configuration satisfying the conditions.

The center edge doesn't satisfies the condition

The flipped edge satisfies the condition

Finally, the algorithm for transforming an ordinary triangulation into a Delaunay triangulation consists in checking whether every edge satisfies the condition and flip it in case it is not true until every edge satisfies the condition.

Program demonstration

Ordinary triangulation of a set of points

The Doubly-Connected Edge List permits a quick computing of the faces crossed by a line

References

Computational Geometry Algorithms and Applications (third edition)

Mark de Berg - Otfried Cheong - Marc van Kreveld - Mark Overmars