The rectangle-packing Reference Manual

Table of Contents

The rectangle-packing Reference Manual

This is the rectangle-packing Reference Manual, version 1.0.0, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Feb 19 21:28:18 2020 GMT+0.

1 Introduction

Simple Bin Packing / Rectangle Packing

This code implements a simple algorithm for a complicated problem, given a set of rectangles, pack them into a square/rectangle.

I wrote this because I am playing with OpenGL and want to pack multiple graphics into a texture.

Inspiration

This code is a straight adaptation of the code found Packing Lightmaps.

Interface

The main interface consists of two functions pack-rectangles and pack-rectangles-tree. Both functions take two arguments,

1. A list of rectangles
2. A keyword argument :size specifying the size of the target rectangle (as a rectangle)

The only difference is the return value. The function pack-rectangles-tree return a tree representation of the packing. This tree is mostly usefull as an intermediate representation.

The pack-rectangles returns a list of placements, each placement is of the form (x y orientation rectangle) where rectangle is one of the input rectangles, the x and y are the placement coordinates, and orientation indicates if the rectangle is rotated.

At the moment orientation is always :0 indicating no rotation.

Rectangles

A rectangle is any list as along as the first two values of the list indicate the width and height of the rectangle. So for example (200 300 "This is a rectangle") is a rectangle, and so is (200 300) or (200 300 (lambda (x) x))

Supporting functions

1. tree-utilized-size takes one argument, a tree, and returns the packed size.
2. rectangle-tree-to-rectangle-list takes a tree as an argument and returns the same output as pack-rectangles.
3. write-html takes a tree and a file name and write a html file which will show the packing.

Tips

The code tries to place the rectangles in the order they are given. It turns out that it pays off to trie them in order of size. E.g. first sort them on either area or lexicographically on the coordinates.

Example

Simple packing.

> (pack-rectangles (list '(100 200 "Hallo") '(300 400 "Nr 2")  '(50 100 "Tall") '(200 30 "Wide")))
=>
((400 0 :|0| 200 30 "Wide") (100 0 :|0| 300 400 "Nr 2")
 (0 200 :|0| 50 100 "Tall") (0 0 :|0| 100 200 "Hallo"))

Or using the tree

> (pack-rectangles-tree (list '(100 200 "Hallo") '(300 400 "Nr 2")  '(50 100 "Tall") '(200 30 "Wide")))
=>
#<NODE {100CCF8473}>
> (write-html * "/tmp/pack.html")
=>
NIL

The resulting html shows a picture like this, note that the target size was very large, so red rectangle sticking out to the right easily fits.

Improvements

1. It should have the ability to automatically increase the target size.
2. It should also try rotations.
3. Performance, it is currently not optimized for performance. If performance is an issue, there is a lot that can be done to make it faster.

LICENSE

It is licensed under LLGPL. This is because it is my default license when I do not want to think about licensing stuff. However, I am flexible and if you want any other license, ask me, and I am likely to agree with it.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 rectangle-packing

Author

Willem Rein Oudshoorn <woudshoo@xs4all.nl>

License

LLGPL, but I am flexible, ask me if you want something else.

Description

Code to pack rectangles into a bigger rectangle. Useful for texture packing for OpenGL.

Version

1.0.0

Source

rectangle-packing.asd (file)

Components

