binpack

Documentation

Overview

Package binpack implements Jake Gordon's 2D binpacking algorithm.

The algorithm used is described on Jake's blog here:

http://codeincomplete.com/posts/2011/5/7/bin_packing/

And is also implemented by him in JavaScript here:

https://github.com/jakesgordon/bin-packing

Index

• func Pack(p Packable) (width, height int)
• type Packable

Functions

func Pack

func Pack(p Packable) (width, height int)

Pack uses the packable interface, p, to pack two dimensional blocks onto a larger two dimensional grid.

The algorithm does not start with an fixed width and height, instead it starts with the width and height of the first block and then grows as neccessary to fit each block into the overall grid. As the grid is grown the algorithm attempts to maintain an roughly square ratio by making 'smart' choices about whether to grow right or down.

The returned width and height reflect how large the overall grid must be to contain at least each packed block.

When growing, the algorithm can only grow to the right or down. If the new block is both wider and taller than the first [p.Size(0)] block, then the algorithm will be unable to pack the blocks, and [-1, -1] will be returned.

To avoid the above problem, sort blocks by max(width, height).

If the number of blocks is zero (p.Len() == 0) then this function is no-op and [0, 0] is returned.

Types

type Packable

type Packable interface {
	// Len should return the number of blocks in total.
	Len() int

	// Size should return the width and height of the block n
	Size(n int) (width, height int)

	// Place should place the block n, at the position [x, y].
	Place(n, x, y int)
}