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:
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.
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.
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.
Add the four combinations.
Choose the first child,
Try to add next rectangle, adding every combination as before
If there are no room for the rectangle go back, and test next child of this parent.
Repeat that until there is no more rectangles to add.
|show 3 more comments|