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:

- 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*f*,_{1}*f*, and_{2}*f*_{3 } - 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 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.

- 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) - If the only unique point of
*f*is inside of the face's circumcircle, then flip the edge_{adj } - This creates 2 new faces, and gets rid of the current face
- Recursively call ValidEdge for the 2 new faces

###
__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.__The Convex Hull__

## No comments:

## Post a Comment