Perfectly fill a rectangle with a list of smaller rectangles

4
votes

I want to take a bounding rectangle and a list of other rectangles (x, y, width, height) that may overlap each other or the bounds and move/resize them to fit perfectly inside of the bounds, leaving no spaces or overlaps.

I've searched Google, Stack Exchange and other resources and can't find a name for this algorithm let alone an implementation. Is there a standard method of implementing this?

Here's what I hope the algorithm would do: Reconciling rectangles

Additional thoughts:

  1. I'm using Javascript, but a reference implementation in any language would help
  2. Where overlaps occur, any method of resizing the rectangles is fine but I would probably choose the mid point of the overlap
  3. Final rectangles may be any size, including 0 in one dimension, as long as they all fit within the bounds
  4. My data has the bounds and rectangles normalized to a 0-1 range, where 0,0 is the top left corner of the bounds and 1,1 is the bottom right corner
2
javascriptalgorithmrectangles
To clarify point 4: the data for the image would be [ [0,0], [0,1], [0,2], [1,0 ] ] or would the last one be [1,1] since it's the second row and second column? There is no size defined since you can resize the blocks right? But if point 4 is about the size then the first would be [0,0] to [1,0.5] ? And that would mean you can re order everything according to nearest size? – HMR
Sorry for the lack of clarity! What I mean by that is that the top left corner of the bounds would be represented as { x: 0.0, y: 0.0 } and the bottom right corner would be represented as { x: 1.0, y: 1.0 }. Each of the contained rectangles is expressed relative to the size of the bounds, e.g. a rectangle filling the top right quarter would be { x: 0.5, y: 0.0, width: 0.5, height: 0.5 }. The largest blue rectangle in th unsorted example image might be expressed as { x: -0.1, y: -0.1, w: 0.5, h: 1.0 } – Tristan Shelton
So that would mean the script should re order the inner rectangles as best as possible to fit it's desired size? Because you say you can resize it the data indicating the size of the triangles is only a suggestion right? – HMR
Yes, that's correct. The input data is a suggestion of the layout but edges may be moved freely as long as the shapes remain rectangles. – Tristan Shelton
So you can only move the edges and not the order? – HMR

2 Answers

1
votes

A renown problem which is related to your problem is "Pallet Loading" problem. In general, the complexity class of this problem is not known and is an open problem. You can read more about the problem and its variation in this article.

0
votes

This seems like problem of finding layout structure of given rectangles.

General layout of rectangles can be of any kind, like in his problem, which is probably hard to solve. I would attack this problem by defining simple layout model which can be used to transform input data into it, and after that use that layout data to fill input boundary rectangle.

The simplest layout is with dividing a box into two boxes by stacking them horizontally or vertically. In your example boundary rectangle is divided into two horizontally stacked boxes. Right one is divided into vertically stacked boxes, and top one of them is divided horizontally.

Main step for creation of layout for given set of rectangles is to find horizontal or vertical line that divides the best set of rectangles. After that same method is applied on two sets of rectangles produces by splitting.

After layout structure is created, it is easy to find size and position of rectangles by recursively merging boxes bottom to top to calculate relative size. Than propagate position and size by going top to bottom.

Improvement to this layout is layout that allows stacking more boxes horizontally or vertically. Result is the same, but this approach is probably faster since less iterations of finding of splitting line is needed.