For https://old.reddit.com/r/golang/comments/hypnod/dynamically_layout_images_of_various_sizes/

glob.go

package sheet

import (
	"context"
	"fmt"
	"image"
	"os"
	"path/filepath"
	"runtime"

	"golang.org/x/sync/errgroup"
)

// XXX It's not clear if such a utility function makes sense in this package.

// Glob loads all the images with filenames matching pattern.
// The syntax of patterns is the same as in path/filepath.Match.
func Glob(pattern string) ([]image.Image, error) {
	filenames, err := filepath.Glob(pattern)
	if err != nil {
		return nil, err
	}
	images := make([]image.Image, len(filenames))
	// Normally file IO doesn't benifit from running concurrently,
	// however, image decoding can take enough CPU resources that
	// this appears to be worth it.
	N := runtime.GOMAXPROCS(0) // or runtime.NumCPU()
	work := make(chan int)
	group, ctx := errgroup.WithContext(context.Background())
	for i := 0; i < N; i++ {
		group.Go(func() error {
			for i := range work {
				f, err := os.Open(filenames[i])
				if err != nil {
					return err
				}
				images[i], _, err = image.Decode(f)
				_ = f.Close()
				if err != nil {
					return fmt.Errorf("%s: %w", filenames[i], err)
				}
			}
			return nil
		})
	}
loop:
	for i := range filenames {
		select {
		case work <- i:
		case <-ctx.Done():
			break loop
		}
	}
	close(work)
	if err = group.Wait(); err != nil {
		return nil, err
	}
	return images, nil
}

go.mod

module example.com/image/sheet

go 1.14

require (
	golang.org/x/image v0.0.0-20200618115811-c13761719519
	golang.org/x/sync v0.0.0-20200625203802-6e8e738ad208
)

partition.go

package sheet

import (
	"math"
)

// linearPartion partitions s into k or fewer subslices to minimize the
// maximum sum over all the ranges.
//
// The return value is a slice of subslices of s, that is, it shares the
// same backing array as s and care should be taking if modifying either
// after calling this.
//
// AKA Integer partition without rearrangement.
func linearPartition(s []float64, k int) [][]float64 {
	n := len(s)
	if k >= n {
		// Optimise the case where everything
		// is partitioned to single items.
		// Alternatively, we could just set k = n
		// and let the rest of the algorithm run.
		parts := make([][]float64, len(s))
		for i := range s {
			parts[i] = s[i : i+1 : i+1]
		}
		return parts
	}

	// See §8.5 in The Algorithm Design by Steven S. Skiena.
	//
	// The algorithm in the book uses two 2D 1-indexed arrays and a
	// single 1D array. We'll use 1D slices for all of these and
	// access `m` and `d` slices via `m[idx(i,j)]` to let the code
	// use 1-based indexes and to not have to make slice-of-slices.
	m := make([]float64, n*k)
	d := make([]int, n*k)
	p := make([]float64, n+1)
	idx := func(i, j int) int { return (i-1)*k + j - 1 }
	// m[idx(i,j)] is the minimum possible cost over
	//             all partitionings of s[:i] into j ranges
	//             where the cost of a partition is the largest
	//             sum of elements in one of its parts.
	//             1 <= i <= len(s)
	//             1 <= j <= k
	// d[idx(i,j)] is the divider position used to achieve m[idx(i,j)]
	// p[i]        is the sum of all s[:i]; 0 <= i <=len(s)

	for i := 1; i <= n; i++ {
		p[i] = p[i-1] + s[i-1]
		m[idx(i, 1)] = p[i]
	}
	for j := 1; j <= k; j++ {
		m[idx(1, j)] = s[0]
	}

	infinite := math.Inf(1)
	for i := 2; i <= n; i++ {
		for j := 2; j <= k; j++ {
			m[idx(i, j)] = infinite
			for x := 1; x <= i-1; x++ {
				cost := math.Max(m[idx(x, j-1)], p[i]-p[x])
				if m[idx(i, j)] > cost {
					m[idx(i, j)] = cost
					d[idx(i, j)] = x
				}
			}
		}
	}

	// We recurse through `d` to build the resulting partitions.
	parts := make([][]float64, 0, k)
	var recurse func([]float64, int)
	recurse = func(s []float64, k int) {
		//log.Printf("recurse(%v,%d) %d", s, k, len(s))
		if k == 1 {
			parts = append(parts, s)
			return
		}
		n := d[idx(len(s), k)]
		recurse(s[:n:n], k-1)
		parts = append(parts, s[n:])
		//log.Println("parts:", parts)
	}
	recurse(s[:n:n], k)
	return parts
}

