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:
Makes me realise that there really is not a simple answer to this problem
$\endgroup$ 34 Answers
$\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$ $\begingroup$If you have control over your paper size and dimensions, then you can find a solution to your problem here: 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$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$ $\begingroup$Check out my solution here:
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$
