Here is my problem:
- I have a bunch of circles that I need to display inside a canvas.
- There are an arbitrary number of circles, each with a predefined radius.
- The summed area of circles is always smaller than the area of the canvas.
I want to position the circles so that they take up the maximal space available inside the canvas, without touching each other.
Here is an example of what I am trying to achieve:
I am unsure about how to model the algorithm to solve this problem. Specifically, I don't understand which function(s) I need to maximize to find the maximum of the "global" inter-circle distance function. I am not even sure if that's the right criterion to maximize to achieve a "balanced" result.
My first "brute force" idea was the following:
- For each circle:
- Calculate the shortest distances between its border and each other circle's border.
- Sum all of these distances (call that X).
- Calculate the sum of all circles' X.
- Randomly change the distances between the circles, with the constraint that they can't touch each other.
- Redo 1-3 for a preset number of iterations and take the maximal value obtained at step (2).
However, this does not seem "elegant" from a mathematical perspective; I'm sure there is a better way to do it. Also, ideally, the results would be deterministic (i.e. same input always produce same output), which can't be accomplished with this method. Could anyone point me in the right direction?