Fortune’s Algorithm for Calculating the Voronoi Diagram of Polylines, Polygons, and Functions

The Voronoi diagram is part of the field of computational geometry, just like the Delaunay triangulation, the convex hull, the bounding rectangle, etc. It is used in many areas, including mathematical morphology, cartography, and volume reconstruction. The Voronoi diagram divides the space between several sites, thus forming Voronoi cells. Sites can be points, segments, objects, etc. Several algorithms allow the calculation of the Voronoi diagram. Among these algorithms, there is the Steven Fortune algorithm. We will see in this paper the application of the algorithm on polylines, polygons, and mathematical functions, we study the Voronoi cell shapes for the different objects, and we have highlighted the particular cases. In this work, the algorithm is implemented in Lazarus (based on the Pascal language), and we were able to test it on datasets of different types and geographical maps. We compared the results with another algorithm (Voropix), and the results were the same.