# Automatic box packing

I have a number of say, subfigures, of varying shapes and would like to waste less space displaying them; their order doesn't matter, and rather than having them all lined up on the same baseline I would prefer a 2D packing.

\documentclass{article}
\def\X#1#2{%
\fbox{\hbox to #1{\vbox to #2{}}}
}
\begin{document}
\begin{figure}
\X{2cm}{3cm}\X{2cm}{6cm}\X{3cm}{2cm}
\X{2cm}{3cm}\X{4cm}{3cm}\X{1cm}{4cm}
\X{3cm}{3cm}\X{2cm}{5cm}\X{2cm}{6cm}
\caption{My rectangles}
\end{figure}
\end{document}


Produces this:

I could use a picture-environment to manually arrange the boxes, but this seems cumbersome, I'd rather have an environment I can tell the maximum width and height and have it pack the content automatically.

This seems relatively straightforward using LuaTex (i.e. collect the boxes, measure them, run a rectangle packing algorithm like Korf's using the sizes, place the boxes at their optimal coordinates).

Has anybody implemented something like this yet? I don't necessarily need an optimal solution, but I couldn't find anything in that direction.

• Possibly related: tex.stackexchange.com/questions/168748/… – Steven B. Segletes Mar 30 '15 at 19:34
• Oh yes tex.stackexchange.com/a/65601/2356 seems like exactly what I'm looking for -- weird the search didn't show any related results for 'packing' – pascal Mar 30 '15 at 19:39
• Of course, my answer there does not rearrange, which would indeed open up new possibilities for optimization. – Steven B. Segletes Mar 30 '15 at 19:40
• I would use your answer for i.e. images, but my boxes contain text/tikz graphics, and that would look weird resized. I'll try michal.h21's code, but I'm not sure if I like that algorithm's output… – pascal Mar 30 '15 at 19:46
• I agree that resizing text is problematic in this context. – Steven B. Segletes Mar 30 '15 at 19:47

I modified the code from this answer quite substantially -- we don't have to mark every item in the environment specially, there's no need for a picture environment, we only use the temp box register.

The new generativelayout.sty: we create new lengths for the root box that can be set dynamically (I'm simply using all the available space). The environment collects its contents in a box which we unpack in Lua, no need to use a box register for each item.

\ProvidesPackage{generativelayout}
\directlua{gen = require('generativelayout')}
\newdimen\generativewidth
\newdimen\generativeheight
\newenvironment{genlayout}{%
\generativewidth=\hsize%
\generativeheight=\vsize%
\setbox0=\hbox\bgroup%
}{%
\egroup%
\directlua{gen.process()}%
}


The new generativelayout.lua:

module(...,package.seeall)


We simply collect everything with a size, that includes hboxes, vboxes, rules, glyphs.

local function get_boxes(parent)
local boxes = {}
if n.width or n.height or n.depth then
table.insert(boxes, {
w = n.width,
h = n.height + n.depth,
box = node.copy(n),
})
end
end
return boxes
end


The algorithm, largely as implemented by michal.h21

local function findNode(n, w, h)
if n.used then
local right = findNode(n.right, w, h)
if right then
return right
else
return findNode(n.down, w, h)
end
elseif w <= n.w and h <= n.h then
n.used = true
n.down  = { x = n.x,     y = n.y + h, w = n.w,     h = n.h - h }
n.right = { x = n.x + w, y = n.y,     w = n.w - w, h = h       }
return n
else
return nil
end
end

local function binpack_tree(boxes)
table.sort(boxes, function(a, b) return a.h > b.h end)
local root = {
x = 0,
y = 0,
w = tex.dimen['generativewidth'],
h = tex.dimen['generativeheight']
}
for _, v in ipairs(boxes) do
local n = findNode(root, v.w, v.h)
if n then
v.x = n.x
v.y = n.y
end
end
return boxes
end


Instead of the picture environment we build \vbox{\vskip<y> \hbox{\hskip<x> <node>}} to position a node at (<x>,<y>). The resulting node has zero size.

local function shift_by(n, w)
n.width = 0
n.height = 0
n.depth = 0
local g = node.new('glue', 0)
g.spec = node.new('glue_spec')
g.spec.width = w
return n
end

local function position_node(n, x, y)
n = node.hpack(n)
n = shift_by(n, x)
n = node.vpack(n)
n = shift_by(n, -y)
return n
end


Position all boxes, packing them into a root box of minimal size.

local function output(boxes)
local w = 0
local h = 0
for _, b in ipairs(boxes) do
if b.x and b.y then
-- add node to the list
local n = position_node(b.box, b.x, b.y + b.box.depth)
else
end
-- track extents
if b.x + b.w > w then w = b.x + b.w end
if b.y + b.h > h then h = b.y + b.h end
end
end
-- natural size was zero
end
end


The entry point: Like in the original code we could call something instead of binpack_tree to get a different layout.

function process()
local boxes = get_boxes(tex.box[0])
binpack_tree(boxes)
output(boxes)
end


The test file generates a few boxes etc, notice we just throw any content into the genlayout environment; also notice how the rule depth is no issue.

\documentclass{article}
\usepackage{generativelayout}
\newcounter{piece}
\def\X#1#2{%
\fbox{%
\vbox to #2{\vfill\hbox to #1{\hfill%
\stepcounter{piece}%
\thepiece%
\hfill}\vfill}}
}
\begin{document}
\begin{figure}\hfil
\begin{genlayout}
\X{2cm}{3cm}\X{2cm}{6cm}\X{3cm}{2cm}
\X{2cm}{3cm}\X{4cm}{3cm}\X{1cm}{4cm}
\X{3cm}{3cm}\X{2cm}{5cm}\X{2cm}{6cm}
\rule[-5mm]{1cm}{1cm}
\Huge Hello!
\end{genlayout}
\caption{My Rectangles}
\end{figure}
\end{document}


The output:

• this seems to fix issues in my code, thanks :) – michal.h21 Mar 31 '15 at 8:30