CSE2010 - Data Structures

This is a demonstration of my Delaunay Triangulation and Voronoi Diagram application

• Click here to launch the application. Source code is included in the .jar file if you know how to fish that out.

• Delaunay Triangulation - With any given set of points, there are many ways those points can all be connected to form a set of triangles. A Delaunay Triangulation is a method of triangulating the edges with certain rules in mind. In order to be a valid triangle in a Delaunay Triangulation, the circle that circumscribes a triangle may not contain any other points within it.
  
• Voronoi Diagram - A Voronoi Diagram is a set of polygonal cells that encase each point in a set of points. These cells mark a region where any point within the cell has the inclusive point as its nearest neighbor.
  

The Delaunay Triangulation and the Voronoi Graph are considered Dual Graphs. That means that they are so closely related, that if you have one, you can use it to calculate the other. My program uses the user's inputed points to calculate the Delaunay Triangulation. Then it uses the triangulation to calculate the Voronoi Diagram.

I used a brute force approach to creating the Delaunay Triangulation. Storing the points in a vector, I loop through every possible combination (without repeating) of 3 points and test if the triangle formed by those points is valid. To check each triangle, a circumcircle has to be calculated.

Calculating the circumcircle involves a bit of reasoning. I know that the vertices of the triangle have to fall on the circumference of the circle. I also know that any point on the circumference is exactly the same distance from the center as any other point (the radius). I also know that with any 2 points, any point on a line dividing them equally will be of equal distance to each point. Since we want a point where all 3 vertices are equal distance from said point, the problem becomes a matter of finding the line that divides 2 vertices in the triangle and then finding the line that divides another set of 2 vertices in the triangle. The intersection of these 2 lines will be a point where all 3 vertices of the triangle are an equal distance away.

Once a circumcircle for the triangle has been calculated, the triangle can be checked for validity. To do that, loop through every point once again. Check if each point is within the circumcircle by finding the distance between it and the circumcenter. If that distance is less than the circle's radius, then it is within the circle. A valid triangle gets stored in the Delaunay Triangulation. An invalid triangle simply gets tossed out.

The Voronoi Diagram is calculated using the Delaunay Triangulation. It turns out that the circumcenter for each triangle in the Delaunay Triangulation is a vertex in the Voronoi Diagram of the same set of points.

Since I have all of the triangles, all that is needed is to find out which points connect to each other for the Voronoi Diagram. I start by once again looping through every point. For each point, it is determined which triangles connect to it (a triangle that has a vertice the same as said point connects) and the circumcenters of those triangles are stored. Connecting all of these points as a convex hull will correctly form the cell for that point in the Voronoi Diagram. However, in order for this to work the point we are examining has to be completely surrounded by triangles. The outside points in the triangulation will not have a complete set of triangles since there are no points beyond the outside edge to connect to. To make my Voronoi Diagram 'appear' correct, I added 3 points way outside the view of the screen. These points result in being the outside points and so any point the user adds will be inside of the whole structure and will have a complete set of surrounding triangles.

Connecting all of the points into a convex hull can be tricky, since the order the triangles were stored (and therefore examined) can not be garunteed to be in clockwise or counter-clockwise order to the point we are examining. To correcly draw the cells, we need a convex hull algorithm. I chose to use a modified version of Graham's Scan. Normally, Graham's Scan will order points in order by angle size. Then move forward through them performing certain checks. The algorithm assumes that the given points can be inside or outside the convex hull. So, the checks made are determining if the next point added will invalidate the previous points and correct them as being inside the hull. Because I am feeding the algorithm points that I know to be on the outside of the hull, I can assume that none will be inside the hull. My modified version only sorts the points by angle size and has no need to check for invalid points.

Once all of the points are ordered, they can be stored in the Voronoi structure as a polygon object. Find the cells for every point in the triangulation (including the 3 outside points) and a Voronoi Diagram can be drawn for the set of points given.