This code sample demonstrates how to compute a Laguerre-Voronoi diagram (also known as power diagram) in 2d.
Power diagrams have a wonderful property : they decompose the union of (overlapping) circles into clipped circles that don't overlap. The cells have a simple geometry, just straight lines.
It works as following
- The circles centers are considered as points associated with a positive weight : the circle's radius
- Transform the points (called here lifting the points) from 2d to 3d.
- Compute the convex hull of the lifted points
- The lower enveloppe of the convex hull gives us the power triangulation
- The power diagram is the dual of the power triangulation.
The complexity of this algorithm is O(n log(n)), with most of the heavy lifting done by the convex hull routine.
To run this sample, you will need
- Python 3.8 or above
- Numpy
- Scipy
- Matplotlib, 2.0.2 or above