Computing the cut locus, Voronoi diagram, and signed distance function of polygons

This paper presents a new method for the computation of the generalized Voronoi diagram of planar polygons. First, we show that the vertices of the cut locus can be computed efficiently. This is achieved by enumerating the tripoints of the polygon, a superset of the cut locus vertices. This is the set of all points that are of equal distance to three distinct topological entities. Then our algorithm identifies and connects the appropriate tripoints to form the cut locus vertex connectivity graph, where edges define linear or parabolic boundary segments between the Voronoi regions, resulting in the generalized Voronoi diagram. Our proposed method is validated on complex polygon soups. We apply the algorithm to represent the exact signed distance function of the polygon by augmenting the Voronoi regions with linear and radial functions, calculating the cut locus both inside and outside. • Efficient algorithm for computing generalized Voronoi diagrams for polygon soups. • Our method constructs tripoints by embedding the polygon in a Delaunay triangulation. • Algorithm correctness is argued with a number of geometric theorems and a conjecture. • Exact algorithm utilizes closed-form geometric formulas and graph transformations. • Our robust Matlab implementation performs in O(n log(n)) time for most inputs.