Engineer at Mapbox, creator of Leaflet, algorithms geek, open source enthusiast, musician, father of twin girls, Ukrainian. 🇺🇦
Public
Edited
Aug 30, 2023
Paused
1 fork
48 stars
Finding a short route through points without returning back with 2-optCollatz conjecture (3x + 1)Robust Arithmetic in Computational GeometryKinematics of Reverse Angle ParkingDrawing logarithmic spiralsApproximating Geometric SlerpEdgebreaker, the Heart of Google DracoFast Icosphere MeshHilbert Curve PackingFast and simple prime generatorFast Distance TransformCalculating Pi digitsAdaptive Concave HullMARTINI: Real-Time RTIN Terrain Mesh
Simple rectangle packing
Also listed in…
Algorithms
result = {
// calculate total box area and maximum box width
let area = 0;
let maxWidth = 0;
for (const box of boxes) {
area += box.w * box.h;
maxWidth = Math.max(maxWidth, box.w);
}
// sort the boxes for insertion by height, descending
boxes.sort((a, b) => b.h - a.h);
// aim for a squarish resulting container,
// slightly adjusted for sub-100% space utilization
const startWidth = Math.max(Math.ceil(Math.sqrt(area / 0.95)), maxWidth);
// start with a single empty space, unbounded at the bottom
const spaces = [{x: 0, y: 0, w: startWidth, h: Infinity}];
const packed = [];
for (const box of boxes) {
// look through spaces backwards so that we check smaller spaces first
for (let i = spaces.length - 1; i >= 0; i--) {
const space = spaces[i];
// look for empty spaces that can accommodate the current box
if (box.w > space.w || box.h > space.h) continue;
// found the space; add the box to its top-left corner
// |-------|-------|
// | box | |
// |_______| |
// | space |
// |_______________|
packed.push(Object.assign({}, box, {x: space.x, y: space.y}));
if (box.w === space.w && box.h === space.h) {
// space matches the box exactly; remove it
const last = spaces.pop();
if (i < spaces.length) spaces[i] = last;
} else if (box.h === space.h) {
// space matches the box height; update it accordingly
// |-------|---------------|
// | box | updated space |
// |_______|_______________|
space.x += box.w;
space.w -= box.w;
} else if (box.w === space.w) {
// space matches the box width; update it accordingly
// |---------------|
// | box |
// |_______________|
// | updated space |
// |_______________|
space.y += box.h;
space.h -= box.h;
} else {
// otherwise the box splits the space into two spaces
// |-------|-----------|
// | box | new space |
// |_______|___________|
// | updated space |
// |___________________|
spaces.push({
x: space.x + box.w,
y: space.y,
w: space.w - box.w,
h: box.h
});
space.y += box.h;
space.h -= box.h;
}
break;
}
yield {packed, spaces};
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
