The rectangle-packing Reference Manual

This is the rectangle-packing Reference Manual, version 1.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Sun Dec 08 19:28:08 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 rectangle-packing

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

Author

Willem Rein Oudshoorn <>

License

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

Version

1.0.0

Source

rectangle-packing.asd.

Child Components

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/rectangle-packing.asd

Source

rectangle-packing.asd.

Parent Component

rectangle-packing (system).

ASDF Systems

rectangle-packing.


3.1.2 rectangle-packing/package.lisp

Source

rectangle-packing.asd.

Parent Component

rectangle-packing (system).

Packages

rectangle-packing.


3.1.3 rectangle-packing/rectangle-packing.lisp

Dependency

package.lisp (file).

Source

rectangle-packing.asd.

Parent Component

rectangle-packing (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 rectangle-packing

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


5.1 Public Interface


5.1.1 Ordinary 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.

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.

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.

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.

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.

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.


5.2 Internals


5.2.1 Special variables

Special Variable: *size*
Package

rectangle-packing.

Source

rectangle-packing.lisp.


5.2.2 Ordinary 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.

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.

Function: translate (rect point)
Package

rectangle-packing.

Source

rectangle-packing.lisp.


5.2.3 Generic functions

Generic Reader: content (object)
Package

rectangle-packing.

Methods
Reader Method: content ((node node))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

content.

Generic Writer: (setf content) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf content) ((node node))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

content.

Generic Function: dimension (object var)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

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.

Methods
Method: empty-target-p ((node decision))
Method: empty-target-p ((node target-rectangle))
Generic Reader: high (object)
Package

rectangle-packing.

Methods
Reader Method: high ((target-rectangle target-rectangle))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

high.

Generic Writer: (setf high) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf high) ((target-rectangle target-rectangle))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

high.

Generic Function: hv (object var)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

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.

Generic Reader: left-child (object)
Package

rectangle-packing.

Methods
Reader Method: left-child ((node node))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

left-child.

Generic Writer: (setf left-child) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf left-child) ((node node))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

left-child.

Generic Reader: low (object)
Package

rectangle-packing.

Methods
Reader Method: low ((target-rectangle target-rectangle))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

low.

Generic Writer: (setf low) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf low) ((target-rectangle target-rectangle))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

low.

Generic Function: lv (object var)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

Methods
Method: lv (object var)
Method: lv ((object list) var)
Generic Function: placed-rectangle-p (node-content)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

Methods
Method: placed-rectangle-p (node-content)
Method: placed-rectangle-p ((node-content target-rectangle))
Generic Reader: rectangle (object)
Package

rectangle-packing.

Methods
Reader Method: rectangle ((target-rectangle target-rectangle))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

rectangle.

Generic Writer: (setf rectangle) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf rectangle) ((target-rectangle target-rectangle))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

rectangle.

Generic Function: rectangle-fits (node rectangle)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

Methods
Method: rectangle-fits ((node target-rectangle) rectangle)
Generic Reader: right-child (object)
Package

rectangle-packing.

Methods
Reader Method: right-child ((node node))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

right-child.

Generic Writer: (setf right-child) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf right-child) ((node node))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

right-child.

Generic Reader: split-var (object)
Package

rectangle-packing.

Methods
Reader Method: split-var ((target-rectangle target-rectangle))

automatically generated reader method

Source

rectangle-packing.lisp.

Target Slot

split-var.

Generic Writer: (setf split-var) (object)
Package

rectangle-packing.

Methods
Writer Method: (setf split-var) ((target-rectangle target-rectangle))

automatically generated writer method

Source

rectangle-packing.lisp.

Target Slot

split-var.

Generic Function: walk-tree-pre-order (node function)
Package

rectangle-packing.

Source

rectangle-packing.lisp.

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.

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.

Direct methods
Direct slots
Slot: decision-var
Type

(integer 0 1)

Initform

0

Initargs

:decision-var

Slot: low
Initform

0

Initargs

:low

Slot: decision
Initform

0

Initargs

:decision

Slot: high
Initargs

:high

Class: node
Package

rectangle-packing.

Source

rectangle-packing.lisp.

Direct methods
Direct slots
Slot: content
Initargs

:content

Readers

content.

Writers

(setf content).

Slot: left-child
Readers

left-child.

Writers

(setf left-child).

Slot: right-child
Readers

right-child.

Writers

(setf right-child).

Class: target-rectangle
Package

rectangle-packing.

Source

rectangle-packing.lisp.

Direct methods
Direct slots
Slot: split-var
Type

(integer 0 1)

Initform

0

Initargs

:split-var

Readers

split-var.

Writers

(setf split-var).

Slot: low
Initform

(list 0 0)

Initargs

:low

Readers

low.

Writers

(setf low).

Slot: high
Initform

(list nil nil)

Initargs

:high

Readers

high.

Writers

(setf high).

Slot: rectangle
Initargs

:rectangle

Readers

rectangle.

Writers

(setf rectangle).


Appendix A Indexes


A.1 Concepts


A.2 Functions

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

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

C
content: Private generic functions
content: Private generic functions

D
dimension: Private generic functions
dimension: Private generic functions
dimension: Private generic functions

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

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

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

H
high: Private generic functions
high: Private generic functions
hv: Private generic functions
hv: Private generic functions
hv: Private generic functions

I
insert-rectangle: Private generic functions
insert-rectangle: Private generic functions

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

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

P
pack-rectangles: Public ordinary functions
pack-rectangles-tree: Public ordinary functions
placed-rectangle-p: Private generic functions
placed-rectangle-p: Private generic functions
placed-rectangle-p: Private generic functions

R
rectangle: Private generic functions
rectangle: Private generic functions
rectangle-fits: Private generic functions
rectangle-fits: Private generic functions
rectangle-tree-to-rectangle-list: Public ordinary functions
right-child: Private generic functions
right-child: Private generic functions

S
sort-rectangles-on-size: Public ordinary functions
split-node: Private ordinary functions
split-node-once: Private ordinary functions
split-var: Private generic functions
split-var: Private generic functions

T
translate: Private ordinary functions
tree-utilized-size: Public ordinary functions

W
walk-tree-pre-order: Private generic functions
walk-tree-pre-order: Private generic functions
walk-tree-pre-order: Private generic functions
write-html: Public ordinary functions
write-svg-element: Private generic functions
write-svg-element: Private generic functions
write-svg-element: Private generic functions
write-svg-element: Private generic functions