I've experimented with other strategies, but I think this one is optimal.Īs for an exact diameter, I don't have one, but I know you can make them at least 1.00000235 cm in diameter (quite conservative-a better calculation is too messy for me right now, but probably you could get 1.00001 cm diameter). The M*N circles can be larger by a very very small amount. I did a calculation that was evidently wrong. The distance (d) between circles in the same row is about 0.05733373693Įach rows adds about 0.8559664362 to the height (h),Īnd this time there's also enough extra room left on the side to actually fit the even rows. MxN=9x7 I get a maximum diameter (2r) of 1.008234938Īnd it fits 8 rows of 8 circles (again one more than needed) I think there was still an error in my last result, « Last Edit: Jul 3 rd, 2003, 2:31am by towr » The diameter wasn't asked, but if you want it this should give enough information to find it, somehow.Īnd yes, incidentally it also fits one circle more. It's easy to calculate that there is actually space left at the top, and since 7 is smaller than 8 there is space in the length-direction as well. And there is also room left at the top, so that the circles can be bigger since they can expand in height, and length. If you take a length 8, height 6 box, you can put 7 layers of 7 (diameter 1) circles in it. And in my case I think it does, and I'm sure that's also the case in James' solution. Just because I don't know the diameter doesn't mean larger circles don't fit. « Last Edit: Jul 2 nd, 2003, 4:37pm by Leo Broukhis » What is the smallest value of M*N such that an M cm by N cm rectangle can contain more than M*N identical circles, each with diameter 1 cm. ĭoc, I'm addicted to advice! What should I do?Īs neither towr, nor James specified the diameter, I tend to believe that they were solving a different problem: Wikipedia, Google, Mathworld, Integer sequence DB « Last Edit: Jul 3 rd, 2003, 3:33am by towr » I think 8*6=48, but I'm not quite sure, since my numbers change every 10 minutes (had lots of errors in my method). Some people are average, some are just mean. « Last Edit: Jul 2 nd, 2003, 9:03am by Leo Broukhis » All circles must fit entirely within the rectangle at the same time, no circle may overlap any other circle.Ĩ4? And the diameter is 1.01036297108184508789. What is the smallest value of M*N such that an M cm by N cm rectangle can contain M*N identical circles, each with diameter greater than 1 cm? If M and N are integers, it is easy to fit M*N circles of 1 cm diameter into an M cm by N cm rectangle without the circles overlapping.
Topic: Fitting Circles In A Rectangle (Read 16254 times) Hard (Moderators: Grimbal, Eigenray, william wu, Icarus, ThudnBlunder, SMQ, towr)
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register « wu :: forums - Fitting Circles In A Rectangle » I have added a simple dichotomic search on top of it to guess the minimal surface (which yields the smallest bounding rectangle for a given aspect ratio).Wu :: forums - Fitting Circles In A Rectangle
(it simply tries to fit a bunch of circles into a given rectangle). The original algorithm does not produce the smallest rectangle to hold all the circles The algorithm simply starts with the four bounding circles and adds one circle at a time, using the greedy heuristic lambda parameter to pick the "best" location. This also simplifies the start condition greatly. The "corner" circles (as the algorithm calls them) are all computed as tangents to a pair of circles, thus eliminating the special circle+segment or segment+segment cases. They are computed to pass through the corners of the bounding box and converge toward the actual sides when the radius grows. The picture shows what the 4 bounding circles look like when the radius is decreased. Instead of segments defining the bounding box, I used circles with "infinite" radii, that can be considered a good approximation of lines: I used a trick to make the computation more regular. I tweaked it quite a bit, but I think it does basically the same thing. Here is a go at the implementation of your algorithm. This is the general pattern: function drawCircles() ) There's a much better way to do this - using Mitchell's Best Fit algorithm.
0 kommentar(er)
