Rotating binpacker in Python.

binpack.py

import sys
import math

EDGE_NONE	= 0
EDGE_TOP	= 1
EDGE_BOTTOM	= 2
EDGE_LEFT	= 3
EDGE_RIGHT	= 4

def next_pow2(value):
	pv = 1
	while (pv < value):
		pv *= 2
	return pv

class Quad:
	def __init__(
		self,
		x, y,
		width, height
	):
		self.x1 = x
		self.y1 = y
		self.x2 = x + width
		self.y2 = y + height

	def intersects(
		self,
		q
	):
		return not (
			self.x2 < q.x1 or
			self.x1 > q.x2 or
			self.y2 < q.y1 or
			self.y1 > q.y2
		)

	def edge_match(
		self, q2
	):
		q1 = self
		if   (q1.x1 == q2.x1 and q1.x2 == q2.x2 and q1.y1 == q2.y2):
			return EDGE_TOP
		elif (q1.x1 == q2.x1 and q1.x2 == q2.x2 and q1.y2 == q2.y1):
			return EDGE_BOTTOM
		elif (q1.y1 == q2.y1 and q1.y2 == q2.y2 and q1.x1 == q2.x2): # q1.y2 == q2.y1
			return EDGE_LEFT
		elif (q1.y1 == q2.y1 and q1.y2 == q2.y2 and q1.x2 == q2.x1): # q1.y2 == q2.y1
			return EDGE_RIGHT
		return EDGE_NONE

	def __repr__(self):
		return \
		("%s("
			"%d,%d, %d,%d"
		")") % (
			type(self).__name__,
			self.x1, self.y1, self.x2, self.y2
		)

class Entry:
	def __init__(
		self,
		width, height
	):
		self.width = width
		self.height = height
		self.longest_edge = 0
		self.area = 0

		self.placed = False
		self.rotated = False
		self.x = 0
		self.y = 0

	def set_size(
		self,
		width, height
	):
		self.width = width
		self.height = height
		self.longest_edge = max(self.width, self.height)
		self.area = self.width * self.height

	def place(
		self,
		x, y,
		rotated
	):
		self.placed = True
		self.rotated = rotated
		self.x = x ; self.y = y

	def __repr__(self):
		return \
		("%s("
			"size: (%d, %d), longest_edge: %d, area: %d, "
			"placed: %s, rotated: %s, position: (%d, %d)"
		")") % (
			type(self).__name__,
			self.width, self.height, self.longest_edge, self.area,
			self.placed, self.rotated, self.x, self.y
		)


class Slot:
	def __init__(
		self,
		x, y,
		width, height
	):
		self.x = x
		self.y = y
		self.width = width
		self.height = height

	def get_quad(self):
		return Quad(
			self.x, self.y,
			self.width, self.height
		)

	# tuple(bool fits, int edge_count)
	def fits(
		self,
		width, height
	):
		ec = 0
		if width == self.width:
			ec += 1
			if height == self.height:
				ec += 1
		elif width == self.height:
			ec += 1
			if height == self.width:
				ec += 1
		elif height == self.width:
			ec += 1
		elif height == self.height:
			ec += 1

		if (width <= self.width and height <= self.height):
			return (True, ec)
		elif (height <= self.width and width <= self.height):
			return (True, ec)
		else:
			return (False, ec)

	def merge(
		self,
		slot
	):
		q1 = self.get_quad()
		q2 = slot.get_quad()
		q1.x2 += 1 ; q1.y2 += 1
		q2.x2 += 1 ; q2.y2 += 1

		edge = q1.edge_match(q2)
		if edge is EDGE_TOP:
			self.x = slot.x
			self.height += slot.height
		elif edge is EDGE_BOTTOM:
			self.height += slot.height
		elif edge is EDGE_LEFT:
			self.x = slot.x
			self.width += slot.width
		elif edge is EDGE_RIGHT:
			self.width += slot.width
		else:
			return False
		return True

	def __repr__(self):
		return \
		("%s("
			"position: (%d, %d), size: (%d, %d)"
		")") % (
			type(self).__name__,
			self.x, self.y, self.width, self.height
		)


