Distribute images evenly to columns in gallery

Question

Brief Explanation

I am currently building a gallery that has three columns, each column contains images all of which have the same width, but can vary in height.

The images for the columns are gathered from a directory and placed into an array using the PHP glob() function. This is the easy part...

An example of what the gallery looks like:

The Issue

As these images are being loaded and placed into the columns dynamically, there is a chance that the columns may differ in height hugely.

For instance, if two portrait photos were placed in column 1, and two landscape photos were placed in column 2, the columns would be very uneven like so:

It is extremely unlikely that the columns will ever match in height, but I would like them to be as close as possible with the given images and therefore would like to form an algorithm that will look at the images retrieved and place them in the columns to return three columns that are as close in height as they can be.

So, for example, the script would correct the above problem by re-sorting the images and placing them like so:

I am capable of writing this if I have the correct algorithm, I just cannot think of the best steps to do this. Can anyone suggest any steps?

Possible Solution

One of the methods I thought of (I think there will be better ways as I think this is flawed):

1. Add up the height of all of the images combined and divide by the number of columns (3). This will give us the height to aim for
2. Distribute the images to the column array and when it exceeds the height of the column, overflow onto the next column.
3. Place any left over images into the first column, then second column etc...

Thanks in advance

Answer 1

You can try somethig like this. Create array:

$totalHeight = array(
 1 => 0, //Column 1
 2 => 0, //Column 2
 3 => 0 //Column 3
);

Add image to column with the smallest $totalHeigth and increase height of that column with added image height.

So if in some loop you have array like this:

$totalHeight = array(
 1 => 2500, //Column 1
 2 => 1950, //Column 2
 3 => 2450 //Column 3
);

you will know that image need to be added in column 2.

Answer 2

I'd suggest something along the following:

1. Order your images into an array from tallest to shortest (assuming your width is constant)
2. Add image to first column array
3. Add images to next column array until total height is equal or greater than previous column array
4. Repeat steps 2 & 3 until all images are used (you could even alternate populating the columns in ascending and descending order to help even things out)
5. Shuffle image arrays to make gridlines appear random before adding images to columns
6. Adjust vertical margins on images for the shorter columns to match total height of tallest column (a vertical justified align, of sorts)

Hope this helps!