Rectpacking (Updated)

By Sören Domrös, August 31, 2022, updated January 4, 2024

The rectpacking algorithm was introduced to solved common problems with the box algorithm, which cannot stack boxes in a row. The idea is to form stacks with subrows inside rows, while the size of a row is always dominated by a highest rectangle to provide a visual anchor point to “read” the rows from left to right.

Since it was a common use case of the box algorithm to add a priority to order the rectangles rectpacking uses the model order (which corresponds to the input order of the rectangles) as a criterion. By enabling interactive layout and setting desired positions for nodes, this order can be changed without changing the order in the input graph.

Box algorithm:

Rectpacking algorithm:

Algorithm

The algorithm is divided into several phases.

Width approximation

Same as the box algorithm rectpacking packs rectangles inside a given aspect ratio. As a first step this problem is transformed in a strip packing problem by approximating the width.

The width can also be specified by setting a target width ) (ELK 0.9.0 target width).

Different strategies can be chosen for width approximation based on which goal (ELK 0.9.0 goal) the greedy algorithm should prioritize.

Since the approximated width is mainly responsible for the line breaks between the rows that are formed by rectpacking, one can make sure that a rectangle is placed in a new row (since ELK 0.9.0).

GREEDY width approximation (0.9.0) may yield the following graph:

Placement

Rectangles are placed in rows similar to the box algorithm. Per default the row height does not change after this step. By enabling row height re-evaluation (since ELK 0.9.0) the row height might change by investing more computation time. After placement the graph looks like this:

Compaction

After placement the rectangles are compacted to from stack with subrows inside the rows. This can also be disabled (ELK < 0.9.0), however, this is not recommended.

In ELK 0.9.0 this step is part of the placement step and done via the default packing.strategy. Only placement can be done by setting the packing.strategy to SIMPLE.

Whitespace Elimination

Rectangles can fill potential whitespace (ELK 0.9.0 whiteSpaceElimination.strategy set to EQUAL_BETWEEN_STRUCTURES).

The drawing can also be configured to fill whitespace such that the drawing has the desired aspect ratio (ELK 0.9.0 . whiteSpaceElimination.strategy set to TO_ASPECT_RATIO).