Project 2: Delaunay Triangulations & Voronoi Diagrams

due: 03/31/2022
submission: push to GitLab and copy link to Canvas quiz

goals

  • implement the Bowyer-Watson algorithm,
  • convert your Delaunay triangulation to a Voronoi diagram,
  • smooth the vertices in a Delaunay triangulation,
  • improve the efficiency of your Delaunay triangulation algorithm.
part 1: implement the Bowyer-Watson algorithm (14 points)

Please implement the Bowyer-Watson algorithm as described in the notes to compute a Delaunay triangulation within a $[0,1]^2$ domain. Start by implementing the $\mathcal{O}(n^2)$ version (you can optimize it in Part 4 later). I have already initialized a set of Delaunay vertices in main.cpp which you should use to compute the Delaunay triangulation. Given some desired number of points N, some vertices are initially placed at the corners of the $[0,1]^2$ domain. Then, some vertices are placed randomly in the interior of the domain (in such a way that these interior vertices are spaced away from the domain boundaries so they are contained within the initial two supertriangles). The first two supertriangles, therefore, have vertex indices {0,1,2} and {0,2,3}. You will need to add these two triangles to your mesh to create the two initial supertriangles. Be careful not to re-add corner vertices into your triangulation during the Bowyer-Watson insertion procedure.

You are free to design the classes, functions, etc. however you wish, but you must use the incircle predicate we used in class to determine if a point is inside a triangle's circumcircle. I would not recommend using half-edges for this assignment - our simple mesh representation using element indices and vertex coordinates will work well for this assignment. Try to implement the Bowyer-Watson algorithm without using the remove function for the array2d class (that I recently added).

Ultimately, you should be constructing a Mesh<Triangle> to represent the Delaunay triangulation. Note that there are some other files in the template (delaunay.h, delaunay.cpp) which you can use if you'd like to keep your implementation separate from main.cpp. The CMakeLists.txt file produces the project2 target which compiles main.cpp and delaunay.cpp. As in Project 1, you should copy the initial source files, CMakeLists.txt and the README.md from src/flux-base/projects/project2 into projects/project2. Remember to uncomment add_subdirectory(project2) in projects/CMakeLists.txt.

part 2: convert your Delaunay triangulation to a Voronoi diagram (2 points)

Please convert the Delaunay triangulation you computed in Part 1 to a Voronoi diagram. This will be very similar to what we did in class, so please revisit those notes. Recall how we omitted creating Voronoi cells that contained (Voronoi) vertices that lie out of some predefined limit (i.e. a circumcenter that is outside of [-limit,1+limit]). You should do the same here and set limit = 0.0.

part 3: smooth the vertices in the Delaunay triangulation (2 points)

Please implement the Lloyd relaxation scheme (recall the lecture and notes) for smoothing the vertices defining the Delaunay triangulation. You will need to compute the centroids of the Voronoi cells you computed in Part 2. You will also need to be careful with vertices whose Voronoi cells contain a vertex that is outside the domain. If you detect a Voronoi cell contains a vertex outside the domain, then leave the corresponding site (the Delaunay vertex) fixed (retain the original coordinates). Recall that on each iteration, the Delaunay vertices get re-assigned to the centroids of the Voronoi cells (except those that are fixed). You can use the average of the cell vertex coordinates to compute the centroid, if you want (or you can use the true centroid using this formula). Perform 10 iterations of Lloyd relaxation to smooth $n = 1000$ vertices.

part 4: make your Delaunay triangulation algorithm more efficient (1 point)

This part is challenging and will require a good amount of code (for only 1 point out of 20). If you attempt this portion, and only partially complete it, please make sure you can revert back to your implementation in Part 1. Here is how you can make your code more efficient:

  • Pick one of the corners. Sort the remaining vertices (to be inserted) by distance from this point.
  • Insert the points in order of increasing distance from the starting vertex.
  • After a point is inserted into the triangulation, keep track of one of the elements that was just created.
  • Start your search for broken triangles (recall our lecture on searching) from an element that was just created. As soon as you find one then continue searching it's neighbors (adding neighbors that violate the Delaunay property). Do not step into neighbors that do not violate the Delaunay property when searching for the remaining broken triangles (after you found the first one). Either BFS or DFS will work fine - DFS might be faster for the search for the first broken triangle, but they will be about the same when searching for the remaining broken triangles.
  • You can also keep track of all the triangles inserted on the last iteration. You can first check all of those triangles for the initial broken triangle and, if no triangle is found, proceed with the search as described in the previous step.
  • You will need to keep track of neighbors (you can use the Adjacency class) and update them as the triangulation is modified (this is perhaps the most challenging part).

part 5: report (1 point)

In the README.md file, please include the following:

  • Measure the time it takes to compute the Delaunay triangulation (once, without smoothing) for $n = 100$, $n = 10,000$ and $n = 100,000$ vertices. See the initial source for an example on how to measure time in C++ (there are other ways too, if you like). If you completed part 4, include the timing for $n = 1,000,000$ points as well.
  • Include pictures of your initial and final (after 10 iterations of smoothing) Delaunay triangluations and Voronoi diagrams for $n = 1000$. This means you will need to add these pictures to your repository (you can save them in projects/project2). For a picture named delaunay.png, you can include it in your README via ![](delaunay.png). Please see this documentation for more information.

Please leave your code in a compilable and runnable state. When typing make project2 your code should run 10 iterations of Lloyd relaxation.

submission

After completing the code and your README, please push to your GitLab repository. Then copy a link to your project commit to this Canvas assignment. All group members should submit this link in Canvas.