The rectangle-packing Reference Manual

Table of Contents

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]

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.

Screen shot of browser

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.


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>

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

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)


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

3.1.2 rectangle-packing/package.lisp

Parent

rectangle-packing (system)

Location

package.lisp

Packages

rectangle-packing


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

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)


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

rectangle-packing

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

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)


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

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)

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

5.2.4 Classes

Class: decision ()
Package

rectangle-packing

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

rectangle-packing

Source

rectangle-packing.lisp (file)

Direct superclasses

standard-object (class)

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


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L   R  
Index Entry  Section

F
File, Lisp, rectangle-packing.asd: The rectangle-packing<dot>asd file
File, Lisp, rectangle-packing/package.lisp: The rectangle-packing/package<dot>lisp file
File, Lisp, rectangle-packing/rectangle-packing.lisp: The rectangle-packing/rectangle-packing<dot>lisp file

L
Lisp File, rectangle-packing.asd: The rectangle-packing<dot>asd file
Lisp File, rectangle-packing/package.lisp: The rectangle-packing/package<dot>lisp file
Lisp File, rectangle-packing/rectangle-packing.lisp: The rectangle-packing/rectangle-packing<dot>lisp file

R
rectangle-packing.asd: The rectangle-packing<dot>asd file
rectangle-packing/package.lisp: The rectangle-packing/package<dot>lisp file
rectangle-packing/rectangle-packing.lisp: The rectangle-packing/rectangle-packing<dot>lisp file

Jump to:   F   L   R  

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  
Index Entry  Section

