Generates a collage given a directory containing only images

collage.py

#!/usr/bin/env python3

import glob
from PIL import Image
from random import shuffle
from sys import argv


# The maximum size an individual image can be
MAXSIZE = (640,480)

# the number of pixels padding between two images
OFFSET = 16

# the aspect ratio of the image
RATIO = 4.0 / 3.0


# load in all of the images
images = []
imagefilelist = list(glob.glob((argv[1]+"/" if len(argv) > 1 else "") + "*.*"))
#imagefilelist = list(glob.glob("images/*.*"))

for imagefile in imagefilelist:
    image = Image.open(imagefile)
    image.thumbnail(MAXSIZE)
    images.append(image)

# sort the images from largest to smallest
# this will cause the largest images to be placed first
images.sort(key=lambda image: image.size[0] * image.size[1], reverse=True)

# A rectange with an upper-left and bottom-right point
class Rectangle:
    def __init__(self, x1, y1, x2, y2, image=None):
        self.x1 = x1
        self.x2 = x2
        self.y1 = y1
        self.y2 = y2
        self.width = x2 - x1
        self.height = y2 - y1
        self.area = self.width * self.height
        self.ratio = self.width / self.height
        self.image = image
    def __eq__(self, other):
        return (self.x1 == other.x1 and self.y1 == other.y1 and
                self.x2 == other.x2 and self.y2 == other.y2)
    def __hash__(self):
        return (self.x1, self.y1, self.x2, self.y2).__hash__()
    def __repr__(self):
        return ("(" + str(self.x1) + " " + str(self.y1) + " " +
                str(self.x2) + " " + str(self.y2) + ")")
    # whether this rectangle intersects with (an) other rectangle(s)
    def intersects(self, other):
        if type(other) == Rectangle:
            return (self.x1 < other.x2 and self.x2 > other.x1 and
                    self.y1 < other.y2 and self.y2 > other.y1)
        for r in other:
            if self.intersects(r):
                return True
        return False
    # returns a new rectangle that encloses this and another rectangle
    def grow(self, other):
        if type(other) != Rectangle:
            raise Exception()
        return Rectangle(self.x1 if self.x1 < other.x1 else other.x1,
                         self.y1 if self.y1 < other.y1 else other.y1,
                         self.x2 if self.x2 > other.x2 else other.x2,
                         self.y2 if self.y2 > other.y2 else other.y2)
    # shift a rectangle some number of coordinates
    def shift(self, coords):
        self.x1 += coords[0]
        self.y1 += coords[1]
        self.x2 += coords[0]
        self.y2 += coords[1]


# a list of rectangles (associated with an image) to place in the collage
rectangles = []

# The overall size of the collage, enclosing all rectangles
overall = None

# The "inflection points" in the collage
# These are points located near the corners or intersections of rectangles
# New rectangle corners may be placed at inflection points
inflections = set([])

# Assign each image to a properly placed rectangle
for image in images:
    # Handle the very first rectangle
    if not len(rectangles):
        rectangles.append(Rectangle(0,0, image.size[0], image.size[1], image))
        overall = Rectangle(0, 0, image.size[0], image.size[1])
        # place the four corners in the inflection set
        # the corners are offset to allow for the possible gap between images
        inflections.update([(overall.x1-OFFSET, overall.y1-OFFSET),
                            (overall.x2+OFFSET, overall.y1-OFFSET),
                            (overall.x1-OFFSET, overall.y2+OFFSET),
                            (overall.x2+OFFSET, overall.y2+OFFSET)])
        continue
    # build a set of possible points at which the image rectangle can be placed
    options = set([])
    for point in inflections:
        # each inflection point gets associated with the four image corners
        options.update([(point[0],point[1]),
                        (point[0]-image.size[0],point[1]),
                        (point[0],point[1]-image.size[1]),
                        (point[0]-image.size[0],point[1]-image.size[1])])
    # build a list of possible rectangles that will contain the image
    potentials = []
    for option in options:
        # for each possible location, ignore rectangles that intersect others
        testrect = Rectangle(option[0], option[1],
                             option[0]+image.size[0], option[1]+image.size[1])
        if testrect.intersects(rectangles):
            continue
        potentials.append(testrect)
    # potential rectangle order is arbitrary
    # the potential rectangles are shuffled to provide different layouts
    shuffle(potentials)
    # determine which rectangle(s) will cause the image to grow the least
    smallestgrow = None
    bestrect = None
    for pot in potentials:
        newgrow = overall.grow(pot)
        if (smallestgrow is None) or (newgrow.width + newgrow.height < smallestgrow.width + smallestgrow.height):
            # ignore rects that extend the image past the ratio
            if newgrow.ratio > RATIO:
                smallestgrow = newgrow
                bestrect = pot
    # associate the current image with the rectangle
    bestrect.image = image
    # store the rectangle and update the collage
    rectangles.append(bestrect)
    overall = smallestgrow
    inflections.update([(bestrect.x1-OFFSET, bestrect.y1-OFFSET),
                        (bestrect.x2+OFFSET, bestrect.y1-OFFSET),
                        (bestrect.x1-OFFSET, bestrect.y2+OFFSET),
                        (bestrect.x2+OFFSET, bestrect.y2+OFFSET)])

# shift all the rectangles so none of them have negative positions
minx = rectangles[0].x1
miny = rectangles[0].y1
for rectangle in rectangles:
    if minx > rectangle.x1:
        minx = rectangle.x1
    if miny > rectangle.y1:
        miny = rectangle.y1
minx = -minx
miny = -miny
for rectangle in rectangles:
    rectangle.shift((minx, miny))
overall.shift((minx, miny))

# output the final image
final = Image.new("RGB", (overall.x2,overall.y2), (128,128,128))
for rectangle in rectangles:
    final.paste(rectangle.image, (rectangle.x1, rectangle.y1))
final.save("/tmp/out.png")