GitHub - pvigier/MyGAL: MyGAL is a computational geometry algorithms library
MyGAL is a computational geometry algorithms library - pvigier/MyGAL
Fortune’s Algorithm: The Details
pvigier.github.ioThe last few weeks, I worked on an implementation of the Fortune’s algorithm in C++. This algorithm takes a set of 2D points and construct the Voronoi diagram of these points. If you wonder what is a Voronoi diagram, it looks like this: For each input point, which is called a site, we want to find the set of points which are nearer to this site than to any other site. These sets of points form cells as you can see on the image above. What is remarkable about the Fortune’s algorithm is that it constructs such diagrams in \(O(n\log n)\) time (which is optimal for an algorithm which uses comparisons) where \(n\) is the number of sites. I am writing this article because I find it very hard to implement this algorithm. Until now, it is surely the hardest algorithm I have ever implemented. Thus, I want to share with you the issues I faced and how I solved them. The code is, as usual, available on github and you will find all the references I used at the bottom of this article.