Given a rectangle of size $x$, $y$, I would like to fit the maximum circles in it. The second rule is that my circles come in 3 different radii $r_1$, $r_2$, $r_3$, and I need the maximum number of triplets $(r_1, r_2, r_3)$ filling my rectangle.
If that can help, the circle sizes are $r_1=9cm$, $r_2=12cm$, $r_3=16cm$, and the rectangle vary in size. An example would be 130$\times$170 cm.
For a bit of context, I need to cut the maximum number of circle triplets out of a rectangle fabric. I don't want to waste any unnecessary fabric.
After some research I've realised that it is a very hard problem to solve, but I'd be happy with any algorithm, code, or formula giving me a rather good filling, even if it is not the optimal solution.
Here is my research so far :
- Packing identical circles in a square : I could simplify my problem by packing squares in a rectangle... https://en.wikipedia.org/wiki/Circle_packing_in_a_square
- I think the Circle packing theorem does not apply as I have a rectangle instead of large circle, different radii
- An other option is to do an approximation with square packing in rectangle...
Thanks a lot to those who'll help me with this :)
Here's a way to fit $11$ of each radius: