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

Thread: packing rectangles into a container rectangle with minimum overlap

  1. #1
    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. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    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.

  3. #3
    Join Date
    Oct 2008
    Posts
    1,133

    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. #4
    Join Date
    Jun 2013
    Posts
    2

    Re: packing rectangles into a container rectangle with minimum overlap

    Quote Originally Posted by superbonzo View Post
    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. #5
    Join Date
    Oct 2008
    Posts
    1,133

    Re: packing rectangles into a container rectangle with minimum overlap

    Quote Originally Posted by stonu View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center