layout algorithm for tightly-packed image thumbnails

Question

I'm working on an image gallery and I'd like to tightly pack the image thumbnails. The thumbnails are:

• different aspect ratios
• available at the same source resolution (longest edge 256 pixels)

I'd like to come up with an optimal solution (will probably have to be a heuristic) that allowed me to balance:

• the padding between each thumbnail (preferably constant)
• the consistency of thumbnail size (preferably all the same size)
• the amount of each image that gets cropped for the display (preferably none)
• the proximity of images consistent with their sort order (preferably sort-neighbours will be near one another in the grid)

I think this is a variant of the rectangle packing problem.

I've found some good references: Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites

But I wanted to check with the experts to see if anyone knows of:

• any established algorithms that are available publicly,
• any open source libraries that implement them or
• any other mathematical references or guidance that might help me produce something as good as: http://labs.tineye.com/multicolr#colors=4b669e;weights=100;

Answer 1

I have come up with something like this (now also with code on github) https://mendrik.github.io/diorama/

I should add that the order will be random, and the sizes try to be uniform, but for me it was more important to fill out the entire space rather than keep the sizes consistent. You can resize the browser window to see how it works.

If your height is not fixed, there are several other options, mostly knapsack or partitioning algorithms. 2d bin backing will leave you with gaps or wont find solutions that always fit all images.

my algorithm has almost no cropping and fits always all images into the given space, provided there are enough combinations to do so. the less images the more cropping obviously.