Tiles of various sizes of rectangles

Question

I am looking for some pointers to algorithms that should allow tiles without overlapping different size rectangles.

Given a set of rectangles of different sizes, apply them to an area of ​​size H x W without overlapping. The goal would be to maximize the space used, or vice versa - to minimize the area of ​​gaps. If there is not enough space, go to the second area of ​​the same size, etc.

It is assumed that each width and height of the rectangle is smaller than the corresponding dimensions of the tile area. Rectangles do not rotate or otherwise transform, i.e. Their sides are horizontal or vertical.

I'm not looking for ready-made code, just wondering which approaches / algorithms are best used to solve this problem.

Answer 1

The simplest is to use a kd tree to split the tree into vertical and horizontal Euclidean 2d space. Then you can pack the rectangle into one of the created space and split the tree recursively. An online example of the plugin is available. JQuery masonry can do the same, but it looks more like a solution for sorting in 1d. 2d packing in a hopper is much more complicated and may also mean turning the rectangles. Here is an example of lightmap packaging: http://www.blackpawn.com/texts/lightmaps/default.html .

Answer 2

I have one idea that can go in the right direction. The idea is to track the ratio of the area of ​​the tile to the white area in the bounding box.

input: unordered set of input rectangles output: filled area

• Define an empty bounding box
• Select two rectangles A_i and B_j from the input set whose bounding block B contains the minimum ratio of the void area
• Update the bounding box with two optimal cells
• Place the bounding box in the corner, say (1,1)
• Repeat until a window appears
  • Take a new flag from the set, for example, an updated bounding box that has a minimum space.
  • Growth restriction in the horizontal or vertical direction, if the width or height of the bounding box exceeds the width of the output area
  • If it is not possible to add a new flag, go to the new area H x W and restart the algorithm, otherwise update the bounding box

There are still some points to determine - what is the best way to determine the location of the bounding box? How to impose restrictions on limiting restrictions? How to efficiently find the best bounding box?