# What is an efficient packing algorithm for packing rectangles into a polygon?

I need to put as many rectangle of same size as possible inside a polygon. The algorithm can put rectangles in different orientation(angle). But they cannot overlap. This is image is an example of the end result:

-
Any constraints on the shape of the polygon? It's also a rectangle in your illustration, which is a relatively simple case. – aaaaaaaaaaaa Apr 9 '12 at 12:11
If that's a rectangle, then perhaps google for 2D bin packing might help. If not, your problem is not NP complete for sure.. – teodron Apr 9 '12 at 13:34
This is asking for backtracking for sure. – kaoD Apr 9 '12 at 13:48
@eBusiness, The Polygon can be in any shape but the rectangle is in fixed size. – user960567 Apr 9 '12 at 18:04
@teodron, The Polygon can be in any shape but the rectangle is in a fixed size. – user960567 Apr 9 '12 at 18:05

This is called the Pallet Loading Problem. Solving it is actually pretty hard, and we don’t know of an exact solution that always works in reasonable time. And sometimes the solution is not intuitive at all, see for instance:

Here is a comprehensive list of existing algorithms (Recursive Five-block Algorithm, L-Algorithm, Recursive Partitioning Algorithm) with full source code. The same authors have a web application that lets you enter your own data and see the result.

-

In this sample you can find an algorithm to pack small textures into a big texture, that is quite similar to your matter... and maybe a good start to solve it.

http://create.msdn.com/en-US/education/catalog/sample/sprite_sheet

EDIT:

You can use a tree, where the leafs have empty regions, and the rest of nodes have the rectangles. You can iterate deeply to get a solution.

## Algoritm

At first pass, the node contains the empty region. There are four combinations for adding the rectangle, by the orientation ( Vertical, Horizontal) and the way that region will be divided.

Choose the first child,