An algorithm for finding the maximum area ratio of several circles in a rectangle

just thought of an algorithm question
knowing the length and width of a rectangle and the number of circles, what is the largest proportion of the area of the circle in it?
for example, a rectangle of 10 to 10, if the number of circles is one, then the diameter of the circle should be 10. If the number of circles is 2, then the diameter of the two circles may be 10, the other is the corner of the large circle, or both diameters are 5 or other, but the area ratio of the inner circle is the highest, so the diameter of the two circles should be unique, the same three circles and four circles. Or if the aspect ratio of the rectangle is 3:2, and so on, what should the circle look like inside?

function

//h:w:count:
function fn(h,w,count) {
            
}
Mar.18,2022

draw a circle first with the maximum radius as far as possible.

< H1 > there is an error in the following algorithm. Ignore < / H1 >

draw a circle inside each rectangle

  1. there must be four corner spaces where you can continue to draw circles
  2. there may also be length-width remaining space of a rectangle to continue to draw a circle (if it is a square, this bar does not exist)

the idea is that after each circle is drawn, according to the current length and width , calculate the above two possible length, width, radius , put into priority queue , and then take out the maximum radius value to continue to draw the circle until count is 0

.

use the following picture to illustrate the idea of the solution to this problem

clipboard.png
Picture from: http://mathworld.wolfram.com/.

it is obvious that every time you fill a circle, the radius should be as strong > as possible and directly take the maximum value that can be filled .
the subject considers two circles, make one of them smaller, and then leave space for the other to achieve a larger total area . In fact, does not exist
of course it is quite complicated to write code. All kinds of irrational number operations.
if the precision requirement is not high, using the method of translation, constantly offsetting the center point of the circle should be a more scientific idea

.

Update 2018.12.29:
look at figure 1 and figure 2 below. It's so obvious. (aheb) 2 = (A) 2 + (B) 2 + 2AB.
(Abib) 2 > (A) 2 + (B) 2, it must be that the larger the radius, the bigger the , that's all.

think backwards:
Let one large circle reduce the radius of X, it is impossible to increase the radius of another small circle > X .
therefore, there is no question of how the two circles are arranged and positioned.
is always filled in with the largest circle, which is the optimal solution .

Menu