Menu
I am looking for some pointers to algorithms that should allow to tile with no overlap different size rectangles.
Given a set of different sized rectangles, tile them on an area of size H x W with no overlap. The objective would be to maximize the space used or conversely - minimize area of gaps. If there is not enough space, proceed on the second area of the same size and so on.
It is assumed that each rectangle's width and height are smaller than respective dimensions of the tiling area. Rectangles are not rotated or otherwise transformed - i.e. their sides are either horizontal or vertical.
I am not looking for finished code, just curious what approaches/algorithms are the best to use to solve this problem.
704
To tile a rectangle in this sense is to divide it up into smaller rectangles or squares. Each of the smaller rectangles or squares is called a tile. The side length of the smaller rectangle or square is called the size of the tile, and the number of different sizes of tiles determines the order of the tiling.
Most simple is to use a kd-tree to subdivide the tree into vertical and horizontal euklidian 2d space. Then you can pack a rectangle into one of the created space and recursively subdivide the tree. There is a Jquery treemap plugin example available online. The jquery plugin masonry can do the same but it's more like a 1d bin-packing solver. 2d bin-packing is much more complicated and can also mean to rotate rectangles. Here is an example for packing lightmaps: http://www.blackpawn.com/texts/lightmaps/default.html.
57
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
