# 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`).

- 2022
- Rectpacking (Updated)
- Edge Routing with Libavoid
- 2023
- Layered: Constraining the Model
- Top-down Layout: Zoom in the Layout Process
- 2024
- Layer Unzipping