layout algorithm for tightly-packed image thumbnails

3
votes

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:

1
algorithmthumbnailsheuristicspackingrectangles
I'm wondering if I need to create some kind of neural network, where each of the balance points becomes a weight on a node (Wikipedia: link). – stanhope
The problem becomes quite simple if you think about a single column of images. There's no packing, save perhaps two portrait images next to one another, just a single long line of images. When I introduce a second column, there are now only a few place each image can go (underneath 1, underneath 2, next to 1, next to 2). Maybe that's the most simple way to build up what may be a complex algorithm? – stanhope
Don't write explanations of your question in comments, edit your question. A lot of people on SO don't read comments, in the main they're not terrifically useful and a lot of us filter them out. – High Performance Mark
Thanks Mark, but if you read them you'll see they're not actually part of the question. They're comments on the question - ideas more than anything. I didn't want to confuse the question with my spurious ramblings about what a solution might look like, precisely because I know many people on SO don't read the comments. – stanhope
Stated like that, this question is very hard to answer because this is some kind of multi-objective optimization problem. Of yourse you can use all the knowledge which is available regarding 2d-packing and all the other stuff, but maybe you have to design some metric / cost-function / evaluation-function first: you need to decide, which optimization-criterion is how important (which is kind of a psychology or trial&error-driven task ). When you have this function , you can implement some mathematical-optimization algorithms OR work on heuristics which work well regarding your metric. – sascha

1 Answers

2
votes

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.