Find distribution of 4 points in a given shape, so that areas of Voronoi Diagram have the same and biggest size

Question

I have given a random shape, wherein I want to place 4 (or any other number) dots. The dots should be distributed, so that all areas of their Voronoi-Diagram have the same size of area and have the biggest size of area possible. I want to find an algorithm that I can implement in Python. Any ideas how to start?

The algorithm should find the best distribution of a swarm of drones that is discovering a room.

Answer 1

A natural approach is to pick some arbitrary starting points and apply the Lloyd algorithm repeatedly moving the sites to their Voronoi centers. It isn't guaranteed to get the optimal configuration but generally gives a much nice (and nearly locally optimal) configuration in a few steps.

In practice the ugliest part of the code is restricting the Voronoi cells to the polygonal domain. See discussion here and here among other duplicates of this question.

Here is an alternative that maybe easier to implement quickly. Rasterize your polygonal domain, computing finite set of points inside the polygon. Now run k-means clustering which is just the discrete variant of Lloyd's method (and also in scipy) to find your locations. This way, you avoid the effort of trimming infinite Voronoi cells and only have to rely on a geometric inside-outside test for the input polygon to do your rasterization. The result has a clear accuracy-performance trade-off: the finer you discretize the domain, the longer it will take. But in practice, the vast majority of the benefit (getting a reasonably balanced partition) comes with a coarse approximation and just a few clustering iterations.

Finally, implementing things is a lot more complex if you need to use geodesic distances that don't allow sites to see directly around non-corners of the domain. (For example, see Figure 2a here.)