1
$\begingroup$

Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as many circles of area $A$ into the rectangle as possible. All the shapes trying to be packed in a given instance are identical, we also assume we are living in 2D.

What would be the general way to approach this problem? Can it be done with a program or is this a mathematical question?

$\endgroup$
2
$\begingroup$

As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete.

Skiena Section 17.9 reports:

Fortunately, relatively simple heuristics tend to work well on most bin-packing problems.

The same source provides the following heuristic recommendation:

Analytical and empirical results suggest that first-fit decreasing is the best heuristic. Sort the objects in decreasing order of size, so that the biggest object is first and the smallest last. Insert each object one by one into the first bin that has room for it. If no bin has room, we must start another bin. In the case of one-dimensional bin packing, this can never require more than $22\%$ more bins than necessary and usually does much better. First-fit decreasing has an intuitive appeal to it, for we pack the bulky objects first and hope that little objects can fill up the cracks.

First-fit decreasing is easily implemented in $O(n \ \text{lg} n + bn)$ time, where $b \leq min(n,m)$ is the number of bins actually used. Simply do a linear sweep through the bins on each insertion. A faster $O(n \ \text{lg} n)$ implementation is possible by using a binary tree to keep track of the space remaining in each bin. We can fiddle with the insertion order in such a scheme to deal with problem-specific constraints.

I recommend reading the original material in its entirety.

$\endgroup$
1
$\begingroup$

The problem for shapes of general form is in the class of NP-Hard, so there is nos efficient algorithm to solve this problem. Bin packing is a well known class of problems.

The approach will depend on your intentions:

  • Need a complete algorithm, i.e. an algorithm that compute the correct solution for the problem but can only compute small instances of your problem.
  • Need a fast approximation algorithm, i.e an algorithm that compute a "good" solution for large instances but not necessarily the optimal. I have seen very nice results using meta heuristics to solve this.

Almost every code I have seen so far works with not any kind of shapes but small sub classes such as polygons and circles.

$\endgroup$
  • $\begingroup$ A good approximation would definitely be good. What is the algorithm? $\endgroup$ – wjmccann Dec 7 '17 at 0:43

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.