Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Limiting the placement of covering rectangle with smaller rectangles algorithm?

  1. May 22, 2012 #1
    I'm looking for a 'covering rectangle with smaller rectangles' algorithm with the unique feature of being able to exclude some possible center points of rectangles. Basically, limiting the possible areas the smaller rectangles can be placed, while still having the algorithm try to solve for filling up the entire big rectangle with smaller rectangles (of a fixed size). Obviously this will sometimes result in the algorithm not succeeding, no possible solutions.

    Has anyone seen anything like this or know how it would be developed?

    somethings to keep in mind: 1. This problem can be optimally solved by simply placing the fixed size rectangle at every point that is allowed. This of course is too many rectangles, and I'm trying to accomplish this with the minimum amount of rectangles possible. the minimum amount can usually be determined by dividing the area of the big rectangle by the area of the smaller rectangle.

    Example: a big rectangle with an area of 200. small rectangle with an area of 5. The smallest possible amount of rectangles to cover the area inside the big rectangle is 40 (200/5=40). If you limit the places you can put the rectangles, this number might grow, and the spacing might become uneven. I'm essentially asking for a way to solve this problem.

    2.Coverage areas are not boxes, packing algorithms are not covering algorithms. coverage areas can overlap. box packing algorithms don't overlap.
  2. jcsd
  3. May 22, 2012 #2


    User Avatar
    Gold Member

    are you using similar rectangles little to big ratio? This would solve a lot.
  4. May 22, 2012 #3
    you mean if i have a big rectangle that is 60 length, 30 width, then i would use 60% length, 30% width for smaller rectangles? yes, but I wonder if adding areas that you can't put centerpoints of rectangles will divide the room into more rectangles and change this 'optimum' spacing?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook