Algorithm to organise rectangles in the fixed rect

问题:

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

回答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.

回答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.

回答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.