Algorithm for organizing rectangles in a fixed rectangular container

Question

My problem is very similar to the 2D Knapsack problem, or cutting material with one exception ... the rectangles that fit into the container can be resized and cropped. No turning allowed.

The task is to make as few crops as possible and fill the entire container (without spaces).

Has anyone come across an algorithm that will do something similar. Any links, pseudo code is very appreciated.

The general question remained, but I would like to use it to organize photos on a fixed-size page.

Many thanks

Answer 1

While I am writing this, the exact criterion that we are trying to optimize has not been resolved. But whichever criterion is ultimately resolved, the following heuristic (i.e., generally suboptimal) approach may be useful:

Consider only a small number of "layouts" for combining a small number of rectangles into one large rectangle. Then, recursively consider ways to combine these new rectangles into even larger rectangles, using only as many layouts until only one rectangle remains.

This does not guarantee an optimal solution, because some subsets of photographs are limited to form subelements in the final solution. But it seems likely that he will give reasonable quality solutions.

For example, for the three rectangles A, B, and C, consider the following 4 layouts:

A B C ABC AB (ie A appears on the left) AC AA (ie A appears on the top) BC 

Crop will only happen in the first round, when we combine groups of 3 photos. For this step, each subset of 3 photos should be taken into account under each of the 4 layouts above, and the optimal scaling and cropping are determined for each, given that the resulting rectangle can be increased or decreased at later stages. (A good choice of the optimality criterion should have the property that the ideal amount of scaling and cropping for each of A, B, and C under a certain layout does not depend on how much the resulting rectangle scales, so this should not be a problem.)

Subsequent combinations of rounds will behave the same, but without cropping. For a complete solution, round 2 includes an attempt to combine all sets of three rectangles created in the first round, in which all 9 photos are different from each other, but after this approach will lead to exponential bloating. This is enough to save only the best designs for each subset of photos. Please note that it is important that each photo is displayed in at least one of the rectangles created by each round.

Answer 2

First, start with the determinant Best Fit Decreasing algorithm:

• Order large to small rectangles based on size

• Take the first rectangle and place it in the container if it fits

• Take the next rectangle and place it in the best remaining space in the container without cropping (if it fits into it). If there are several options, select the option that leaves the area on the left with the least number of sides. Repeat this step until the container is full or all rectangles are used.

• If the container is not full yet, go through the unused rectangles in the same order, but this time try cropping.

Now it will not be perfect. You may encounter a situation similar to the left 2 solutions in this image, where you can crop the element “without space”, even if it is not needed:

So, secondly, throw a metauretic algorithm on the result of the first, for example, a search in Taboo or simulated annealing. If you are looking for an open source library to do this for you, check out this one .

Answer 3

I'm not going to argue that this is optimal, but there are some ideas here that might make you experiment.

I will override the comment based problem. We are given the rectangles of the rectangle X and N of size t from size of different sizes. We want to completely cover the rectangle X with the rectangles N. We are allowed to resize images proportional to the original sizes. We want to minimize the area of ​​the area covered by N rectangles that also do not cover the area of ​​rectangle X.

Here is one idea:

• If we can find a package that is proportional to the original size, we can simply scale it up or down and fit the rectangle, and we are done
• Given some bin packing algorithm, do a binary search to find the minimum scaling constant for X so that we can pack all the rectangles in the cell.
• Expand and crop individual rectangles until the space is full.

Not sure how it will cost, but try something.