Making a big image from many images using php GD library

Hello everyone,
I want to work on some kind of image generator, which as input will receive an unknown amount of images with unknown widths & heights (can be square, high or wide) and will combine them together to one image using php GD library.
What I plan to do is hard and would probably require some good php skills and math.
I want to build it in a way which the resulting image will have no extra space, like the images inputted will cover all of it (with about 5px space between each image) and ofcourse resize the given images in proportions as needed.
As a first step, I would like only some ideas or advice on how you would achieve such a thing (not talking about code yet), how do you suggest i should start and what techniques / methods you know which would be really helpful in this case, i guiss mathematical stuff would go in really handy.
I already got some start, lets say we decide that we work on a 800x800 canvas, we would calculate its area which is 800*800 = 640000 then we iterate all input images and reduce their size until their total area is equal/less than the area of our canvas, only problem would be to position them correctly on the canvas so they will fill it all properly.

Made an example in photoshop to make the idea more clear:

The compositing of images with GD is pretty easy and there are tons of tutorials out there for that. The hard part is the math for finding the best fit for the images. I suggest you look at the article as a starting place.

you should also consider imagemagick because it has great capabilities