class Packer:
	def __init__(
		self,
		border = 0,
		force_pow2 = False
	):
		self.border = border
		self.force_pow2 = force_pow2

		self.entries = None
		self.total_area = 0
		self.unused_area = 0
		self.longest_edge = 0
		self.result_width = self.result_height = 0
		self.free_slots = None

	def pack(
		self,
		entries
	):
		assert (
			entries is not None and
			len(entries) > 0
		)
		self.entries = entries

		for e in self.entries:
			e.set_size(
				e.width + self.border,
				e.height + self.border
			)

		self.total_area = sum(e.area for e in self.entries)
		self.unused_area = self.total_area
		self.longest_edge = max(e.longest_edge for e in self.entries)

		self.result_width = (
			max(
				math.floor(math.sqrt(self.total_area)),
				self.longest_edge
			)
		)
		self.result_height = (
			self.longest_edge * (
				(self.total_area / (self.longest_edge ** 2))
			))

		#print((
		#	"binpack.Packer: total_area: %d, longest_edge: %d, "
		#	"result_size: (%d, %d)"
		#) % (
		#	self.total_area, self.longest_edge,
		#	self.result_width, self.result_height
		#))

		self.free_slots = [Slot(0,0, self.result_width, self.result_height)]

		for _ in range(len(self.entries)):
			self._place()
			while (self._merge_slots()):
				continue

		self._finish()

		#print((
		#	"binpack.Packer: (%d, %d)"
		#) % (
		#	self.result_width, self.result_height
		#))

	def _place(self):
		lentry = None
		for e in self.entries:
			if e.placed:
				continue
			elif lentry is None:
				lentry = e
				continue

			if e.longest_edge > lentry.longest_edge:
				lentry = e
			elif (
				e.longest_edge == lentry.longest_edge and
				e.area > lentry.area
			):
				lentry = e

		least_x = least_y = sys.maxsize
		edge_count = 0
		best_fit = None
		for slot in self.free_slots:
			fit, fit_ec = slot.fits(lentry.width, lentry.height)
			if not fit:
				continue
			if fit_ec == 2:
				best_fit = slot
				edge_count = fit_ec
				break

			if slot.y < least_y:
				least_x = slot.x
				least_y = slot.y
				best_fit = slot
				edge_count = fit_ec
			elif (slot.y == least_y and slot.x < least_x):
				least_x = slot.x
				best_fit = slot
				edge_count = fit_ec

		# should best_fit ever be None?
		assert best_fit is not None
		self._place_entry(
			best_fit, lentry, edge_count
		)

	def _place_entry(
		self,
		slot,
		entry,
		edge_count
	):
		rotated = False
		width = entry.width
		height = entry.height

		# crop slot and append new slot
		if edge_count == 0:
			if entry.longest_edge <= slot.width:
				if height > width:
					width, height = height, width
					rotated = True
				entry.place(slot.x, slot.y, rotated)
				self.free_slots.append(Slot(
					slot.x, slot.y + height,
					slot.width, slot.height - height
				))
				slot.x += width
				slot.width -= width
				slot.height = height

			else:
				assert entry.longest_edge <= slot.height
				if height < width:
					width, height = height, width
					rotated = True
				entry.place(slot.x, slot.y, rotated)
				self.free_slots.append(Slot(
					slot.x, slot.y + height,
					slot.width, slot.height - height
				))
				slot.x += width
				slot.width -= width
				slot.height = height

		# crop slot
		elif edge_count == 1:
			if entry.width == slot.width:
				entry.place(slot.x, slot.y, False)
				slot.y += entry.height
				slot.height -= entry.height
			elif entry.height == slot.height:
				entry.place(slot.x, slot.y, False)
				slot.x += entry.width
				slot.width -= entry.width

			elif entry.width == slot.height:
				entry.place(slot.x, slot.y, True)
				slot.x += entry.height
				slot.width -= entry.height
			elif entry.height == slot.width:
				entry.place(slot.x, slot.y, True)
				slot.y += entry.width
				slot.height -= entry.width

		# slot == entry
		elif edge_count == 2:
			rotated = (
				entry.width  != slot.width or
				entry.height != slot.height
			)
			entry.place(slot.x, slot.y, rotated)
			self.free_slots.remove(slot)

	def _finish(self):
		x = y = 0
		self.result_height = 0
		for entry in self.entries:
			entry.set_size(
				entry.width - self.border,
				entry.height - self.border
			)
			if entry.rotated:
				x = entry.x + entry.height
				y = entry.y + entry.width
			else:
				x = entry.x + entry.width
				y = entry.y + entry.height
			if x > self.result_width:
				self.result_width = x
			if y > self.result_height:
				self.result_height = y

		if self.force_pow2:
			self.result_width = next_pow2(self.result_width)
			self.result_height = next_pow2(self.result_height)

		self.unused_area = (
			(self.result_width * self.result_height) - self.total_area
		)

	def _merge_slots(self):
		for a in self.free_slots:
			for b in self.free_slots:
				if (a is not b and a.merge(b)):
					self.free_slots.remove(b)
					return True
		return False

	def __repr__(self):
		return \
		("%s(" 
			"border: %d, force_pow2: %s, "
			"total_area: %d, unused_area: %d, longest_edge: %d, "
			"result_size: (%d, %d), entries: %r"
		")") % (
			type(self).__name__,
			self.border, self.force_pow2,
			self.total_area, self.unused_area, self.longest_edge,
			self.result_width, self.result_height, self.entries
		)