6

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
3

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 = {}
  for n in node.traverse(parent.head) do
    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
    n.head = node.insert_before(n.head, n.head, g)
    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
  local head = nil
  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)
      if head then
        node.insert_after(head, head, n)
      else
        head = n
      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
  if head then
    head = node.hpack(head)
    -- natural size was zero
    head.width = w
    head.height = h
    node.write(head)
  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:

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.