Click to add a point, click and drag to move the point around. The green outline is the convex hull.
The Incremental AlgorithmThis 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:
- Take the next un-added point, which we will call p
- Determine what face p is in, which we will call f
- Break f into 3 smaller faces, which we will call f1, f2, and f3
- Continue till all points have been added
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 FlippingSo 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.
- Find the adjacent and opposite face (which may or may not exist), which we will call fadj
- 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)
- This creates 2 new faces, and gets rid of the current face
Starting the AlgorithmWhat 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.