
June 22nd, 2013, 11:25 AM
#1
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!

June 24th, 2013, 02:32 AM
#2
Re: packing rectangles into a container rectangle with minimum overlap
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

June 24th, 2013, 04:15 AM
#3
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 ...

June 24th, 2013, 07:54 AM
#4
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!

June 24th, 2013, 11:23 AM
#5
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 lineartime. 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 05: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

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
