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

Answer 1

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.