packing rectangles into a container rectangle with minimum overlap
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: packing rectangles into a container rectangle with minimum overlap

1. Junior Member
Join Date
Jun 2013
Posts
2

## packing rectangles into a container rectangle with minimum overlap

Hi!
I have a case where I have a container rectangle of fixed dimensions, say WXH and I want to fill it up with two kinds of rectangles, with dimensions say w1Xh1 and w2Xh2,we can assume that w1,w2,h1 and h2 are integers, and these filling rectangles can be rotated by 90 degrees only. I want to fill up the container rectangle completely, for which there will be overlaps between rectangles. So, I have two objectives, first to determine minimum overlap area possible, and second determining the tiling placement(s) of rectangles that results in this minimum overlap area. How do I approach this problem? I have gone through the standard packing problems, and I guess none of them fulfill my requirement. Thanks a lot!

2. ## Re: packing rectangles into a container rectangle with minimum overlap

3. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: packing rectangles into a container rectangle with minimum overlap

clearly, the solution is far from being unique, so, do you need an exact solution or just an heuristic ? in the latter case, a simple method could be to start from a uniform pseudorandom distribution of allowed rectangles filling the "container" surface completely; then, you could apply some relaxation algorithm to minimize overlap and the number of rectangles with the constraint of not creating holes in the tiling. In order to do this, you could use physical inspired methods ( for example, in molecular dynamics so called montecarlo methods or annealing methods are used to "relax" molecular structure to minimize energy while retaining molecular bounds; in your case, this would tantamount to randomly move or delete rectangles with a probability proportional to the overlap change, or to model rectangles as physical bodies with a repulsion force related to the overlapped area etc ... ) or genetic algorithms or ...

4. Junior Member
Join Date
Jun 2013
Posts
2

## Re: packing rectangles into a container rectangle with minimum overlap

Originally Posted by superbonzo
clearly, the solution is far from being unique, so, do you need an exact solution or just an heuristic ? in the latter case, a simple method could be to start from a uniform pseudorandom distribution of allowed rectangles filling the "container" surface completely; then, you could apply some relaxation algorithm to minimize overlap and the number of rectangles with the constraint of not creating holes in the tiling. In order to do this, you could use physical inspired methods ( for example, in molecular dynamics so called montecarlo methods or annealing methods are used to "relax" molecular structure to minimize energy while retaining molecular bounds; in your case, this would tantamount to randomly move or delete rectangles with a probability proportional to the overlap change, or to model rectangles as physical bodies with a repulsion force related to the overlapped area etc ... ) or genetic algorithms or ...
Hi superbonzo!
Thanks for the reply. I am in search of an heuristic algo for the purpose, could you please elaborate the approach using modelling the rectangles as physical bodies repelling each other? Thanks a lot!

5. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: packing rectangles into a container rectangle with minimum overlap

Originally Posted by stonu
could you please elaborate the approach using modelling the rectangles as physical bodies repelling each other?
ok, but to keep things simple, the first algorithm I'd try is:

1) generate rectangles until the "container" is completely covered, the shape and position of the rectangles are choosen pseudorandomly, rectangle centers are picked uniformly in the container box

2) for each rectangle exceeding the container area, move it inside the container the obvious way

3) then, for each rectangle X, if X is fully covered by other rectangles then remove it. Otherwise, for each other rectangle Y compute a displacement vector whose magnitude is proportional to the overlap area of X and Y and direction is such as to maximize the overlap decrease; then, sum up all displacements over X and clamp the result in order to forbid the rectangle to go outside the container and to forbid any rectangle corner to jump through any other rectangle boundary ( this is to avoid the formation of holes ); then, update X's position by adding the clamped displacement vector.

4) repeat 3) until the system stabilizes or some overlap threshold is reached

note that you can use a spatial tree or a verlet list data structure to make the algorithm linear-time. Moreover, the ability of mixing two intermidiate solutions the obvious way suggests a trivial genetic extension ... that said, it all depends on the esthetic effect you want to ultimately achieve ...
Last edited by superbonzo; June 24th, 2013 at 04:00 PM. Reason: typo

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•