You are going to implement a program for calculating and visualizing the Voronoi Diagram of a set of points in 2D using the following two approaches:
Note that as Delaunay Triangulation is the dual of the Voronoi Diagram, computation of the Voronoi Diagram may involve calculating its dual Delaunay Triangulation first.
Please see the following reference by Aurenhammer, F., Klein, R., for details on the Randomized Incremental and Plane Sweep (Fortune's) Algorithms:
"Voronoi Diagrams and Delaunay Triangulations", Aurenhammer, F., Klein, R., in the Handbook of Discrete and Computational Geometry, J.E. Goodman, J. O'Rourke, and C. D. Toth (editors), 3rd edition, CRC Press, Boca Raton, FL, 2017.
Voronoi Diagrams and Delaunay Triangulations
Your program should generate a set of random points in two dimensions using various distributions (Gaussian, uniform, etc.) as input and calculate and visualize the 2D Voronoi Diagram as graphical output. The program should have a good user interface to specify the parameters, such as the number of points and distribution parameters. Your program should support zooming in/out and moving the view while displaying the 2D Voronoi Diagram. You may assign different colors to each Voronoi Cell for better visualization.
After creating the 2D Voronoi Diagram, your program should also support dynamic manipulation of the Voronoi Cells. Specifically, we should be able to move the points to alter the Voronoi Cells. We should also be able to insert new points to create a new Voronoi Cell, affecting the neighboring cells. These two operations should operate on the existing Voronoi Diagram instead of building it from scratch.
You will visualize the steps of Fortune's Algorithm (we should see the visual result of the current Voronoi Diagram as the algorithm proceeds). You will also visualize the steps of the Randomized Incremental algorithm during the Delaunay triangulation construction. See the animated gif on the following page for an example step-by-step visualization of Fortune's algorithm:
You will test your program for arbitrary point sets in 2D and report the performance of your implementation, comparing the two approaches. You must use a reasonable number of test cases, e.g., starting with 100 and up to 1,000,000.
Please also see the project description for the CS 274: Computational Geometry course at UC Berkeley by Prof. Dr. Jonathan Shewchuk at
Delaunay Triangulation Project
which also contains various test data sets that you can use.