What is the algorithm for automatic layout of multiple images into one?

Question

Algorithms

There are a bunch of small images of different sizes and with different aspect ratios. It is necessary from them, as from a mosaic, to make one large image with the given dimensions.
You need a program for this. Tell me, are there such programs (language is not important)? Interested in the source, not the utility itself.
Or, can someone tell me what this process is called? I don't even know what to ask Google.
I would be grateful for any recommendations.

Answer 1

As part of imagemagik there is a wonderful montage utility that allows you to combine images in any way,
examples of use here
Despite the seeming simplicity, you can generate anything by simply combining montage calls according to the principle - the output of one is used as the input of another.
To generate composite images, I use my script on top of montage that runs shell commands, or if the task is one-time, then I generate a shell script where inside everything looks like this
montage ./images/0.jpg[x${HALF_HEIGHT}] ./images/1 .jpg[x${HALF_HEIGHT}] ./images/2.jpg[x${HALF_HEIGHT}] -geometry "${THRD_WIDTH}x<" -gravity center -crop ${THRD_WIDTH}x${HALF_HEIGHT}+0+ 0 -geometry "+${BORDER}+${BORDER}" ./out/4.html

Answer 2

If you are interested in the algorithmic aspect, then:
1) This is a 2-dimension bin packing problem.
2) In the general case, the computational complexity is high, so they solve it with heuristics
3) It won’t be possible to solve it ideally - there will be “gaps”
4) In general, choose some heuristic (I can offer a couple), and then “pull” the pictures a little so that around them were uniform fields, and the unmarked area was not very conspicuous.