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:
Ideally any implementation would be usable from Python but any implementations at all would be appreciated to start with.
Many thanks.