[Python] Is there an implementation of the geodesic voronoi diagram in a simple polygon usable...

As the title states, I am trying to find an implementation of the geodesic voronoi diagram in a simple polygon. Ideally it would be usable from Python. It is sometimes referred to as the shortest path voronoi diagram.

It is the voronoi diagram of points contained within a non-convex bounding polygon where the shortest paths determining the voronoi cells are constrained to be within the polygon. Note this is not the same as simply clipping a standard voronoi diagram with a bounding polygon, - the cells are generated within a 2D polygon.

This is a simple illustration of a standard voronoi diagram clipped to a bounding polygon:



And this is a simple illustration of the geodesic voronoi diaram generated within the polygon:



I have come across four papers that describe this and some algorithms to achieve it:

• Aronov, B. (1987). On the geodesic Voronoi diagram of point sites in a simple polygon.
• Guth, N. and Klingel, P. (2012). Demand Allocation in Water Distribution Network Modelling – A GIS-Based Approach Using Voronoi Diagrams with Constraints.
• Liu, C.-H. (2019). A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon.
• Oh, E. (2019). Optimal Algorithm for Geodesic Nearest-point Voronoi diagrams in Simple Polygons.

I have also found a video that describes it where the points are also moving within the polygon:

• Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Ideally any implementation would be usable from Python but any implementations at all would be appreciated to start with.

Many thanks.

Continue reading...