21
$\begingroup$

I've just came back from my Mathematics of Packing and Shipping lecture, and I've run into a problem I've been trying to figure out.

Let's say I have a rectangle of length $l$ and width $w$.

Is there a simple equation that can be used to show me how many circles of radius $r$ can be packed into the rectangle, in the optimal way? So that no circles overlap. ($r$ is less than both $l$ and $w$)

I'm rather in the dark as to what the optimum method of packing circles together in the least amount of space is, for a given shape.

An equation with a non-integer output is useful to me as long as the truncated (rounded down) value is the true answer.

(I'm not that interested in how the circles would be packed, as I am going to go into business and only want to know how much I can demand from the packers I hire to pack my product)

$\endgroup$
  • 3
    $\begingroup$ I had an answer before, but I looked into it a bit more and my answer was incorrect so I removed it. This link may be of help: en.wikipedia.org/wiki/Circle_packing_in_a_square $\endgroup$ – Cam Jul 26 '10 at 6:30
  • 1
    $\begingroup$ @Cam: Looks like there's no optimal solution yet. Maybe you could just put this comment as an answer. $\endgroup$ – kennytm Jul 26 '10 at 6:34
  • $\begingroup$ Might be a good question to work out how to answer problems which actually aren't solved yet in advanced maths. (if there is not an optimal solution yet) $\endgroup$ – Justin L. Jul 26 '10 at 7:01
  • $\begingroup$ @KennyTM: Sure. $\endgroup$ – Cam Jul 26 '10 at 12:31
  • 2
    $\begingroup$ @NeilRoy That is an upper bound but it assumes that the circles pack basically perfectly in the rectangle, which is obviously asymptotically false as there must be space between the circles. $\endgroup$ – Solomonoff's Secret Jan 5 '16 at 18:29
7
$\begingroup$

I had an answer before, but I looked into it a bit more and my answer was incorrect so I removed it. This link may be of interest: Circle Packing in a Square (wikipedia)

It was suggested by KennyTM that there may not be an optimal solution yet to this problem in general. Further digging into this has shown me that this is probably correct. Check out this page: Circle Packing - Best Known Packings. As you can see, solutions up to only 30 circles have been found and proven optimal. (Other higher numbers of circles have been proven optimal, but 31 hasn't)

Note that although problem defined on the wikipedia page and the other link is superficially different than the question asked here, the same fundamental question is being asked, which is "what is the most efficient way to pack circles in a square/rectangle container?".

...And it seems the answer is "we don't really know" :)

$\endgroup$
0
$\begingroup$

Nesting circles into rectangular sheets

Optimal nesting and practical limits: When considering different nesting options while searching for an optimal nesting solution, it is desirable to find the solution quickly. This begs the question: how do I know a solution is optimal? The answer is not always obvious.

An automated nesting search is part of the answer, which can explore a number of options quickly, automatically and report the results. Finding the maximum number of parts in a full sheet or finding the smallest sized sheet required for a given number of parts. It should be noted that circles have subtle nuances in packing efficiencies. It can be an advantage to have a working knowledge of these expected packing efficiencies of typical cases. (See efficiency graph)

Oddly in some cases the optimal packing for circles is irregular packing which is counter-intuitive. Transferring these irregular types of packing placements into other software is difficult. Hence, generally a trade-off is made by selecting the most optimal of the more regular circle packing patterns.

Rectangular, Hexagonal and Worst case packing

There is no set formula for calculating the maximum number of discs from a rectangular sheet. The efficiency of disc packing depends on the arrangement of discs in the material. The Rectangular disc packing array (with zero spacing) is 78.5% (does not suffer from the low efficiency of edge effects) The Hexagonal disc packing array (with zero spacing) is 90.6% Worst case disc packing is (2 discs inside a square) 53.8%

Circle packing software

The above disc packing software calculates and compares eight different packing methods and highlights the most efficient solutions. Each variation uses a different nesting pattern. Note that no single method will give the optimum yield for nesting every size disc into every sized sheet. The optimum method varies depending on the disc sizes and sheet dimensions. Note that transferring these optimal arrangements of the x,y positions of each disc to the profiling software can be challenging.

Different nesting options examined by the software

Different nesting options examined by the software when searching for optimal quantity per sheet.

A graph of nesting efficiency vs disc diameter

A graph of nesting efficiency (%) vs disc diameter (mm) nested into a rectangular sheet 2400x1200 with 5mm spacing. The blue line is the actual efficiency, and other colours theoretical. The maximum value of the results of 8 different circle packing methods is taken. The graph’s non-linear nature indicates a simple formula for the maximum number of discs is unlikely. Note also the low packing efficiency of discs smaller than 100mm diameter due to inter-part spacing being a greater percentage of the area and efficiency peaking at 78.5%.

During tabulation the packing result was noted together with the method of circle packing. Further to these automatically generated results, if the efficiency of that data point appeared low compared to nearby points on the graph, a manual nest of the discs was attempted and any better yields tabulated and noted as Irregular packing. Using these results in a practical sense helps halt the search with confidence if adding another disc (N+1) would require an efficiency that, by the graph, is not possible. Maximum packing efficiencies for discs in rectangles is continually being researched and improved. For the current ultimate best nest for discs for irregular packing refer to the on-line link: http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html

McErlean, P. (2018) "The CAD/CNC Programming Handbook: 2D Material Optimization and Tips for Laser, Plasma and Oxy profile cutting"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.