partition_test.go

package sheet

import (
	"reflect"
	"testing"
)

func TestLinearPartition(t *testing.T) {
	cases := []struct {
		s     []float64
		sizes []int
	}{
		{[]float64{1, 2, 3, 4, 5, 6, 7, 8, 9}, []int{9}},
		{[]float64{1, 2, 3, 4, 5, 6, 7, 8, 9}, []int{1, 1, 1, 1, 1, 1, 1, 1, 1}},
		{[]float64{1, 1, 1, 1, 1, 1, 1, 1, 1}, []int{3, 3, 3}},
		{[]float64{1, 2, 3, 4, 5, 6, 7, 8, 9}, []int{5, 2, 2}},
	}
	want := make([][]float64, 0, 9)
	seq := make([]float64, 0, 9)
	for _, tc := range cases {
		// Build `want` and `k` from tc.sizes.
		want = want[:0]
		var i int
		for _, sz := range tc.sizes {
			want = append(want, tc.s[i:i+sz])
			i += sz
		}
		k := len(tc.sizes)
		if k == len(seq) {
			k += 42 // To check that any k >= len(seq) works.
		}

		// We make a copy of tc.s to detect if/when the underlying
		// array data gets modified.
		seq = seq[:0]
		for _, v := range tc.s {
			seq = append(seq, v)
		}

		got := linearPartition(seq, k)
		if !reflect.DeepEqual(got, want) {
			t.Errorf("linearPartition(%v,%d)\n\tgave: %v\n\twant: %v",
				tc.s, k, got, want,
			)
		}
		if !reflect.DeepEqual(seq, tc.s) {
			t.Errorf("linearPartition(%v,%d) modified the slice\n\t\t\t     now: %v",
				tc.s, k, seq,
			)
		}

		// Verify capacities of the returned slices were adjusted
		// so that any appends won't overwrite the original data.
		for i := range got {
			got[i] = append(got[i], 100+float64(i))
			got[i] = got[i][:len(got[i])-1]
		}
		if !reflect.DeepEqual(got, want) {
			t.Errorf("linearPartition(%v,%d) after appending\n\tgave: %v\n\twant: %v",
				tc.s, k, got, want,
			)
		}
	}
}

sheet.go

// Package sheet generates a contact sheet for a set of images.
// A contact sheet is a single fixed width image which is a mosaic of
// the supplied images *in order*. The algorithm attempts to split the
// supplied images into rows of equal height keeping the scalling factor
// of images as equal as possible.
package sheet

// XXX is the above description entirely correct? e.g. "keeping the scalling
// factor … equal"?

import (
	"image"
	"math"
	"runtime"
	"sync"

	"golang.org/x/image/draw"
)

// XXX set in tests for debugging
var logf = func(string, ...interface{}) {}

