13
$\begingroup$

If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for.

I have a rectangular space.

I also have a number of rectangle objects.

I want to find an algorithm that will try to fit all the objects in the rectangle and if this is not possible I want to know that so that I can show an error message.

This is for a computer program that I am working with to place images on a sheet of paper so that I can print them. The idea is to waste as little paper as possible.

Edit: Found this one which was a very interesting read: http://cgi.csc.liv.ac.uk/~epa/surveyhtml.html

Makes me realise that there really is not a simple answer to this problem

$\endgroup$
3
  • 1
    $\begingroup$ You can also check the Stack Overflow and Computer Science forums, since they deal with algorithms a lot more than here. $\endgroup$
    – user2566092
    Aug 8, 2014 at 19:47
  • 2
    $\begingroup$ Are you restricted to axially aligned rectangles? See for example the optimal packing of 10 squares: en.wikipedia.org/wiki/File:10_kvadratoj_en_kvadrato.svg $\endgroup$
    – DanielV
    Jan 7, 2017 at 5:05
  • $\begingroup$ It sounds like you are allowing multiple sheets of paper to be used, so that "waste as little paper as possible" has the sense of minimizing the number of pages printed. In any case there is a broad literature on such two-dimensional rectangular packing problems, as the survey you found illustrates. For small problems it is possible to minimize the number of sheets by combinatorial search. Without narrowing the problem statement there is little that can be said. $\endgroup$
    – hardmath
    Jul 19, 2017 at 5:20

4 Answers 4

Reset to default
2
$\begingroup$

I have bad news.

Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $S\setminus A$ such that $\sum_{x\in A} x=\sum_{x\in S\setminus A}$. It is $NP$-Complete (see, for instance, [N]).

When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).

References

[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.

[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.

$\endgroup$
1
$\begingroup$

If you have control over your paper size and dimensions, then you can find a solution to your problem here: http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu where they figure out the minimum area rectangle that can be packed with all the smaller rectangles (i.e. minimum wasted space). If you don't have control over the size/dimensions of your paper, then you can still run that algorithm and if the minimum area surrounding rectangle has area greater than your paper area, you can report that there is no solution for your paper size. Similarly, if the minimum area rectangle found fits inside your paper size, then you can use the solution found.

Probably an even better strategy is to run that algorithm with one additional smaller rectangle to pack, which is very very thin and has length equal to the larger of your two paper dimensions. Then the minimum area surrounding rectangle will probably have one side length equal to that large paper dimension, and you can just test to see if the other dimension of the minimum area surrounding rectangle is smaller or larger than your smaller paper dimension when you remove the extra thin rectangle from the packing.

$\endgroup$
3
  • $\begingroup$ Problem with the first idea is that it would really not give me optimal use of the paper and I guess I will get a lot of unused paper? The "Better strategy" sounds interesting but isn't it also here a big chance that I will get a very long rectangle that is not going to fit the paper? $\endgroup$
    – www.jensolsson.se
    Aug 9, 2014 at 8:22
  • $\begingroup$ @www.jensolsson.se The first part of the strategy in the first par is guaranteed to minimize the amount of unused paper, but it would require you to change your paper dimensions in order to achieve that optimality. And you're right, the second part of the first suggestion in the first par, as well as the suggestion in the second par are not guaranteed to always work, but if they do work then they're guaranteed to give you the right answer. I suspect that if people can find a minimum area surrounding rectangle then they can also solve your packing problem, so maybe do a literature search $\endgroup$
    – user2566092
    Aug 9, 2014 at 17:46
  • $\begingroup$ Well, that is the problem, I really cannot change the paper size. $\endgroup$
    – www.jensolsson.se
    Aug 12, 2014 at 6:58
1
$\begingroup$

Check out my solution here: https://github.com/avaneev/areafitter

It's a finished algorithm for practical uses, but it can be also used to answer your question: if the algorithm produces more than 1 output rectangle/image then your source set of rectangle does not fit a single bigger output rectangle.

$\endgroup$
0
+50
$\begingroup$

The proposed task is a two-dimensional version of the “knapsack problem”, so it requires a “greedy” selector algorithm that uses some sorting criteria.

You can offer, for example, the following sorting criteria: 1) total area (use for the upper left corner of the area) 2) the largest linear size; 3) the ratio of the larger side to the smaller (more elongated rectangles should be placed close to the edges of the area).

The number of objects placed is small, so the issues of theoretical optimality should not be major.

Good luck!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .