3

I have a collection of different sized rectangles that need to be placed on a 2D surface of a known dimension, with the condition that:

  • there is no overlap between the blocks,
  • the rectangles may not be rotated,
  • there is no area left blank (whole surface needs to be filled).

The rectangles are actually generated by breaking down the surface area, so they ought to fill up the area completely once you start putting everything together.

I figured there would be a dozen algorithms available for this problem, but the algorithms I find are more like best effort algorithms such as sprite generators that do not have the precondition that the whole area needs to be (can be...) filled -- which obviously is not necessary when building sprites, however, it is in my case.

I am a bit lost here, either this problem isn't as simple as I thought, or I am searching on wrong keywords.

Some topics I have found but do not fully suit my needs:

What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? (in my case, the area is preset)

How to arrange N rectangles to cover minimum area (in my case, minimum area must equal zero)

Is there any algorithm out there that may suit my needs?

Community
  • 1
  • 1
user3210499
  • 31
  • 2
  • Is it homework assignment? – ctrl-alt-delor Jan 18 '14 at 19:11
  • I was thinking of a recursive guessing algorithm: a brute force try every combination, until you succeed. – ctrl-alt-delor Jan 18 '14 at 19:13
  • This question appears to be off-topic because it is about maths homework. Stackoverflow is a site for professional software developers. – Ali Jan 18 '14 at 19:23
  • "this problem isn't as simple as I thought" --- that's exactly the case. There's no exact solution that works in acceptable time, and no hope to find one, ever. – n. m. could be an AI Jan 18 '14 at 19:29
  • Voting to close as a duplicate of [one of your linked questions](http://stackoverflow.com/questions/1213394/algorithm-needed-for-packing-rectangles-in-a-fairly-optimal-way), as I don't see any answers that could be added here adding much beyond those answers. One of the answers already mentions that problem is NP-complete and suggests brute force. – Bernhard Barker Jan 18 '14 at 19:39
  • look here: http://stackoverflow.com/a/21282418/2521214 It si very similar question. Brute force is too slow, but some simple heuristics and size/sort + area subdivision allways helps. I am very skeptic with the no space left condition for any solution ... – Spektre Jan 22 '14 at 12:17

1 Answers1

0

IMHO, the most natural solution is recursive. For the form of source area is not set. And after removing a rectangle from it, we have the same task, only with smaller area and -1 rectangle.

I would start from the edges, because there the possible variants are already limited. So, simply go by spiral, trying to put rectangles along the edge. If no rectangle fits, go back. That will be the simplest and not so slow raw force method.

Gangnus
  • 24,044
  • 16
  • 90
  • 149