• package.lisp (file)
• rectangle-packing.lisp (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 rectangle-packing.asd

Location

rectangle-packing.asd

Systems

rectangle-packing (system)

3.1.2 rectangle-packing/package.lisp

Parent

rectangle-packing (system)

Location

package.lisp

Packages

rectangle-packing

3.1.3 rectangle-packing/rectangle-packing.lisp

Dependency

package.lisp (file)

Parent

rectangle-packing (system)

Location

rectangle-packing.lisp

Exported Definitions

• pack-rectangles (function)
• pack-rectangles-tree (function)
• rectangle-tree-to-rectangle-list (function)
• sort-rectangles-on-size (function)
• tree-utilized-size (function)
• write-html (function)

Internal Definitions

• *size* (special variable)
• content (method)
• (setf content) (method)
• decision (class)
• dimension (generic function)
• dimension (method)
• dimension (method)
• empty-target-p (generic function)
• empty-target-p (method)
• empty-target-p (method)
• high (method)
• (setf high) (method)
• hv (generic function)
• hv (method)
• hv (method)
• insert-rectangle (method)
• left-child (method)
• (setf left-child) (method)
• low (method)
• (setf low) (method)
• lv (generic function)
• lv (method)
• lv (method)
• node (class)
• placed-rectangle-p (generic function)
• placed-rectangle-p (method)
• placed-rectangle-p (method)
• rectangle (method)
• (setf rectangle) (method)
• rectangle-fits (generic function)
• rectangle-fits (method)
• right-child (method)
• (setf right-child) (method)
• split-node (function)
• split-node-once (function)
• split-var (method)
• (setf split-var) (method)
• target-rectangle (class)
• translate (function)
• walk-tree-pre-order (generic function)
• walk-tree-pre-order (method)
• walk-tree-pre-order (method)
• write-svg-element (generic function)
• write-svg-element (method)
• write-svg-element (method)
• write-svg-element (method)

4 Packages

Packages are listed by definition order.

4.1 rectangle-packing

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• pack-rectangles (function)
• pack-rectangles-tree (function)
• rectangle-tree-to-rectangle-list (function)
• sort-rectangles-on-size (function)
• tree-utilized-size (function)
• write-html (function)

Internal Definitions

• *size* (special variable)
• content (generic function)
• content (method)
• (setf content) (method)
• (setf content) (generic function)
• decision (class)
• dimension (generic function)
• dimension (method)
• dimension (method)
• empty-target-p (generic function)
• empty-target-p (method)
• empty-target-p (method)
• high (generic function)
• high (method)
• (setf high) (method)
• (setf high) (generic function)
• hv (generic function)
• hv (method)
• hv (method)
• insert-rectangle (generic function)
• insert-rectangle (method)
• left-child (generic function)
• left-child (method)
• (setf left-child) (method)
• (setf left-child) (generic function)
• low (generic function)
• low (method)
• (setf low) (method)
• (setf low) (generic function)
• lv (generic function)
• lv (method)
• lv (method)
• node (class)
• placed-rectangle-p (generic function)
• placed-rectangle-p (method)
• placed-rectangle-p (method)
• rectangle (generic function)
• rectangle (method)
• (setf rectangle) (method)
• (setf rectangle) (generic function)
• rectangle-fits (generic function)
• rectangle-fits (method)
• right-child (generic function)
• right-child (method)
• (setf right-child) (method)
• (setf right-child) (generic function)
• split-node (function)
• split-node-once (function)
• split-var (generic function)
• split-var (method)
• (setf split-var) (method)
• (setf split-var) (generic function)
• target-rectangle (class)
• translate (function)
• walk-tree-pre-order (generic function)
• walk-tree-pre-order (method)
• walk-tree-pre-order (method)
• write-svg-element (generic function)
• write-svg-element (method)
• write-svg-element (method)
• write-svg-element (method)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: pack-rectangles RECTANGLES &key SIZE

Takes a list of rectangles, where each rectangle
is specified as (width height . rest).

The size argument specifies the size of the target rectangle.

Returns a list of (x y orientation . rectangle)
Where rectangle is one of the argument rectangles
and orientation is either :0 or :90 (when it is rotated).
The location of the rectangles is given by ’x’ and ’y’.

Note that if not all rectangles can be placed, they will be silently dropped from the packing and from the output.

To see which rectangles are packed you can use

(mapcar (pack-rectangles ...) #’cdddr)

NOTE: See also the note on the sort order of the rectangles in the function ‘pack-rectangles-tree’

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: pack-rectangles-tree RECTANGLES &key SIZE

Takes a list of rectangles, where each rectangle
is specified as (width height . rest).

Returns a tree containing the pack information.

The size parameter is a list of the form (width height . rest) and
this specifies size of the target rectangle in which all the rectangles are packed.

If some rectangles do not fit they are silently skipped. To see if
the rectangles are skipped you have to call
‘rectangle-tree-to-rectangle-list’ and compare the length of the
resulting list.

NOTE: This function tries to pack the rectangles one by one.
So the sort order can have a huge impact on the efficiency
of the packing.

Experience has shown that in practice it is good idea to
sort the rectangles on size (the area). With the largest
rectangles first.

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: rectangle-tree-to-rectangle-list ROOT

Takes a rectangle tree as returned by ‘pack-rectangles-tree’ as argument and returns
the packed rectangles as a list.

Each item of the list is rectangle, specified as (x y orientation . rectangle)
where ’rectangle’ is one of the original inputed rectangle.
The location of the packed rectangle is given by ’x’ and ’y’.

Orientation is either :0 or :90 depending if the rectangle is placed as given, or rotated. Note that the current algorithm does not use rotation and will always have :0 as orientation.

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: sort-rectangles-on-size RECTANGLES

Sort the ‘rectangles’ form largest to smalles area.
This operation is non-destructive and for the format of the ‘rectangles’ argument see ‘pack-rectangles’.

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: tree-utilized-size NODE

Returns the minimum enclosing rectangle of the rectangle tree ‘node’.

If the ‘node’ is created with ‘pack-rectangles-tree’ the result is
guarenteed (with restrictions, see the ‘pack-rectangles-tree’ function)
to fit in the given size.

However it is of course possible that the packing does not use the whole rectangle. This function returns the smallest enclosing rectangle for the packing.

The return value is a list of two elements:

(width height)

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: write-html NODE FILE-NAME

Writes a packing tree to an html file so the packing can be previewd. The red rectangles are placed, the blue is empty space.

See ‘pack-rectangles-tree’ for how to create a packing tree.

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

5.2 Internal definitions

5.2.1 Special variables

Special Variable: *size*

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

5.2.2 Functions

Function: split-node NODE RECTANGLE

Node needs to be a target-rectangle and rectangle needs to fit inside this rectangle.

This function will change:

node ... (target-rectangle)

==>
node ... (decision)
/
/ node ... (target-rectangle) /
node ... (decision)
/
/ node ... (target-rectangle)
/
node ... (target-rectangle = rectangle)

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: split-node-once NODE RECTANGLE

Replaces the target node node
with a decision node with two target node children.

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Function: translate RECT POINT

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

5.2.3 Generic functions

Generic Function: content OBJECT

Generic Function: (setf content) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: content (NODE node)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf content) NEW-VALUE (NODE node)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: dimension OBJECT VAR

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: dimension (RECT target-rectangle) VAR

Method: dimension (RECT list) VAR

Generic Function: empty-target-p NODE

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: empty-target-p (NODE decision)

Method: empty-target-p (NODE target-rectangle)

Generic Function: high OBJECT

Generic Function: (setf high) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: high (TARGET-RECTANGLE target-rectangle)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf high) NEW-VALUE (TARGET-RECTANGLE target-rectangle)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: hv OBJECT VAR

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: hv OBJECT VAR