// New generates a new contact sheet of the supplied images.
// The resulting image has a width of `targetWidth` and a height
// sufficient to have as many image rows as required.
//
// `scale` determines the maximum size of individual images by
// setting the initial scalling; (0,1]. Images may be scalled
// down more than this to fit.
//
// `scaler` is the interpolation algorithm used to scale images.
// E.g. draw.NearestNeighbor, draw.ApproxBiLinear, draw.CatmullRom.
func New(images []image.Image, targetWidth int, scale float64, scaler draw.Scaler) image.Image {
	// Determine the scaled aspect ratios and scaled total width.
	ratios := make([]float64, len(images))
	var totalWidth int64
	for i, m := range images {
		b := m.Bounds()
		w, h := b.Dx(), b.Dy()
		sc := 1.0
		if w > targetWidth {
			sc = float64(targetWidth) / float64(w)
		}
		if sc > scale {
			sc = scale
		}
		w = int(math.Round(float64(w) * sc))
		h = int(math.Round(float64(h) * sc))
		logf("image%d: %d,%d → %d,%d\t%v", i, b.Dx(), b.Dy(), w, h, sc)
		ratios[i] = float64(w) / float64(h)
		totalWidth += int64(w)
	}
	rows := int(math.Round(float64(totalWidth) / float64(targetWidth)))
	logf("total scaled width: %d; rows: %d", totalWidth, rows)

	// Partition the images into rows (by partitioning the aspect ratios).
	var parts [][]float64
	if rows <= 1 {
		rows = 1
		parts = [][]float64{ratios}
	} else {
		parts = linearPartition(ratios, rows)
	}
	logf("partition(%v, %d): %v", ratios, rows, parts)

	// Build up the destination rectangles for each
	// image in the final contact sheet image.
	dstRs := make([]image.Rectangle, 0, len(images))
	yoff := 0
	for row, part := range parts {
		var ratioSum float64
		for _, ratio := range part {
			ratioSum += ratio
		}
		logf("row%d: ratioSum: %v", row, ratioSum)
		y := math.Round(float64(targetWidth) / ratioSum)
		h := int(y)
		xoff := 0
		for i, ratio := range part {
			var w int
			if i < len(part)-1 {
				w = int(math.Round(y * ratio))
			} else {
				// Last image in each row gets whatever
				// width remains (may not match the above
				// calculation due to rounding errors).
				w = targetWidth - xoff
			}
			logf("img %d,%d: %v,%v", row, i, w, h)
			dstRs = append(dstRs, image.Rect(
				xoff, yoff,
				xoff+w, yoff+h,
			))
			xoff += w
		}
		yoff += h
	}
	logf("dstRs: %v", dstRs)

	// Create the contact image and do the image resizing
	// in worker goroutines to use all the CPUs.
	dst := image.NewNRGBA(image.Rect(0, 0, targetWidth, yoff))
	N := runtime.GOMAXPROCS(0) // or runtime.NumCPU()
	work := make(chan int)
	var wg sync.WaitGroup
	wg.Add(N)
	for i := 0; i < N; i++ {
		go func() {
			defer wg.Done()
			for i := range work {
				scaler.Scale(dst, dstRs[i],
					images[i], images[i].Bounds(),
					draw.Src, nil,
				)
			}
		}()
	}
	for i := range dstRs {
		work <- i
	}
	close(work)
	wg.Wait()
	return dst
}

sheet_test.go

package sheet

import (
	"image/jpeg"
	"image/png"
	"os"
	"testing"
	"time"

	"golang.org/x/image/draw"
)

var _ = png.Decode

// XXX this isn't a "real" test, it just calls the New function with
// all the images in testdata and writes the result to a file for
// manual viewing.

func TestNew(t *testing.T) {
	if testing.Short() {
		t.Skip("skipping test in short mode.")
	}

	t.Log("reading images from testdata/*")
	start := time.Now()
	images, err := Glob("testdata/*")
	if err != nil {
		t.Fatal(err)
	}
	t.Log("using", len(images), "images loaded in", time.Since(start))

	const targetWidth = 800
	t.Log("making a contact sheet with a width of", targetWidth)
	const scale = 0.15
	scaler := draw.CatmullRom
	//logf = t.Logf
	//logf = log.Printf
	start = time.Now()
	m := New(images, targetWidth, scale, scaler)
	t.Log("took", time.Since(start))

	const filename = "test_new.jpg"
	f, err := os.Create(filename)
	if err != nil {
		t.Fatal(err)
	}
	if err = jpeg.Encode(f, m, nil); err != nil {
		t.Error("jpeg.Encode:", err)
	}
	if err = f.Close(); err != nil {
		t.Error("closing "+filename+":", err)
	}
	t.Log("Manually check/view the contact sheet written to " + filename + ".")
}