@mark1russell7/packing

Rectangle packing for layouts: a guillotine row packer and a skyline packer that place rectangles in an outer rectangle.

npm i @mark1russell7/packing

import { pack, Rect } from "@mark1russell7/packing";

const rects = [[30, 10], [20, 20], [10, 5]].map(([w, h]) => {
  const r = new Rect<string>();
  r.size.set(w, h);
  return r;
});
const outer = pack(rects);
outer.size; // the size of the layout
rects[0].position; // the place of the first rectangle

Without fixed sizes, the outer rectangle grows until all rectangles fit. With fixedWidth, the width stays. With fixedSize, a rectangle that does not fit stays unpacked.

Strategies

pack sets the width of the outer rectangle, and then packs with a strategy:

pack(rects, outer, { strategy: "skyline", sortOrder: "area-desc" });

Without strategy, a fixed size uses the pick of SELECT_TABLE: packRows, or packMaxRects with the rule bl. Each other container uses packRows. defaultLayoutOf gives the choice. This default starts in 0.3.0. For the output of the versions before 0.3.0, give strategy: "rows".

• packRows: a guillotine row packing. It fills the space under the short rectangles of each row.
• packSkyline: each rectangle goes to the lowest place where it fits. It packs around a locked rectangle.
• packShelf: it fills rows left to right in the sort order, and goes around each locked rectangle. With the sort order input, the rows read in your order.

Since 0.2.4, packShelf and the strategy shelf have the option fit. SHELF_FITS lists its values. Without fit, the shelf packing does not change.

pack(rects, outer, { strategy: "shelf", fit: "best" });

• fit: "next": each rectangle uses only the open shelf. A short rectangle can also stack above a shorter rectangle.
• fit: "first": each rectangle goes on the first shelf from the top where it fits.
• fit: "best": each rectangle goes on the shelf with the least height left over above it.
• With a fit, the shelves open only in the free spans of each container shape. docs/PACKER.md tells the rules.

Since 0.2.5, packMaxRects and the strategy maxrects pack with a list of maximal free rectangles. MAXRECTS_RULES lists the rules of the option rule.

pack(rects, outer, { strategy: "maxrects", rule: "cp" });

• rule: "bssf" (the default): the free rectangle with the smallest leftover short side. Its move is move.bssf.
• rule: "blsf": the free rectangle with the smallest leftover long side. Its move is move.blsf.
• rule: "baf": the free rectangle with the smallest leftover area. Its move is move.baf.
• rule: "bl": the highest place, then the leftmost place. Its move is move.split, a box that cuts 2 free rectangles or more.
• rule: "cp": the place that touches the most length of edges. Its move is move.cp.
• The move of each rule other than bl counts a box when the rule chooses a place that bl does not choose.
• A shape that is not a rectangle gets bands. The option bandHeight sets their largest height. The default is the height divided by MAXRECTS_BANDS.

Since 0.2.6, packPortfolio packs an input with each member and keeps the best output. It is opt-in, and no default uses it.

const { output, winner } = packPortfolio(["skyline", "shelf"]).pick(input);

• The pick is selectBest of @mark1russell7/layout-contract on PORTFOLIO_LEVELS: the hard breaks, then pack.overflow.excessArea, then pack.fill.
• The trace of the output gets the stage portfolio with the measure move.pick.
• outputHash gives the hash of the placements of an output, as the bench records have it.

Since 0.2.7, the strategy portfolio packs an input with the set of its cell. It is opt-in, and no default uses it.

const output = packWith("portfolio", input); // the default member count of the cell
const cell = portfolioCell(input); // { shape: "rect", count: "100", spread: "uniform" }

• portfolioCell gives the container shape, the band of the item count and the band of the size spread.
• PORTFOLIO_SETS gives the sets of 1, 2 and 3 members of each cell. The bench records of one run gave them.
• Without options, the default member count of the cell runs. The output is a function of the input only.
• The option k (2 or 3) runs each member of the set of k. The option budgetMs is an opt-in time limit.
• The option members sets a fixed list of members. The option key sets the measures of the pick after the hard breaks.

The function aspectFit wraps a strategy for a container of free size. It is opt-in, and no default uses it.

const fit = aspectFit(strategy("maxrects"), { targetAspect: 16 / 9 });
const output = packWith("aspect-fit", input, { strategy: "maxrects", options: { rule: "bl" } });

• A container of fixed size gives the output of the wrapped strategy, with no change.
• For a free size, it packs at the widths of ASPECT_FIT_FACTORS around the target aspect, and at the size of the wrapped strategy.
• The pick uses ASPECT_FIT_LEVELS: the hard breaks, then pack.overflow.excessArea, then pack.aspectError, then pack.area.
• The target is targetAspect, else aspect of the container, else 1. docs/PACKER.md tells the widths.

The strategy restarts packs with one member in some random orders, and keeps the best output. It is opt-in, and no default uses it.

const output = packWith("restarts", input, { member: "rows", iterations: 16, perturb: "swap" }, 7);

• Restart 0 is the member in its own order. Thus the result is not worse than the member on the key of PORTFOLIO_LEVELS.
• Each later restart changes the order with swap, shuffle-blocks or shuffle. The option strength sets the share of the positions that move.
• The same seed gives the same output. The cost is iterations packs of the member. docs/PACKER.md tells each option.

Both functions also work alone, in an outer rectangle with a width that you set. They do not change the width.

A locked rectangle keeps its position. packSkyline and packShelf put the other rectangles around it. packRows only keeps its position.

The sort orders are height-desc (the default), height-asc, width-desc, area-desc, perimeter-desc, long-side-desc, short-side-desc, side-diff-desc, ratio-desc, diagonal-desc and input. SORT_ORDERS lists them. compareRects gives the comparator of one, and sortKey gives the key of a box.

The order input keeps the order of your array. Use it for a ranked list. packRows then fills no gaps, so the rows read in your order: left to right, and top to bottom. packSkyline places the rectangles in your order, but a later rectangle can go higher than an earlier one. For a ranked list with locked rectangles, use packShelf.

Treemaps

treemapSliceDice, treemapSquarified, treemapStrip, treemapPivotSplit, treemapPivotMiddle, treemapPivotSize and treemapSpiral cut a rectangle into cells, one cell for each leaf of a list or a tree. The area of each cell is in proportion to the weight of its leaf. treemapPack puts each box at the center of its cell, and scales the cells until each box fits. These functions are standalone. They are not strategies of pack or of the registry.

import { treemapSquarified } from "@mark1russell7/packing";

const cells = treemapSquarified(
  [{ id: "a", weight: 6 }, { id: "b", weight: 3 }, { id: "c", weight: 1 }],
  { x: 0, y: 0, w: 400, h: 300 },
);

Free width

packFree searches the width. It tries many widths with one strategy of pack, and keeps the width with the lowest objective: the area of the bounding box times 1 + aspectWeight * aspectError.

import { packFree } from "@mark1russell7/packing";

const result = packFree(rects, undefined, { strategy: "skyline", aspect: 16 / 9 });
result.outer.size; // the chosen size
result.fill; // the area of the rectangles divided by the area of the box
result.aspectError; // the distance from the target aspect, on a log scale
result.tried; // each width that the search tried, with its objective

• aspect is the target: the width divided by the height. The default is 1, a square.
• aspectWeight sets the weight of the aspect. With 0, only the area counts.
• The search is deterministic. The same input gives the same result.

Pushes and measurements

pushCascade moves the rectangles that a placed rectangle overlaps, and the rectangles that those overlap in turn:

const moved = pushCascade(dropped, cards, { gap: 8 });

• Each shove takes the axis of the smaller overlap, away from the pusher. The cascade goes outward, and a rectangle does not go past 0.
• The placed rectangle and each locked rectangle stay. maxShoves limits the work.

packingMetrics measures a packing: the hull and its aspect, the rows and the raggedness of the right side. It also gives the part of the hull that the rectangles cover (utilization), and the widest rectangle against the median.

const { utilization, raggedness, rows } = packingMetrics(Rect.packed(rects));

The Packer interface

Each strategy has one interface: pack(input, options, context). The input is a PackInput: a container, items, obstacles and a gap. The output is a PackOutput. The output does not change the input.

import { checkHard, packWith, type PackInput } from "@mark1russell7/packing";