Method: hv (OBJECT list) VAR

Generic Function: insert-rectangle NODE RECTANGLE

Package

rectangle-packing

Methods

Method: insert-rectangle (NODE node) RECTANGLE

Inserts the rectangle specified as (width height . rest)
in the tree, and if necessary expand the tree.

Special variables are *size* as (width height) of the total rectangle in which the rectangles are packed

Source

rectangle-packing.lisp (file)

Generic Function: left-child OBJECT

Generic Function: (setf left-child) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: left-child (NODE node)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf left-child) NEW-VALUE (NODE node)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: low OBJECT

Generic Function: (setf low) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: low (TARGET-RECTANGLE target-rectangle)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf low) NEW-VALUE (TARGET-RECTANGLE target-rectangle)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: lv OBJECT VAR

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: lv OBJECT VAR

Method: lv (OBJECT list) VAR

Generic Function: placed-rectangle-p NODE-CONTENT

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: placed-rectangle-p NODE-CONTENT

Method: placed-rectangle-p (NODE-CONTENT target-rectangle)

Generic Function: rectangle OBJECT

Generic Function: (setf rectangle) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: rectangle (TARGET-RECTANGLE target-rectangle)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf rectangle) NEW-VALUE (TARGET-RECTANGLE target-rectangle)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: rectangle-fits NODE RECTANGLE

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: rectangle-fits (NODE target-rectangle) RECTANGLE

Generic Function: right-child OBJECT

Generic Function: (setf right-child) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: right-child (NODE node)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf right-child) NEW-VALUE (NODE node)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: split-var OBJECT

Generic Function: (setf split-var) NEW-VALUE OBJECT

Package

rectangle-packing

Methods

Method: split-var (TARGET-RECTANGLE target-rectangle)

automatically generated reader method

Source

rectangle-packing.lisp (file)

Method: (setf split-var) NEW-VALUE (TARGET-RECTANGLE target-rectangle)

automatically generated writer method

Source

rectangle-packing.lisp (file)

Generic Function: walk-tree-pre-order NODE FUNCTION

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: walk-tree-pre-order NODE FUNCTION

Method: walk-tree-pre-order (NODE node) FUNCTION

Generic Function: write-svg-element STREAM ELEMENT

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Methods

Method: write-svg-element (S stream) (NODE node)

Method: write-svg-element (S stream) (RECT target-rectangle)

Method: write-svg-element (S stream) (RECT decision)

5.2.4 Classes

Class: decision ()

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• write-svg-element (method)
• empty-target-p (method)

Direct slots

Slot: decision-var

Type

(integer 0 1)

Initargs

:decision-var

Initform

0

Slot: low

Initargs

:low

Initform

0

Slot: decision

Initargs

:decision

Initform

0

Slot: high

Initargs

:high

Class: node ()

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• write-svg-element (method)
• insert-rectangle (method)
• walk-tree-pre-order (method)
• right-child (method)
• right-child (method)
• left-child (method)
• left-child (method)
• content (method)
• content (method)

Direct slots

Slot: content

Initargs

:content

Readers

content (generic function)

Writers

(setf content) (generic function)

Slot: left-child

Readers

left-child (generic function)

Writers

(setf left-child) (generic function)

Slot: right-child

Readers

right-child (generic function)

Writers

(setf right-child) (generic function)

Class: target-rectangle ()

Package

rectangle-packing

Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• write-svg-element (method)
• rectangle-fits (method)
• placed-rectangle-p (method)
• empty-target-p (method)
• dimension (method)
• rectangle (method)
• rectangle (method)
• high (method)
• high (method)
• low (method)
• low (method)
• split-var (method)
• split-var (method)

Direct slots

Slot: split-var

Type

(integer 0 1)

Initargs

:split-var

Initform

0

Readers

split-var (generic function)

Writers

(setf split-var) (generic function)

Slot: low

Initargs

:low

Initform

(list 0 0)

Readers

low (generic function)

Writers

(setf low) (generic function)

Slot: high

Initargs

:high

Initform

(list nil nil)

Readers

high (generic function)

Writers

(setf high) (generic function)

Slot: rectangle

Initargs

:rectangle

Readers

rectangle (generic function)

Writers

(setf rectangle) (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types