Public
Edited
Jun 25, 2023
function placeLabels(placement, startBound, endBound, labelSize) {
// Sort the array in ascending order.
placement.sort((a, b) => a - b);
let N = placement.length;
let M = endBound - startBound + 1; // size of the bounds
let dp = Array(N)
.fill(0)
.map(() => Array(M).fill(Infinity)); // DP table
let path = Array(N)
.fill(0)
.map(() => Array(M).fill(0)); // path tracking table
// Fill the DP table for the first label
for (let j = 0; j < M; j++) {
dp[0][j] = Math.abs(placement[0] - (startBound + j));
}
// Fill the DP table for the rest of the labels
for (let i = 1; i < N; i++) {
let minPrevRow = { val: Infinity, pos: -1 };
for (let j = 0; j < M; j++) {
while (minPrevRow.pos < j - labelSize) {
minPrevRow.pos++;
minPrevRow.val = Math.min(minPrevRow.val, dp[i - 1][minPrevRow.pos]);
}
dp[i][j] = minPrevRow.val + Math.abs(placement[i] - (startBound + j));
path[i][j] = minPrevRow.pos;
}
}
// Find the minimum cost and its position for the last label
let minCost = Infinity,
pos = -1;
for (let j = 0; j < M; j++) {
if (dp[N - 1][j] < minCost) {
minCost = dp[N - 1][j];
pos = j;
}
}
// Trace back the placement decisions
let newPlacement = [];
for (let i = N - 1; i >= 0; i--) {
newPlacement[i] = startBound + pos;
pos = path[i][pos];
}
return newPlacement;
}
placements = [2, 4, 5, 6, 7, 10, 11, 12]
startBound = 0
endBound = 12
boxSize = 1
placeLabels(placements, startBound, endBound, boxSize)
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.