const input: PackInput = {
  container: { w: 400, fixed: "width", inset: 8 },
  gap: 4,
  items: [
    { id: "a", w: 120, h: 40, margin: 2 },
    { id: "pin", w: 60, h: 60, x: 200, y: 8, locked: true },
    { id: "b", w: 80, h: 30 },
  ],
  obstacles: [{ id: "logo", region: { kind: "rect", x: 300, y: 0, w: 100, h: 50 } }],
};
const output = packWith("shelf", input, { sortOrder: "input" });
output.placements; // the position of each item
output.size; // the size of the container
checkHard(input, output); // { "no-overlap": 0, "in-container": 0, "locked-kept": 0, complete: 0 }

• The registry strategies has rows, skyline, shelf, push, maxrects, guillotine, bottom-left and best-fit. strategy(id) gives one, and packWith(id, input, options, seed) packs with it.
• bottom-left slides each box down and left, so it does not jump into a closed hole. best-fit puts the widest box that fits into the lowest gap. They are not in pack, in a default or in SELECT_TABLE.
• packDefault(input, seed) packs with DEFAULT_STRATEGY, the composite strategy select. It passed the win test against rows on two fresh-seed corpora.
• fixed is size, width, height or none. A fixed height turns the axes. The value none uses the size search logSweep, which wraps packFree.
• Each strategy declares its cells in supports. cellOf(input) gives the cell of an input. A strategy throws UnsupportedCell for an input outside its cells.
• Only maxrects accepts a turnable item, and it turns items only with rotate: true. The other strategies give UnsupportedCell for a turnable item.
• No strategy reads groups or packs shapes. A group or a shape gives UnsupportedCell.
• checkHard counts the breaks of the hard rules: no-overlap, in-container, locked-kept and complete. It reads the true shape of each obstacle, as packHard of @mark1russell7/layout-contract does.
• fromRects and toRects connect the interface to the Rect objects.

docs/PACKER.md in the repository gives the interface in full.

Import one strategy

Each single strategy has its own subpath. A bundler then adds only the code of the strategy that you import.

import { createContext, maxrects, type PackInput } from "@mark1russell7/packing/maxrects";

const input: PackInput = { container: { w: 300, fixed: "width" }, items: [{ id: "a", w: 120, h: 40 }, { id: "b", w: 80, h: 30 }] };
const output = maxrects.pack(input, { ...maxrects.defaults, rule: "bl" }, createContext(0));

• The subpaths are rows, skyline, shelf, push, maxrects, guillotine, hole-degree and circle-quasi-physical.
• Each subpath exports the strategy, its options type, its packer function, Rect and createContext.
• The subpath default exports packDefault and DEFAULT_STRATEGY. It gets only select, rows and maxrects.
• The root import has the same names as before. Its npm build keeps all strategies in one bundle.
• The composite strategies and packWith find their members by id. Thus they get all strategies of the registry.

The strategy space

packSpace gives the strategies of the package as data: a StrategySpace of the schema strategy-space/1 of @mark1russell7/layout-contract.

import { packConfig, packSpace } from "@mark1russell7/packing";

const output = packConfig(input, packSpace.named!["maxrects-cp"]!, 0);

• The space has 5 stages: order, size-search, placement, local-search and combine. Each option gives its params with their ranges.
• The stage combine has the meta options portfolio, cell-portfolio, select, aspect-fit and restarts. Each meta config has members.
• named has each id of the registry and each entry of the benchmark. The output of a named config is equal to the output of its strategy.
• The named config pack is the choice of pack without a strategy: select with the param table at pack, the table PACK_DEFAULT_TABLE.
• configOfStrategy(id, options) gives the point of a strategy with its options: { ok: true, config }, or { ok: false, reason }.
• packConfig(input, config, seed) checks the config with checkConfig and packs it with the strategies of the registry.
• Each option supports only the shape kind rect. packConfig throws UnsupportedShape for a polygon, circle or free item.
• PACK_SPACE_OPTIONS gives the place in the space of each option of each strategy: a stage, a param or the members of a meta option.
• PACK_SPACE_LEFT_OUT gives the options that the space does not hold, with the reason of each.

More

• The repository: the source, the tests and the roadmap.
• This package was @mark1russell7/render-pack before 0.1.0. render-pack re-exports this package for one more minor, and then it is deprecated.

The package is ESM, has TypeScript declarations, and works in Node.js 22.12 or later and in browsers. The license is MIT.