Organizing images based on size.

[Troy Lundin]

My program utilizes various images of different sizes. I want to organize these images so that they all fit into a predetermined space without resizing any of them. They need to be organized in such a way to use as much of the predetermined space as possible.

I guess it would be like organizing photos in one of those old photo albums (with the translucent, mildly adhesive, peel-back plastic sheet that held the photos in place) so that you could get as many photos on a page as possible.

Or you could think of it sort of like Tetris? Except all the pieces are rectangles.

How would I do this?

I assume I would use a recursive function to loop through all the images to find out if they fit or not, then returning the best outcome?

I tried searching for code samples but searching for Organizing Images or Organizing Shapes gives less than desirable results.

Thanks.

[skywola]

I would get the area of the rectangle you want to fit them into. Each time you add an image, subtract its area from the total area of the page. Start with the smallest images first, that compacts them the most, as best I know. That may not be the most optimum method for all I know, but that is how I would do it.

[boops boops]

Hi Troy,

The term for what you are seeking is a 2D Nesting Algorithm. These are used by software for planning the most efficient use of sheet materials. I suspect that such software uses some rather sophisticated mathematics and logic.

Meanwhile, skywola's approach might work if you intend to place the maximum number of images regardless of size. But if your aim is to fill the target area as efficiently as possible, I think it would be better to place the larger images first. The reason is that you need small images for filling up the leftover spaces between the larger ones, so it would be a mistake to use up all the small images first.

In pseudocode terms, I would tackle the process as follows, starting with a generic collection of images.

1. Make a function for comparing two images, which returns True if the first image is larger in area than the second image

2. Sort the collection of images using the function from step 1 as a comparer, largest first.

3. Convert the collection to a Stack.

4. Recursively:

    a. pop the first image from the stack.
 
    b. scan the whole target area from top-left to bottom-right for an empty rectangle large enough to contain the popped image.

    c. if no suitable rectangle is found and the stack is empty, exit.

    d. if no suitable rectangle is found and the stack is not empty, go back to step 4a.

    e. if a large enough free rectangle is found, place the popped image at top left in the rectangle.

    f. if the stack is not empty, go back to step 4a, else exit.

This assumes you only want to fill one target area. If you intend to fill multiple areas as in the picture album analogy, you could transfer any unused images from steps 4c and 4d above to a new collection, and repeat the routine until there are no images left.

Edit: Whether the above method produces the "best" result depends partly on the mix of image sizes. In some cases, selecting the smaller images first might yield a more efficient packing; or it might be best to start with medium-sized images. In other words, you could repeat the above routine using different sort criteria and see which produces the best result for a given mix of images.

BB

[jmcilhinney]

As you may have gathered by now, what you want to do is not trivial. Search for "backpack problem" and you may find some interesting information about the problem and possible solutions.

[boops boops]

I just noticed an article in the CodeProject which offers "a fast algorithm to pack a series of rectangles of varying widths and heights into a single enclosing rectangle, with no overlap and in a way that minimizes the amount of wasted space in the enclosing rectangle". It appears to seek the smallest rectangle that will enclose a given set of rectangles. That's not quite the same as OP asks but I think it must be worth looking at.

Here's the link: Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites

BB

[boops boops]

[sorry, accidental double posting]