Maxrects-lua Documentation

Limited docs for now, but enough to explain the general idea of how to use the module.

• GitHub Page - The source in lua (and LÖVE).
• Exploring rectangle packing - Write-up exploring various algorithms for packing (Maxrects is a type of grid splitting) by David Colson.

or back to start.

Using maxrects.lua is as easy as requiring it, calling Maxrects.new() and then away you go. Here is an example:

require 'maxrects'
 
-- a packer for a 256 x 256 rectangle space
Packer = MaxRects.new(256,256)
 
-- insert a rectangle! (and attach our data to it)
Packer:insert(32, 32, { img = 'sprite1.png' } )

Of course, this does little. Let's say we had an array of sprite images we want to pack into a texture map:

-- sprites to pack into the map
OurSprites = { { 32, 32, 'tileA.png' },
 { 32, 32, 'tileB.png' },
 { 32, 32, 'tileC.png' } }
 
-- a packer for a 256 x 256 rectangle space
Packer = MaxRects.new(256,256)
 
-- insert a rectangle! (and attach our data to it)
local c = 1
local sprite = OurSprites[c]
while sprite do
 Packer:insert(sprite[1], sprite[2], sprite[3])
 c = c + 1
 sprite = OurSprites[c]
end

So above we have an array of tables, each table containing an array of { WIDTH, HEIGHT, IMG_NAME }. We iterate over that array of tables, inserting each into the rectangle held by Packer. Though, we have made one error of omission. You see :insert(width,height,data) returns a value: true, if the rect will fit and false, if the rect won't fit. Let's adjust the loop to reflect that:

while sprite do
 if not Packer:insert(sprite[1], sprite[2], sprite[3]) then
  error("Packer:insert() no more room!")
 end
 c = c + 1
 sprite = OurSprites[c]
end

Ok, now we catch that condition and error() out to reflect the problem. This is all well and good, but once you have the rectangles packed what then? We haven't actually made a texture map or anything, just assigned rectangle locations for the sprites. The module offers a function :iterate(func,other) which will call func() on all the rectangles in the collection. Like so:

-- ok, so draw the things into the texture
function DrawSprite(rect)
 -- rect is: { x, y, width, height }
 -- we assigned a filename to rect.data, so pass that here
 -- we assume TheImage is the target to draw on
 DoTheDraw(TheImage,rect.data,rect[1],rect[2],rect[3],rect[4])
end
 
Packer:iterate(DrawSprite)

So who knows what you are going to put into DoTheDraw(), that would be dependent on the software engine you are using. This is enough so you can see the semantics of how you iterate over all the contents to make a final image. Below I'll off up some code for LÖVE that'll expand on this a bit, and provide actual functionality.

Maxrects-lua defines a rectangle in a table as so:

• Array indexes 1, 2, 3, and 4 are X, Y, Width, and Height respectively. e.g. If you wanted to calculate the area of a rectangle: rect[3] * rect[4] is Width * Height.
• The field 'data' is user assigned to any Lua value and is there to contain information about what the rectangle represents. It is also valid for .data to be nil.
• The field 'flipped' is set to true if the rectangle was flipped to fit, assuming the algorithm allows that.

This format was chosen for ease of use, see these examples:

-- create a rectangle
MyRect = { 0, 0, 32, 32 } -- as simple as that { X, Y, Width, Height }
-- area of a rectangle
Area = MyRect[3] * MyRect[4] -- Width x Height
-- copy a rectangle
MyOtherRect = MaxRects.copy(MyRect) -- shallow copy of just the 4 indexes and two fields

All the exposed functions of this module, with in-depth explanations.

• width: The width of the full packing rectangle.
• height: The height of the full packing rectangle.
• canflip: optional Boolean, default false. If true the algorithm can flip rectangles for better fit.

• return: A table containing an instance of the packing algorithm, with the ability to store inserted rectangles.

Creates a new instance of a packing algorithm. This can be bypassed if you ever just need on instance, calling MaxRects:init(width,height,canflip) allows you to call later MaxRects:insert(), etc. The .new() is protected from changes you might make using MaxRects: calls and will always return a blank instance.

• rect: The rectangle to duplicate.

• return: A table containing the new copied rectangle.

Creates a shallow copy of a rectangle. Does not duplicate .data for instance, but copies the reference. Explicitly only copies: [1], [2], [3], [4], .data, and .flip.

• width: optional The width of the full packing rectangle.
• height: optional The height of the full packing rectangle.
• canflip: optional Boolean, default false. If true the algorithm can flip rectangles for better fit.

Resets an instance of the algorithm to a blank state with the supplied parameters. If supplied with no parameters, resets the instance with the same parameters it was created with.

• width: The width of the rectangle to insert.
• height: The height of the rectangle to insert.
• data: optional Data to attach to the field .data of the rectangle.

• return: Boolean. True if the rectangle was inserted, False if it didn't fit.

Inserts a rectangle into the collection, using the algorithm to assign a location. If the rectangle can't fit, returns false.

• rect: The rectangle to insert. X/Y([0]/[1]) are ignored, only Width([3]) and Height([4]) count.

• return: Boolean. True if the rectangle was inserted, False if it didn't fit.

Inserts a rectangle into the collection, using the algorithm to assign a location. If the rectangle can't fit, returns false. Copies .data into the stored node in the collection.

• collect: A table array of rectangles to insert into the collection (see :insertRect(rect))
• sort: optional A method to sort the rectangles before insert.

• return: Boolean, Number. True if all were inserted, False if only some fit. The number is the amount added.

Inserts rectangles into the collection, from an array table. If you define sort to one of: 'SortArea', 'SortShortSide', or 'SortLongSide' it will sort them from biggest to smallest using that method before inserting. If you pass anything else as sort, it'll throw an error. Note: If you pass a sort, then table.sort() is applied to collect, so it's order might/will be changed by this function.

• return: Number from 0 to 1. This is a measure of how full the packing rectangle is. A percentage would be done like so: :occupancy() * 100.

Reports how much of the packing rectangle has been filled. The algorithm does not store used space, so this is an O(N) call to iterate over all the contained rectangles. Though that might change in the future.

• func: The function to call over each rectangle in the collection, as so: func(rect).
• other: optional If supplied, passes that variable to the function called like so: func(other,rect).

Iterates over all the rectangles in a collection using func(rect). If you supply other, that becomes func(other,rect). Using this option allows you do iterate with a class/table, like so:

Packer:iterate(MyClass.func,MyClass)
 
function MyClass:func(rect)
 print("Got a rectangle!")
end

• algo: The algorithm to use for this instance. Defaults to 'BestShortSideFit'.

Applies a given algorithm to the packer. The options are: 'BestShortSideFit', 'BestLongSideFit', 'BestAreaFit', and 'ContactPointRule'. Passing any other value will throw an error.

• return: The algorithm in use for this instance. Defaults to 'BestShortSideFit'.

Returns the algorithm in use by the packer. The options are: 'BestShortSideFit', 'BestLongSideFit', 'BestAreaFit', and 'ContactPointRule'.

TODO!