Algorithm to organize rectangles in the fixed rectangular container

Question

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

The challenge is to make as little crops as possible and fill entire container (no gaps whatsoever).

Has anyone encountered an algorithm that would do something similar. Any links, pseudo code much appreciated.

Kept the question generic, but I'd like to apply it to organise photos on a fixed size page.

Many thanks

Rossie

This has been asked before #1213894 – Solomonsolon

yeah I came across that one, but my rects can change size – Rossie

I realise that I want to do something similar to what flipboard does with images, so it might be out of my league quora.com/How-does-flipboard-decide-where-to-crop-images – Rossie

So resizing of an image can be only done proportionally, right? I can't resize an 8x10 to 8x8 without cropping? – Dufour

I think the resizing actually makes it harder than knapsack problem. If you could solve this optimally with 0 resizing it could be used to solve knapsack. – Millsaps

@spintheblack - you don't need to keep image proportions, but I'd like to reduce number of crop operations required, for example 8x10 shouldn't become 1x10, but 6x10 is satisfactory – Rossie

@Rossie - We need to better define cropping, then. This is an optimization problem and we need to know what we're optimizing. Amount of area cropped? Number of pictures cropped? I asked originally because if we can resize the images arbitrarily, we simply divide the rectangle in to n parts and resize the images along that grid. – Dufour

@spintheblack - good thinking, ideal optimisation would be amount of area cropped per image. – Rossie

@beklip: Do you mean the average amount of area cropped per image? That's not a very good criterion, since e.g. if you have 2 10x10 photos to fit in an 10x12 rectangle, it doesn't distinguish between shrinking both to 10x6, and shrinking one to 10x2 and the other to 10x10 (which I presume should be considered much worse). Also how should cropping be weighed vs. resizing? Before trying to minimise anything, we need a function that takes a candidate solution and gives a single number. – Neglect

@j_random_hacker: I think maybe... minimize the maximum of percentage of area cropped in a given picture? I think that approaches fairness, though it doesnt capture the problem of some pictures probably getting reduced to narrow strips, which doesn't seem great. – Nevertheless

@Null Set: I like that approach. I know the OP said that we don't need to keep original aspect ratios, but if we did add that constraint, then I think your criterion would be ideal. – Neglect

@Neglect I took that to mean an aspect ratio change was in fact a crop, possibly after a resize. "you don't need to keep image proportions" because we have cropping capability. Otherwise the question makes no sense. We can always minimize the "cropping" by not doing any and just "resizing" to fit, and cropping is the only thing he wanted to minimize. – Nevertheless

@Null Set: You're right, I see now that we are free to resize (while respecting aspect ratio) as much as we want. This formulation strikes me as likely to cause problems though as it doesn't prevent scaling images to extremely small sizes. OP, surely you want to penalise resizing in some way as well? – Neglect

Answer 1

At the time I write this, the exact criterion we are trying to optimise hasn't been settled on. But whatever criterion is eventually decided on, the following heuristic (i.e. generally suboptimal) approach might be useful:

Consider only a small number of "layouts" for combining a small number of rectangles into a single larger rectangle. Then recursively look at ways of combining these new rectangles into even larger rectangles, using just the same few layouts, until only a single rectangle remains.

This doesn't guarantee an optimal solution, because some subsets of photos are constrained to form subrectangles within the final solution. But it seems likely that it will give reasonable-quality solutions.

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

A
B
C

ABC

AB   (i.e. A appears on the left)
AC

AA   (i.e. A appears on the top)
BC

Cropping will only occur in the first round, when we are combining groups of 3 photos. For this step, every subset of 3 photos should be considered under each of the 4 layouts above, and the optimal scaling and cropping determined for each, bearing in mind that the resulting rectangle could be scaled up or down by later steps. (A good choice of optimality criterion should have the property that the ideal amount of scaling and cropping for each of A, B and C under a particular layout is not affected by how much the resulting rectangle is scaled, so this shouldn't be a problem.)

Subsequent combining rounds will behave similarly, but without considering any cropping. For a full solution, round 2 would involve trying to combine all sets of 3 rectangles produced by round 1 in which all 9 photos are distinct, however following this approach will lead to an exponential blowup. It should suffice to keep just the best few arrangements for each subset of photos. Note that it's important that each photo appear in at least 1 of the rectangles produced by each round.

Neglect

this one is the most appealing solution, given my programming skills and amount of effort required. thank you for your input. all I need is to define enough layouts (I like the fact I have some control on the end result), to include combinations of landscape and portrait regions to minimise required cropping – Rossie

Answer 2

First start with a determinsitic Best Fit Decreasing algorithm:

• Order the rectangles from big to small 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 spot in the container without cropping (if it fits into it). If there a multiple options, take the option that leaves has a left over area with the least amount of sides. Repeat this step until the container is full or all rectangles have been used.

• If the container isn't full yet, go through the not-used rectangles in the same order, but this time try cropping.

Now, that won't be perfect. You can get into a situation similar to the left 2 solutions in this image, where you'd crop the "no space" item even though it's not needed:

So, secondly, throw a metaheuristic algorithm on the result of the first, such as Tabu search or Simulated annealing. If you're looking for an open source library to do that for you, take a look at this one.

Ambience

Answer 3

I'm not going to claim this is optimal at all, but here's some ideas that might get you experimenting.

I'll redefine the problem based on the comments. We are given an v by t sized rectangle X and N rectangles of various sizes. We want to completely cover rectangle X with the N rectangles. We are allowed to resize the images proportional to original dimensions. We wish to minimize the amount of area covered by the N rectangles that also do not cover an area of the rectangle X.

Here's one idea:

• If we can find a packing 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, perform a binary search to find the minimum scaling constant for X such that we can pack all rectangles in the bin.
• Expand and crop individual rectangles until the space is filled

Not sure how it would fare, but something to try.

Dufour