# The rectangle-packing Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The rectangle-packing Reference Manual

This is the rectangle-packing Reference Manual, version 1.0.0, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:30:38 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

## 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.

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

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

Previous: , Up: Systems   [Contents][Index]

### 2.1 rectangle-packing

Author

Willem Rein Oudshoorn <woudshoo@xs4all.nl>

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

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Files

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

Previous: , Up: Files   [Contents][Index]

### 3.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 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

Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.3 rectangle-packing/rectangle-packing.lisp

Dependency

package.lisp (file)

Parent

rectangle-packing (system)

Location

rectangle-packing.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Packages

Packages are listed by definition order.

Previous: , Up: Packages   [Contents][Index]

### 4.1 rectangle-packing

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Definitions

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

Next: , Previous: , Up: Definitions   [Contents][Index]

### 5.1 Exported definitions

Previous: , Up: Exported definitions   [Contents][Index]

#### 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
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
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
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
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
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
Source

rectangle-packing.lisp (file)

Previous: , Up: Definitions   [Contents][Index]

### 5.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.1 Special variables

Special Variable: *size*
Package
Source

rectangle-packing.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 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
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
Source

rectangle-packing.lisp (file)

Function: translate RECT POINT
Package
Source

rectangle-packing.lisp (file)

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.3 Generic functions

Generic Function: content OBJECT
Generic Function: (setf content) NEW-VALUE OBJECT
Package
Methods
Method: content (NODE node)

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
Source

rectangle-packing.lisp (file)

Methods
Method: dimension (RECT target-rectangle) VAR
Method: dimension (RECT list) VAR
Generic Function: empty-target-p NODE
Package
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
Methods
Method: high (TARGET-RECTANGLE target-rectangle)

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
Source

rectangle-packing.lisp (file)

Methods
Method: hv OBJECT VAR
Method: hv (OBJECT list) VAR
Generic Function: insert-rectangle NODE RECTANGLE
Package
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
Methods
Method: left-child (NODE node)

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
Methods
Method: low (TARGET-RECTANGLE target-rectangle)

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
Source

rectangle-packing.lisp (file)

Methods
Method: lv OBJECT VAR
Method: lv (OBJECT list) VAR
Generic Function: placed-rectangle-p NODE-CONTENT
Package
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
Methods
Method: rectangle (TARGET-RECTANGLE target-rectangle)

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
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
Methods
Method: right-child (NODE node)

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
Methods
Method: split-var (TARGET-RECTANGLE target-rectangle)

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
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
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)

Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.4 Classes

Class: decision ()
Package
Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
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
Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: content
Initargs

:content

content (generic function)

Writers

(setf content) (generic function)

Slot: left-child

left-child (generic function)

Writers

(setf left-child) (generic function)

Slot: right-child

right-child (generic function)

Writers

(setf right-child) (generic function)

Class: target-rectangle ()
Package
Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: split-var
Type

(integer 0 1)

Initargs

:split-var

Initform

0

split-var (generic function)

Writers

(setf split-var) (generic function)

Slot: low
Initargs

:low

Initform

(list 0 0)

low (generic function)

Writers

(setf low) (generic function)

Slot: high
Initargs

:high

Initform

(list nil nil)

high (generic function)

Writers

(setf high) (generic function)

Slot: rectangle
Initargs

:rectangle

rectangle (generic function)

Writers

(setf rectangle) (generic function)

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

Jump to: (   C   D   E   F   G   H   I   L   M   P   R   S   T   W
Jump to: (   C   D   E   F   G   H   I   L   M   P   R   S   T   W

Next: , Previous: , Up: Indexes   [Contents][Index]