(
(setf content): Internal generic functions
(setf content): Internal generic functions
(setf high): Internal generic functions
(setf high): Internal generic functions
(setf left-child): Internal generic functions
(setf left-child): Internal generic functions
(setf low): Internal generic functions
(setf low): Internal generic functions
(setf rectangle): Internal generic functions
(setf rectangle): Internal generic functions
(setf right-child): Internal generic functions
(setf right-child): Internal generic functions
(setf split-var): Internal generic functions
(setf split-var): Internal generic functions

C
content: Internal generic functions
content: Internal generic functions

D
dimension: Internal generic functions
dimension: Internal generic functions
dimension: Internal generic functions

E
empty-target-p: Internal generic functions
empty-target-p: Internal generic functions
empty-target-p: Internal generic functions

F
Function, pack-rectangles: Exported functions
Function, pack-rectangles-tree: Exported functions
Function, rectangle-tree-to-rectangle-list: Exported functions
Function, sort-rectangles-on-size: Exported functions
Function, split-node: Internal functions
Function, split-node-once: Internal functions
Function, translate: Internal functions
Function, tree-utilized-size: Exported functions
Function, write-html: Exported functions

G
Generic Function, (setf content): Internal generic functions
Generic Function, (setf high): Internal generic functions
Generic Function, (setf left-child): Internal generic functions
Generic Function, (setf low): Internal generic functions
Generic Function, (setf rectangle): Internal generic functions
Generic Function, (setf right-child): Internal generic functions
Generic Function, (setf split-var): Internal generic functions
Generic Function, content: Internal generic functions
Generic Function, dimension: Internal generic functions
Generic Function, empty-target-p: Internal generic functions
Generic Function, high: Internal generic functions
Generic Function, hv: Internal generic functions
Generic Function, insert-rectangle: Internal generic functions
Generic Function, left-child: Internal generic functions
Generic Function, low: Internal generic functions
Generic Function, lv: Internal generic functions
Generic Function, placed-rectangle-p: Internal generic functions
Generic Function, rectangle: Internal generic functions
Generic Function, rectangle-fits: Internal generic functions
Generic Function, right-child: Internal generic functions
Generic Function, split-var: Internal generic functions
Generic Function, walk-tree-pre-order: Internal generic functions
Generic Function, write-svg-element: Internal generic functions

H
high: Internal generic functions
high: Internal generic functions
hv: Internal generic functions
hv: Internal generic functions
hv: Internal generic functions

I
insert-rectangle: Internal generic functions
insert-rectangle: Internal generic functions

L
left-child: Internal generic functions
left-child: Internal generic functions
low: Internal generic functions
low: Internal generic functions
lv: Internal generic functions
lv: Internal generic functions
lv: Internal generic functions

M
Method, (setf content): Internal generic functions
Method, (setf high): Internal generic functions
Method, (setf left-child): Internal generic functions
Method, (setf low): Internal generic functions
Method, (setf rectangle): Internal generic functions
Method, (setf right-child): Internal generic functions
Method, (setf split-var): Internal generic functions
Method, content: Internal generic functions
Method, dimension: Internal generic functions
Method, dimension: Internal generic functions
Method, empty-target-p: Internal generic functions
Method, empty-target-p: Internal generic functions
Method, high: Internal generic functions
Method, hv: Internal generic functions
Method, hv: Internal generic functions
Method, insert-rectangle: Internal generic functions
Method, left-child: Internal generic functions
Method, low: Internal generic functions
Method, lv: Internal generic functions
Method, lv: Internal generic functions
Method, placed-rectangle-p: Internal generic functions
Method, placed-rectangle-p: Internal generic functions
Method, rectangle: Internal generic functions
Method, rectangle-fits: Internal generic functions
Method, right-child: Internal generic functions
Method, split-var: Internal generic functions
Method, walk-tree-pre-order: Internal generic functions
Method, walk-tree-pre-order: Internal generic functions
Method, write-svg-element: Internal generic functions
Method, write-svg-element: Internal generic functions
Method, write-svg-element: Internal generic functions

P
pack-rectangles: Exported functions
pack-rectangles-tree: Exported functions
placed-rectangle-p: Internal generic functions
placed-rectangle-p: Internal generic functions
placed-rectangle-p: Internal generic functions

R
rectangle: Internal generic functions
rectangle: Internal generic functions
rectangle-fits: Internal generic functions
rectangle-fits: Internal generic functions
rectangle-tree-to-rectangle-list: Exported functions
right-child: Internal generic functions
right-child: Internal generic functions

S
sort-rectangles-on-size: Exported functions
split-node: Internal functions
split-node-once: Internal functions
split-var: Internal generic functions
split-var: Internal generic functions

T
translate: Internal functions
tree-utilized-size: Exported functions

W
walk-tree-pre-order: Internal generic functions
walk-tree-pre-order: Internal generic functions
walk-tree-pre-order: Internal generic functions
write-html: Exported functions
write-svg-element: Internal generic functions
write-svg-element: Internal generic functions
write-svg-element: Internal generic functions
write-svg-element: Internal generic functions

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

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

A.3 Variables

Jump to:   *  
C   D   H   L   R   S  
Index Entry  Section

*
*size*: Internal special variables

C
content: Internal classes

D
decision: Internal classes
decision-var: Internal classes

H
high: Internal classes
high: Internal classes

L
left-child: Internal classes
low: Internal classes
low: Internal classes

R
rectangle: Internal classes
right-child: Internal classes

S
Slot, content: Internal classes
Slot, decision: Internal classes
Slot, decision-var: Internal classes
Slot, high: Internal classes
Slot, high: Internal classes
Slot, left-child: Internal classes
Slot, low: Internal classes
Slot, low: Internal classes
Slot, rectangle: Internal classes
Slot, right-child: Internal classes
Slot, split-var: Internal classes
Special Variable, *size*: Internal special variables
split-var: Internal classes

Jump to:   *  
C   D   H   L   R   S  

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

A.4 Data types

Jump to:   C   D   N   P   R   S   T  
Index Entry  Section

C
Class, decision: Internal classes
Class, node: Internal classes
Class, target-rectangle: Internal classes

D
decision: Internal classes

N
node: Internal classes

P
Package, rectangle-packing: The rectangle-packing package

R
rectangle-packing: The rectangle-packing system
rectangle-packing: The rectangle-packing package

S
System, rectangle-packing: The rectangle-packing system

T
target-rectangle: Internal classes

Jump to:   C   D   N   P   R   S   T