Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
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.
| • Introduction: | What rectangle-packing is all about | |
| • Systems: | The systems documentation | |
| • Files: | The files documentation | |
| • Packages: | The packages documentation | |
| • Definitions: | The symbols documentation | |
| • Indexes: | Concepts, functions, variables and data types |
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.
This code is a straight adaptation of the code found Packing Lightmaps.
The main interface consists of two functions pack-rectangles and
pack-rectangles-tree.
Both functions take two arguments,
: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.
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))
tree-utilized-size takes one argument, a tree, and returns the packed size.rectangle-tree-to-rectangle-list takes a tree as an argument and returns the same output as pack-rectangles.write-html takes a tree and a file name and write a html file which will show the packing.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.
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.
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: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The rectangle-packing system: |
Willem Rein Oudshoorn <woudshoo@xs4all.nl>
LLGPL, but I am flexible, ask me if you want something else.
Code to pack rectangles into a bigger rectangle. Useful for texture packing for OpenGL.
1.0.0
rectangle-packing.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files: |
| • The rectangle-packing.asd file: | ||
| • The rectangle-packing/package.lisp file: | ||
| • The rectangle-packing/rectangle-packing.lisp file: |
Next: The rectangle-packing/package<dot>lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
rectangle-packing.asd
rectangle-packing (system)
Next: The rectangle-packing/rectangle-packing<dot>lisp file, Previous: The rectangle-packing<dot>asd file, Up: Lisp files [Contents][Index]
rectangle-packing (system)
package.lisp
Previous: The rectangle-packing/package<dot>lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
rectangle-packing (system)
rectangle-packing.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The rectangle-packing package: |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions: | ||
| • Internal definitions: |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported functions: |
Previous: Exported definitions, Up: Exported definitions [Contents][Index]
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’
rectangle-packing.lisp (file)
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.
rectangle-packing.lisp (file)
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.
rectangle-packing.lisp (file)
Sort the ‘rectangles’ form largest to smalles area.
This operation is non-destructive and for the format of the ‘rectangles’ argument
see ‘pack-rectangles’.
rectangle-packing.lisp (file)
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)
rectangle-packing.lisp (file)
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.
rectangle-packing.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal special variables: | ||
| • Internal functions: | ||
| • Internal generic functions: | ||
| • Internal classes: |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
rectangle-packing.lisp (file)
Next: Internal generic functions, Previous: Internal special variables, Up: Internal definitions [Contents][Index]
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)
rectangle-packing.lisp (file)
Replaces the target node node
with a decision node with two target node children.
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
Next: Internal classes, Previous: Internal functions, Up: Internal definitions [Contents][Index]
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
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
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
automatically generated reader method
rectangle-packing.lisp (file)
automatically generated writer method
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
rectangle-packing.lisp (file)
Previous: Internal generic functions, Up: Internal definitions [Contents][Index]
rectangle-packing.lisp (file)
standard-object (class)
(integer 0 1)
:decision-var
0
:low
0
:decision
0
:high
rectangle-packing.lisp (file)
standard-object (class)
:content
content (generic function)
(setf content) (generic function)
left-child (generic function)
(setf left-child) (generic function)
right-child (generic function)
(setf right-child) (generic function)
rectangle-packing.lisp (file)
standard-object (class)
(integer 0 1)
:split-var
0
split-var (generic function)
(setf split-var) (generic function)
:low
(list 0 0)
low (generic function)
(setf low) (generic function)
:high
(list nil nil)
high (generic function)
(setf high) (generic function)
:rectangle
rectangle (generic function)
(setf rectangle) (generic function)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index: | ||
| • Function index: | ||
| • Variable index: | ||
| • Data type index: |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | F L R |
|---|
| Jump to: | F L R |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| 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: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | *
C D H L R S |
|---|
| Jump to: | *
C D H L R S |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | C D N P R S T |
|---|
| Jump to: | C D N P R S T |
|---|