Given a 2D space inhabited by circle shapes (grey), is there an easy way to find the largest empty circular area (blue)? I guess I have to look at space partioning, maybe quadtrees, but I'm curious as to whether there might be existing solutions, especially for circular shapes?
My idea (neither thought through or implemented, and computationally expensive):
- Divide the space into a grid, the finer, the more precise
- At every grid point, calculate D, the smallest distance to any of the neighbouring circles C_i (= distance to center of C_i - radius of C_i)
- Choose the grid point that maximizes D