Delaunay Triangulation & Convex Hull

Instead of reviewing what Delaunay Triangulation is, please refer to the linked Wikipedia article. You don't have to understand the entire thing, just that every triangle's circumcircle must not contain another point. For this discussion it will only keep things in 2 dimensions. For all of you impatient people (like me), here is something to play with for a while.

Click to add a point, click and drag to move the point around. The green outline is the convex hull.

 

The Incremental Algorithm

This example implements the incremental algorithm to compute the Delaunay Triangulation. It is one of the simpler algorithms. This algorithm can run in O(n log n), but my version takes some shortcuts and does not run that efficiently. (This paper (mostly Section 4) was used for implementation of this algorithm. But hopefully I can describe it enough so that you won't have to reference it.) As a note, I will use the term "triangle" and "face" interchangeably but they mean the same thing.

It is called the "incremental" algorithm because we incrementally add 1 point at a time and compute the triangulation. So very simplistically the algorithm is:

1. Take the next un-added point, which we will call p
2. Determine what face p is in, which we will call f
3. Break f into 3 smaller faces, which we will call f₁, f₂, and f₃ 
4. Continue till all points have been added

Visually it would look something like this (the green outline is the convex hull):

However it is not that easy. Although (I believe) this will always give you a triangulation of the points, it can lead to very narrow triangles since every time a triangle is broken into 3 smaller ones.

Edge Flipping

So why does this not work for computing a Delaunay Triangulation? Say we have two faces, and we go to insert a point inside one of them. This can cause an adjacent face to have a point inside one of the new circumcircles (thus violating the condition of the Delaunay Triangulation). If we go to add the red point and make the 3 new faces, the point on the far right will be inside the circumscribed blue circle of one of the newly created faces. To solve this, we need to "flip" the common edge.

This gives us two new faces. You can see how this helps in avoiding very narrow triangles. Why flipping an edge is guaranteed to work, I'm not really for sure of, but it works! So how do we detect when we need to flip an edge. In short, we must check the 3 new faces. We will call this function ValidEdge(). Note that it will recursively call itself if an edge was flipped, because we have to check the two new faces.

1. Find the adjacent and opposite face (which may or may not exist), which we will call f_adj
• The adjacent face will share 2 points (this means it is adjacent)
• And, neither of the 2 shared points will be p (this means its opposite)
2. If the only unique point of f_adj is inside of the face's circumcircle, then flip the edge
• This creates 2 new faces, and gets rid of the current face
3. Recursively call ValidEdge for the 2 new faces

Although this seems kind of complicated, if you draw it out and work through several cases it makes sense. All this will take place in between steps 3 and 4 of the incremental algorithm.

Starting the Algorithm

What if we select a point that is not inside any face? Well, the solution is to not do it. This is because of how the algorithm is started off (how would we add the first point, anyways). We first create a huge face that covers the entire area that points could be in, which I'll reference as the Omega face. In our case it has to be big enough to cover the 400x400 pixel screen.

This way, we are guaranteed that any point we add will be inside of a face, and the algorithm will work properly. After all of the points have been added, and all the faces created, just ignore any face that has a point from the Omega face. Then you are left with the faces that triangulate your points...and well...that's it! You should be left with a Delaunay Triangulation of the points.

The Convex Hull

To find the convex hull of the points, the Omega face is important. A face can share either 0, 1, or 2 points with the Omega face. If it shares just 1 point of the Omega face, this means the other 2 points of our face belongs to our computed triangulation, giving an edge that is part of the convex hull.