2b:null 2c:["$","title",null,{"children":"Hyperbolic Tree Viewer Remix | Lao | Observable"}] 31:T9aab,const ht_chart = (() => { // ─── tweakables ─────────────────────────────────────────────────────────── const HT_CONFIG = { // Colour. Any array of CSS colours works: d3.schemeTableau10, // d3.schemeCategory10, d3.schemeSet2, d3.schemePaired, or a hand-written // list. The length of the scheme decides how many clusters get a colour. scheme: [ '#d93d4d', '#728997', '#3fb447', '#f2c210', '#0068b5', '#f8802a', '#813978', '#64c0db', '#e658a8', '#aede27', '#8295ca', '#0098a0', '#bc8fd1', '#9f7920', '#9cb366', '#8b2505', '#a1e2c0', '#6b9072', '#f29baf', '#cdc2a1', '#795ad3', '#22208e', '#00c8b0', '#504f4f', '#007356', '#895c6a', '#b88871', ], maxGroups: null, // null → one cluster per colour in the scheme otherColor: "#a9a9a9", // leftover branches + the nodes above the clusters otherLabel: "Other", minGroupFraction: 0.2, // a cluster below this × the ideal size is leftover // Detail. How hard to thin the parts of the tree you are not looking at. // All of this fades out on its own as the view zooms back out. crampRho: 5, // past this hyperbolic radius a node is squashed localityRange: [0.2, 0.8], // squashed fraction where thinning starts / peaks localityEase: 0.15, // per-frame approach rate for that ramp; 1 = instant stickyRelief: 0.7, // spacing a node already on screen needs to stay kinFalloff: 1.5, // how fast protection drops off per level of kinship focalHysteresis: 2.5, // how much nearer a rival must be to take the focus nearFreeRho: 2, // full detail out to here nearFalloffRho: 2.5, // how fast detail falls off past that spacingMultRange: [1, 2.5], // dot spacing multiplier, top priority → bottom cullRho: 12, // hyperbolic radius past which a node is off-disk linkColor: "#999", linkOpacity: 0.35, // Layout baseSpan: 4.4, // hyperbolic radius the tree spans at spread = 1 // Viewer width: 700, height: 700, renderBudget: 12000, dotSpacingPx: 2, // lower = denser; the main lever on how many draw dotRadius: 3, fadeEase: 0.22, // per-frame opacity approach as nodes enter / leave labelRadius: 0.3, labelSpacingPx: [30, 10], labelBudget: 40, spreadStep: 1.1, spreadRange: [0.35, 5], spreadDuration: 260, animDuration: 500, hitRadiusPx: 40, panLimitDepth: null, // null → one level above the deepest leaves showControls: true }; function ht_cx(re, im = 0) { return { re, im }; } function ht_add(a, b) { return { re: a.re + b.re, im: a.im + b.im }; } function ht_mul(a, b) { return { re: a.re * b.re - a.im * b.im, im: a.re * b.im + a.im * b.re }; } function ht_conj(a) { return { re: a.re, im: -a.im }; } function ht_div(a, b) { const d = b.re * b.re + b.im * b.im; return { re: (a.re * b.re + a.im * b.im) / d, im: (a.im * b.re - a.re * b.im) / d }; } function ht_abs2(a) { return a.re * a.re + a.im * a.im; } const ht_identity = { a: ht_cx(1, 0), b: ht_cx(0, 0) }; function ht_apply(M, z) { const num = ht_add(ht_mul(M.a, z), M.b); const den = ht_add(ht_mul(ht_conj(M.b), z), ht_conj(M.a)); return ht_div(num, den); } function ht_translateFrom(f) { const r2 = Math.min(0.999999, ht_abs2(f)); const s = 1 / Math.sqrt(Math.max(1e-9, 1 - r2)); return { a: ht_cx(s, 0), b: ht_cx(-f.re * s, -f.im * s) }; } function ht_layout(root, { k = 2.2, step = null, weight = (d) => d.value, rootAngle = -Math.PI / 2, maxAperture = Math.PI * 0.98 } = {}) { root.count(); const d = step ?? (2 * k) / Math.max(1, root.height); const rStep = Math.tanh(d / 2); const sinhStep = Math.sinh(d); const sN = 1 / Math.sqrt(1 - rStep * rStep); function childAperture(beta) { const h = Math.asinh(sinhStep * Math.sin(beta)); const gamma = Math.asin(Math.max(-1, Math.min(1, Math.cos(beta) / Math.cosh(h)))); const A = Math.PI - gamma - 2 * Math.atan(Math.exp(-h)); return Math.max(1e-4, Math.min(maxAperture, A)); } root.z0 = { re: 0, im: 0 }; root._far = 1; root._fai = 0; root._fbr = 0; root._fbi = 0; root._forward = rootAngle; root._aperture = Math.PI; root.eachBefore((u) => { if (!u.children || !u.children.length) return; let total = 0; for (const c of u.children) total += Math.max(1e-9, weight(c)); let a = u._forward - u._aperture; const far = u._far, fai = u._fai, fbr = u._fbr, fbi = u._fbi; for (const c of u.children) { const share = (2 * u._aperture * Math.max(1e-9, weight(c))) / total; const beta = share / 2; const theta = a + beta; a += share; const pr = rStep * Math.cos(theta), pi = rStep * Math.sin(theta); const nr = far * pr - fai * pi + fbr; const ni = far * pi + fai * pr + fbi; const dr = fbr * pr + fbi * pi + far; const di = fbr * pi - fbi * pr - fai; const q = dr * dr + di * di; c.z0 = { re: (nr * dr + ni * di) / q, im: (ni * dr - nr * di) / q }; const ar = sN * (far + (fbr * pr + fbi * pi)); const ai = sN * (fai + (fbi * pr - fbr * pi)); const br = sN * nr, bi = sN * ni; const nrm = Math.sqrt(Math.max(1e-9, ar * ar + ai * ai - br * br - bi * bi)); c._far = ar / nrm; c._fai = ai / nrm; c._fbr = br / nrm; c._fbi = bi / nrm; c._forward = theta; c._aperture = childAperture(beta); } }); return root.descendants(); } function ht_easeInOutCubic(t) { return t < 0.5 ? 4 * t * t * t : 1 - Math.pow(-2 * t + 2, 3) / 2; } function ht_smoothstep(t) { return t <= 0 ? 0 : t >= 1 ? 1 : t * t * (3 - 2 * t); } function ht_viewer4(nodes, { width = 700, height = 700, renderBudget = 12000, dotSpacingPx = 1.5, labelRadius = 0.3, labelSpacingPx = [64, 15], spread = 1, spreadStep = 1.1, spreadCompression = 1, spreadDuration = 260, spreadRange = [0.35, 5], relayout = null, labelBudget = 40, domainR = 1.05, label = (d) => d.data.name ?? d.data.id ?? String(d.data), animDuration = 500, rootClampR = 0.95, panLimitDepth = null, cullRho = 12, linkColor = "#999", linkOpacity = 0.35, zoomRegionR = 1.0, dotRadius = 2, fadeEase = 0.22, hitRadiusPx = 40, showControls = true, scheme = d3.schemeObservable10 ?? d3.schemeTableau10, maxGroups = null, otherColor = "#bfbfbf", otherLabel = "Other", minGroupFraction = 0.2, crampRho = 5, localityRange = [0.2, 0.8], localityEase = 0.15, stickyRelief = 0.7, kinFalloff = 1.5, focalHysteresis = 2.5, nearFreeRho = 2, nearFalloffRho = 2.5, spacingMultRange = [1, 2.5] } = {}) { const G = (() => { const ONE = { re: 1, im: 0 }; const ZERO = { re: 0, im: 0 }; const mul = (a, b) => ({ re: a.re * b.re - a.im * b.im, im: a.re * b.im + a.im * b.re }); const add = (a, b) => ({ re: a.re + b.re, im: a.im + b.im }); const neg = (a) => ({ re: -a.re, im: -a.im }); const conj = (a) => ({ re: a.re, im: -a.im }); const div = (a, b) => { const q = b.re * b.re + b.im * b.im; return { re: (a.re * b.re + a.im * b.im) / q, im: (a.im * b.re - a.re * b.im) / q }; }; const identMat = () => ({ a: ONE, b: ZERO, c: ZERO, d: ONE }); const matMul = (A, B) => ({ a: add(mul(A.a, B.a), mul(A.b, B.c)), b: add(mul(A.a, B.b), mul(A.b, B.d)), c: add(mul(A.c, B.a), mul(A.d, B.c)), d: add(mul(A.c, B.b), mul(A.d, B.d)) }); const matNormalize = (A) => Math.hypot(A.d.re, A.d.im) < 1e-12 ? A : { a: div(A.a, A.d), b: div(A.b, A.d), c: div(A.c, A.d), d: ONE }; const transMat = (t) => ({ a: ONE, b: { re: t.re, im: t.im }, c: conj(t), d: ONE }); const matApplyToOrigin = (A) => div(A.b, A.d); const clampDisk = (z, max = 0.9999) => { const r = Math.hypot(z.re, z.im); return r <= max || r === 0 ? z : { re: (z.re / r) * max, im: (z.im / r) * max }; }; return { neg, identMat, matMul, matNormalize, transMat, matApplyToOrigin, clampDisk }; })(); const SVGNS = "http://www.w3.org/2000/svg"; const rootNode = nodes.find((n) => n.depth === 0); const rhoOf = (r) => 2 * Math.atanh(Math.min(0.999999, r)); const nodeIndex = new Map(nodes.map((n, i) => [n, i])); const spacingData = (dotSpacingPx * 2 * domainR) / (Math.min(width, height) - 40); const gridN = Math.max(1, Math.ceil(2 / spacingData) + 1); const grid = new Int32Array(gridN * gridN); const pool = nodes.map((n) => ({ n, x: 0, y: 0, r2: 0, op: 0, keep: false, stick: false, labeled: false, stickLabel: false })); const order = nodes .map((_, i) => i) .sort((a, b) => ((nodes[b].value ?? 1) - (nodes[a].value ?? 1)) || (a - b)); const rank = new Int32Array(nodes.length); for (let j = 0; j < order.length; j++) rank[order[j]] = j; let stickList = []; // Scratch for the per-frame detail scoring, sized once. byDepth walks the // tree parent-first whatever order descendants() came back in. const parentIdx = new Int32Array(nodes.length).fill(-1); const depthOf = new Int32Array(nodes.length); for (let i = 0; i < nodes.length; i++) { depthOf[i] = nodes[i].depth; if (nodes[i].parent) parentIdx[i] = nodeIndex.get(nodes[i].parent); } const byDepth = Int32Array.from(nodes.keys()).sort((a, b) => depthOf[a] - depthOf[b]); const impOf = new Float32Array(nodes.length); { const span = Math.log1p(Math.max(1, rootNode.value ?? 1)); for (let i = 0; i < nodes.length; i++) impOf[i] = Math.log1p(nodes[i].value ?? 1) / span; } const DETAIL_BUCKETS = 64; const onPath = new Uint8Array(nodes.length); const shareBuf = new Int32Array(nodes.length); const needBuf = new Float32Array(nodes.length); const bucketOf = new Uint8Array(nodes.length); const bucketCount = new Int32Array(DETAIL_BUCKETS); const bucketCursor = new Int32Array(DETAIL_BUCKETS); const orderBuf = new Int32Array(nodes.length); const crampR2 = Math.tanh(crampRho / 2) ** 2; const labelPadX = (labelSpacingPx[0] * 2 * domainR) / (Math.min(width, height) - 40); const labelPadY = (labelSpacingPx[1] * 2 * domainR) / (Math.min(width, height) - 40); const labelR2 = labelRadius * labelRadius; const maxDepth = nodes.reduce((m, n) => Math.max(m, n.depth), 0); const limitDepth = Math.max(0, Math.min(maxDepth, panLimitDepth ?? maxDepth - 1)); const kinLut = new Float64Array(maxDepth + 1); let focalPrev = -1; let locality = 0, localitySettling = false; const cullR2 = Math.tanh(cullRho / 2) ** 2; let treeRho = 0, panLimitR = 0.9999; function measureTree() { treeRho = 0; let lim = 0; for (const n of nodes) { const r = Math.hypot(n.z0.re, n.z0.im); treeRho = Math.max(treeRho, rhoOf(r)); if (n.depth === limitDepth) lim = Math.max(lim, r); } panLimitR = Math.min(0.9999, lim > 1e-6 ? lim : Math.tanh(treeRho / 2)); } measureTree(); let M = ht_identity; let Minv = G.identMat(); let focus = { re: 0, im: 0 }; let wheelCursor = null; let morph = null; const morphFrom = new Float64Array(nodes.length * 2); const morphTo = new Float64Array(nodes.length * 2); const spreadPotential = (v) => { const u = Math.log(v); return u <= 0 ? u : u + (spreadCompression * u * u) / 2; }; const spreadFromPotential = (P) => { if (P <= 0) return Math.exp(P); const c = spreadCompression; return Math.exp(c > 0 ? (Math.sqrt(1 + 2 * c * P) - 1) / c : P); }; const solveFocus = (q, t) => { const ar = t.re * q.re - t.im * q.im; const ai = t.re * q.im + t.im * q.re; const det = 1 - (ar * ar + ai * ai); if (!(det > 1e-12)) return { re: q.re, im: q.im }; const rx = q.re - t.re, ry = q.im - t.im; return G.clampDisk({ re: ((1 + ar) * rx + ai * ry) / det, im: (ai * rx + (1 - ar) * ry) / det }); }; const spreadTick = (v, dir) => spreadFromPotential(spreadPotential(v) + dir * Math.log(spreadStep)); let animToken = 0; // Cut the tree into clusters of roughly equal leaf count, one per colour. // A cut is "every maximal node holding at most tau leaves", so the cut sits // at a different depth in each branch: heavy branches keep splitting, light // ones stay whole. Each candidate tau is scored on how much of the tree it // colours, with each cluster's contribution capped at the ideal size so // balance is rewarded over one giant cluster. Whatever is left over — // usually many small branches that only meet at the root, plus the nodes // above the clusters — shares the grey bucket. const K = Math.max(1, maxGroups ?? scheme.length); const leaves = (n) => n.value ?? 1; const totalLeaves = Math.max(1, leaves(rootNode)); const idealSize = totalLeaves / K; const minSize = minGroupFraction * idealSize; const cutAt = (tau) => { const out = []; const stack = [rootNode]; while (stack.length) { const n = stack.pop(); if (leaves(n) <= tau || !n.children || !n.children.length) out.push(n); else for (let i = n.children.length - 1; i >= 0; i--) stack.push(n.children[i]); } return out; }; let taus = Array.from(new Set(nodes.map(leaves))) .filter((v) => v >= minSize) .sort((a, b) => a - b); if (!taus.length) taus = [totalLeaves]; if (taus.length > 96) { const step = (taus.length - 1) / 95; taus = Array.from(new Set( Array.from({ length: 96 }, (_, i) => taus[Math.round(i * step)]) )); } const dfsIndex = new Map(nodes.map((n, i) => [n, i])); let picked = null; for (const tau of taus) { const sel = cutAt(tau) .filter((n) => leaves(n) >= minSize) .sort((a, b) => leaves(b) - leaves(a)) .slice(0, K); const score = sel.reduce((s, n) => s + Math.min(leaves(n), idealSize), 0); const cover = sel.reduce((s, n) => s + leaves(n), 0); if (!picked || score > picked.score + 1e-9 || (score > picked.score - 1e-9 && cover > picked.cover)) { picked = { score, cover, sel }; } } const groups = picked.sel.sort((a, b) => dfsIndex.get(a) - dfsIndex.get(b)); // Name each cluster by its last path segment, falling back to the full // label where two clusters would otherwise read the same. const shortOf = (n) => String(label(n)).split(/[./]/).pop(); const shortSeen = new Map(); for (const g of groups) shortSeen.set(shortOf(g), (shortSeen.get(shortOf(g)) ?? 0) + 1); const catOf = new Map(); const catNode = new Map(); const categories = []; const colorRange = []; groups.forEach((g, i) => { let name = shortSeen.get(shortOf(g)) > 1 ? String(label(g)) : shortOf(g); while (catNode.has(name) || name === otherLabel) name += "\u200b"; categories.push(name); colorRange.push(scheme[i % scheme.length]); catNode.set(name, g); g.each((d) => catOf.set(d, name)); }); for (const n of nodes) if (!catOf.has(n)) catOf.set(n, otherLabel); if (nodes.some((n) => catOf.get(n) === otherLabel)) { categories.push(otherLabel); colorRange.push(otherColor); catNode.set(otherLabel, rootNode); } const container = document.createElement("div"); container.className = "ht-viewer"; container.style.cssText = "display:inline-block;width:fit-content;"; const styleEl = document.createElement("style"); styleEl.textContent = ` .ht-viewer, .ht-viewer * { -webkit-user-select:none; user-select:none; } .ht-viewer g[aria-label="tip"] { pointer-events:none; } .ht-viewer button { font:12px system-ui; } .ht-viewer div[class*="-swatches"] { margin:0 0 4px 0; font-size:10px; min-height:0; } .ht-viewer div[class*="-swatches-wrap"] { display:flex; flex-wrap:wrap; align-items:center; } .ht-viewer [class$="-swatch"] { display:inline-flex; align-items:center; margin-right:0.85em; cursor:pointer; } .ht-viewer [class$="-swatch"]:hover { text-decoration:underline; } .ht-viewer [class$="-swatch"]:focus-visible { outline:1px solid #888; outline-offset:2px; } .ht-viewer [class$="-swatch"] > svg { width:10px; height:10px; margin-right:0.35em; } .ht-viewer .ht-reset { position:absolute; right:14px; bottom:14px; z-index:2; padding:3px 9px; color:#555; background:rgba(255,255,255,0.88); border:1px solid #ccc; border-radius:4px; cursor:pointer; } .ht-viewer .ht-reset:hover { background:#fff; border-color:#999; color:#222; } .ht-viewer .ht-reset:focus-visible { outline:1px solid #888; outline-offset:2px; } `; const legendWrap = document.createElement("div"); legendWrap.style.cssText = "margin:0 0 2px 4px;"; const stage = document.createElement("div"); stage.style.cssText = "position:relative;display:inline-block;"; const figWrap = document.createElement("div"); figWrap.style.cssText = "touch-action:none;cursor:grab;"; stage.append(figWrap); if (showControls) { const resetBtn = document.createElement("button"); resetBtn.className = "ht-reset"; resetBtn.type = "button"; resetBtn.textContent = "Reset view"; resetBtn.addEventListener("click", () => resetView()); stage.append(resetBtn); } container.append(styleEl, legendWrap, stage); let toData = () => ({ re: 0, im: 0 }); let pxPerUnit = 1; let hitList = []; let legendBuilt = false; let lastStats = null; function clampToDisk(x, y, maxR) { const r = Math.hypot(x, y); if (r <= maxR || r === 0) return { x, y, clamped: false }; const s = maxR / r; return { x: x * s, y: y * s, clamped: true }; } function buildPath(list, X, Y) { const out = []; for (const L of list) { out.push( `M${X(L.ax).toFixed(1)},${Y(L.ay).toFixed(1)}L${X(L.bx).toFixed(1)},${Y(L.by).toFixed(1)}` ); } return out.join(""); } function render() { const t0 = performance.now(); const all = pool; stickList.length = 0; const mt = morph ? morph.t : 0; let farCount = 0, focalIdx = 0, focalR2 = Infinity; for (let i = 0; i < nodes.length; i++) { let x, y; if (morph) { const a = morphFrom[2 * i], b = morphFrom[2 * i + 1]; x = a + (morphTo[2 * i] - a) * mt; y = b + (morphTo[2 * i + 1] - b) * mt; } else { const z = ht_apply(M, nodes[i].z0); x = z.re; y = z.im; } const e = all[i]; e.stick = e.keep; e.stickLabel = e.labeled; if (e.keep) stickList.push(i); e.keep = false; e.labeled = false; e.x = x; e.y = y; e.r2 = x * x + y * y; if (e.r2 > crampR2) farCount++; if (e.r2 < focalR2) { focalR2 = e.r2; focalIdx = i; } } // How much of the tree is squashed against the rim right now: near zero // with the whole hierarchy in view, high once you have panned into a // branch or spread the layout out. Everything below scales by it, so a // zoomed-out view keeps the old even treatment. // Eased over frames rather than applied outright: a fast zoom otherwise // switches the thinning on inside two or three frames and dumps a few // hundred nodes at once, which is the pop you see. Spreading the same // change over ~15 frames keeps each step below the noticing threshold. const farFrac = farCount / nodes.length; const localityTarget = ht_smoothstep( (farFrac - localityRange[0]) / Math.max(1e-6, localityRange[1] - localityRange[0]) ); locality += (localityTarget - locality) * localityEase; localitySettling = Math.abs(localityTarget - locality) > 2e-3; if (!localitySettling) locality = localityTarget; // Kinship with the node nearest the centre: 1 across its own subtree, // then a step down per level out to siblings, uncles and so on. share is // the depth of the common ancestor, filled in parent-first. // Hold the incumbent focal node until a rival is clearly nearer, so // slow pans do not flip the whole kinship map back and forth. if (focalPrev >= 0 && focalPrev !== focalIdx && all[focalPrev].r2 < focalR2 * focalHysteresis) focalIdx = focalPrev; focalPrev = focalIdx; const focalNode = nodes[focalIdx]; const focalDepth = focalNode.depth; for (let d = 0; d <= focalDepth; d++) { const kin = focalDepth > 0 ? d / focalDepth : 1; kinLut[d] = kinFalloff === 1 ? kin : Math.pow(kin, kinFalloff); } onPath.fill(0); for (let p = focalNode; p; p = p.parent) onPath[nodeIndex.get(p)] = 1; for (let j = 0; j < byDepth.length; j++) { const i = byDepth[j]; const pi = parentIdx[i]; shareBuf[i] = pi < 0 ? 0 : onPath[pi] ? (onPath[i] ? depthOf[i] : depthOf[pi]) : shareBuf[pi]; } // The same keep score does two jobs: it orders the placement pass, and it // sets how much clear space a node demands. Without the second part the // far side would only lose the race locally and still draw in full, since // the grid is spatial and the crowded rim never competes with the centre. const multSpan = spacingMultRange[1] - spacingMultRange[0]; bucketCount.fill(0); for (let i = 0; i < nodes.length; i++) { const e = all[i]; if (e.r2 >= cullR2) { bucketOf[i] = 0; bucketCount[0]++; continue; } const rho = rhoOf(Math.sqrt(e.r2)); const near = 1 / (1 + Math.max(0, rho - nearFreeRho) / Math.max(1e-6, nearFalloffRho)); // Kinship is a floor, not an average: anything in the branch you are in // keeps full detail however far out it sits, siblings and uncles give // up detail a level at a time, and unrelated nodes fall back to plain // distance. Big subtrees are thinned less, so the far side degrades to // a skeleton you can still see and steer towards. const k = kinLut[shareBuf[i]]; const keep = k + (1 - k) * near; const thin = locality * (1 - keep) * (1 - impOf[i]); needBuf[i] = spacingData * (spacingMultRange[0] + multSpan * thin); const score = impOf[i] + locality * (keep - impOf[i]); const b = Math.min(DETAIL_BUCKETS - 1, Math.max(0, (score * DETAIL_BUCKETS) | 0)); bucketOf[i] = b; bucketCount[b]++; } // Counting sort into buckets, high first, keeping subtree-size order // inside each bucket. At locality 0 that reduces to the old ranking. let acc = 0; for (let b = DETAIL_BUCKETS - 1; b >= 0; b--) { bucketCursor[b] = acc; acc += bucketCount[b]; } for (let j = 0; j < order.length; j++) { const i = order[j]; orderBuf[bucketCursor[bucketOf[i]]++] = i; } const posOf = (n) => all[nodeIndex.get(n)]; const rz = posOf(rootNode); const rc = clampToDisk(rz.x, rz.y, rootClampR); const rootEntry = { n: rootNode, x: rc.x, y: rc.y, r2: rc.x * rc.x + rc.y * rc.y, pinned: rc.clamped, op: 1 }; grid.fill(-1); const isFree = (d, need) => { const gx = ((d.x + 1) / spacingData) | 0; const gy = ((d.y + 1) / spacingData) | 0; const reach = need <= spacingData ? 1 : Math.min(16, Math.ceil(need / spacingData)); const need2 = need * need; const x0 = gx > reach ? gx - reach : 0, x1 = gx + reach < gridN ? gx + reach : gridN - 1; const y0 = gy > reach ? gy - reach : 0, y1 = gy + reach < gridN ? gy + reach : gridN - 1; for (let y = y0; y <= y1; y++) { for (let x = x0; x <= x1; x++) { const h = grid[y * gridN + x]; if (h === -1) continue; const e = all[h]; const dx = e.x - d.x, dy = e.y - d.y; if (dx * dx + dy * dy < need2) return false; } } return true; }; const occupy = (i, d) => { const gx = ((d.x + 1) / spacingData) | 0; const gy = ((d.y + 1) / spacingData) | 0; const k = gy * gridN + gx; if (grid[k] === -1) grid[k] = i; }; // Admitting a node admits every ancestor with it, whether or not they // won their own spacing test. Pruning therefore eats leaves first and // works inwards, and a drawn node always has a drawn parent: no gaps in // the middle of a branch, and no rung of the ladder popping in later. const others = []; const chain = []; const admit = (i) => { chain.length = 0; for (let j = i; j !== -1 && !all[j].keep; j = parentIdx[j]) chain.push(j); for (let c = chain.length - 1; c >= 0; c--) { const j = chain[c]; const d = all[j]; d.keep = true; occupy(j, d); if (d.n !== rootNode) others.push(d); } }; stickList.sort((a, b) => (bucketOf[b] - bucketOf[a]) || (rank[a] - rank[b])); for (let pass = 0; pass < 2; pass++) { const list = pass === 0 ? stickList : orderBuf; for (let j = 0; j < list.length; j++) { if (others.length >= renderBudget - 1) break; const i = list[j]; const d = all[i]; if (d.keep || d.r2 >= cullR2) continue; if (pass === 1 && d.stick) continue; // A node already on screen holds its place at a slacker spacing than // a newcomer needs to take one, so nodes on the edge of colliding // stop flickering in and out frame to frame. if (!isFree(d, pass === 0 ? needBuf[i] * stickyRelief : needBuf[i])) continue; admit(i); } } rootEntry.keep = true; // Selection is a hard in/out, so ease the opacity towards it instead of // snapping. A node that has just been admitted fades up, one that has // just lost its place keeps drawing while it fades down: the churn at the // margin of the visible set stops reading as pop. let fading = false; const dots = []; for (let i = 0; i < nodes.length; i++) { const e = all[i]; const target = e.keep ? 1 : 0; if (e.op !== target) { e.op += (target - e.op) * fadeEase; if (Math.abs(target - e.op) < 0.01) e.op = target; else fading = true; } if (e.op > 0.02 && e.n !== rootNode) dots.push(e); } dots.sort((a, b) => a.r2 - b.r2); const drawn = [...dots, rootEntry]; const linkList = []; for (const d of dots) { const par = d.n.parent; if (!par) continue; const pp = par === rootNode ? rootEntry : posOf(par); linkList.push({ ax: pp.x, ay: pp.y, bx: d.x, by: d.y, op: Math.min(d.op, pp.op) }); } const labelData = []; const tryLabel = (d) => { for (const q of labelData) { if (Math.abs(q.x - d.x) < labelPadX && Math.abs(q.y - d.y) < labelPadY) return; } labelData.push(d); d.labeled = true; }; const centerEntry = dots[0] && dots[0].r2 < rootEntry.r2 ? dots[0] : rootEntry; tryLabel(centerEntry); for (let pass = 0; pass < 2; pass++) { for (const d of dots) { if (labelData.length >= labelBudget - 1) break; if (d.r2 > labelR2) break; if (d.labeled) continue; if (pass === 0 ? !d.stickLabel : d.stickLabel) continue; tryLabel(d); } } if (!rootEntry.labeled) labelData.push(rootEntry); const lastRenderMs = performance.now() - t0; const figEl = Plot.plot({ width, height, margin: 20, x: { domain: [-domainR, domainR], axis: null }, y: { domain: [-domainR, domainR], axis: null }, color: { type: "categorical", domain: categories, range: colorRange, legend: false }, opacity: { domain: [0, 1], range: [0, 1], clamp: true }, marks: [ Plot.dot(dots, { x: "x", y: "y", r: dotRadius, fill: (d) => catOf.get(d.n), fillOpacity: (d) => d.op, stroke: "white", strokeWidth: 0.6, strokeOpacity: (d) => d.op }), Plot.dot([rootEntry], { x: "x", y: "y", r: 8, fill: (d) => catOf.get(d.n), stroke: "black", strokeWidth: 1.5 }), Plot.text(labelData, { x: "x", y: "y", text: (d) => String(label(d.n)).split(/[./]/).pop(), dy: -9, fontSize: (d) => (d.n === rootNode || d === centerEntry ? 11 : 9), fontWeight: (d) => (d.n === rootNode || d === centerEntry ? "bold" : "normal"), fill: "currentColor", fillOpacity: (d) => d.op, strokeOpacity: (d) => d.op, stroke: "white", strokeWidth: 3, paintOrder: "stroke" }), Plot.tip(drawn, Plot.pointer({ x: "x", y: "y", maxRadius: hitRadiusPx, title: (d) => label(d.n) + (d.pinned ? " (pinned \u2014 pan to return)" : "") })) ] }); const svg = figEl.tagName.toLowerCase() === "svg" ? figEl : figEl.querySelector(":scope > svg"); const xs = figEl.scale("x"), ys = figEl.scale("y"); const X = (v) => xs.apply(v), Y = (v) => ys.apply(v); pxPerUnit = Math.abs(X(1) - X(0)); const under = document.createElementNS(SVGNS, "g"); const TIERS = 6; const tiers = Array.from({ length: TIERS }, () => []); for (const L of linkList) tiers[Math.min(TIERS - 1, ((1 - L.op) * TIERS) | 0)].push(L); tiers.forEach((list, i) => { if (!list.length) return; const p = document.createElementNS(SVGNS, "path"); p.setAttribute("d", buildPath(list, X, Y)); p.setAttribute("fill", "none"); p.setAttribute("stroke", linkColor); p.setAttribute("stroke-opacity", (linkOpacity * (1 - i / TIERS)).toFixed(3)); under.append(p); }); const circ = document.createElementNS(SVGNS, "circle"); circ.setAttribute("cx", X(0)); circ.setAttribute("cy", Y(0)); circ.setAttribute("r", pxPerUnit); circ.setAttribute("fill", "none"); circ.setAttribute("stroke", "#ccc"); circ.setAttribute("stroke-dasharray", "2,3"); under.append(circ); svg.prepend(under); const pxAtNeg = xs.apply(-domainR), pxAtPos = xs.apply(domainR); const pyAtNeg = ys.apply(-domainR), pyAtPos = ys.apply(domainR); toData = (clientX, clientY) => { const rect = svg.getBoundingClientRect(); const px = clientX - rect.left, py = clientY - rect.top; return { re: -domainR + ((px - pxAtNeg) / (pxAtPos - pxAtNeg)) * (2 * domainR), im: -domainR + ((py - pyAtNeg) / (pyAtPos - pyAtNeg)) * (2 * domainR) }; }; hitList = drawn; lastStats = { drawn: drawn.length, total: nodes.length, camera: "orbit", spread, locality, cramped: farFrac, focal: String(label(focalNode)), renderMs: lastRenderMs, rootPinned: rootEntry.pinned }; figWrap.replaceChildren(figEl); if (localitySettling || fading) scheduleRender(); if (!legendBuilt) { try { const lg = figEl.legend("color", { width }); if (lg) { legendWrap.append(lg); lg.querySelectorAll('[class$="-swatch"]').forEach((el, i) => { const text = el.textContent.replace(/\u200b/g, "").trim(); const target = catNode.get(text) ?? catNode.get(categories[i]); if (!target) return; el.tabIndex = 0; el.setAttribute("role", "button"); el.title = `Centre on ${text || categories[i]}`; el.addEventListener("click", () => centerOn(target)); el.addEventListener("keydown", (e) => { if (e.key === "Enter" || e.key === " ") { e.preventDefault(); centerOn(target); } }); }); } } catch (e) {} legendBuilt = true; } } function clampFocus(f) { const r = Math.hypot(f.re, f.im); if (!(r > panLimitR)) return G.clampDisk(f); const s = panLimitR / r; return { re: f.re * s, im: f.im * s }; } function setFocus(f) { focus = clampFocus({ re: f.re, im: f.im }); Minv = G.transMat(focus); } function applyPan(delta) { Minv = G.matNormalize(G.matMul(Minv, G.transMat(G.neg(delta)))); setFocus(G.matApplyToOrigin(Minv)); M = ht_translateFrom(focus); } function animateFocus(target, duration = animDuration) { const myToken = ++animToken; const f0 = { ...focus }; const f1 = G.clampDisk({ re: target.re, im: target.im }); const t0 = performance.now(); (function step(now = performance.now()) { if (myToken !== animToken) return; const t = Math.min(1, (now - t0) / duration); const e = ht_easeInOutCubic(t); setFocus({ re: f0.re + (f1.re - f0.re) * e, im: f0.im + (f1.im - f0.im) * e }); M = ht_translateFrom(focus); render(); if (t < 1) requestAnimationFrame(step); })(); } function centerOn(node) { animateFocus(node.z0); } function clearPersistence() { focalPrev = -1; locality = 0; for (const e of pool) { e.keep = false; e.stick = false; e.labeled = false; e.stickLabel = false; } } function applySpread(next, { animate = true, cursor = null } = {}) { const s = Math.min(spreadRange[1], Math.max(spreadRange[0], next)); if (!relayout || s === spread) return; const c = cursor ?? { re: 0, im: 0 }; let anchor = pool[0], best = Infinity; for (let i = 0; i < pool.length; i++) { const e = pool[i]; const dx = e.x - c.re, dy = e.y - c.im; const d = dx * dx + dy * dy; if (d < best) { best = d; anchor = e; } } const target = G.clampDisk({ re: anchor.x, im: anchor.y }); for (let i = 0; i < pool.length; i++) { morphFrom[2 * i] = pool[i].x; morphFrom[2 * i + 1] = pool[i].y; } spread = s; relayout(spread); measureTree(); setFocus(solveFocus(anchor.n.z0, target)); M = ht_translateFrom(focus); clearPersistence(); for (let i = 0; i < nodes.length; i++) { const z = ht_apply(M, nodes[i].z0); morphTo[2 * i] = z.re; morphTo[2 * i + 1] = z.im; } if (!animate || spreadDuration <= 0) { morph = null; render(); return; } const token = ++animToken; const t0 = performance.now(); morph = { t: 0 }; (function step(now = performance.now()) { if (token !== animToken) { morph = null; render(); return; } const raw = Math.min(1, (now - t0) / spreadDuration); morph.t = d3.easeCubicOut(raw); if (raw >= 1) morph = null; render(); if (raw < 1) requestAnimationFrame(step); })(); } let spreadTarget = null, spreadQueued = false; function scheduleSpread(next) { spreadTarget = next; if (spreadQueued) return; spreadQueued = true; requestAnimationFrame(() => { spreadQueued = false; const v = spreadTarget; spreadTarget = null; applySpread(v, { cursor: wheelCursor }); }); } function resetView() { animToken++; morph = null; if (relayout && spread !== 1) { spread = 1; relayout(1); measureTree(); clearPersistence(); } animateFocus({ re: 0, im: 0 }); } const CAP = { capture: true }; let dragging = false, last = null, movedPx = 0, rafPending = false; function scheduleRender() { if (rafPending) return; rafPending = true; requestAnimationFrame(() => { rafPending = false; render(); }); } figWrap.addEventListener("pointerdown", (e) => { if (e.button !== 0) return; e.preventDefault(); e.stopPropagation(); animToken++; morph = null; dragging = true; movedPx = 0; last = toData(e.clientX, e.clientY); figWrap.style.cursor = "grabbing"; figWrap.setPointerCapture(e.pointerId); }, CAP); figWrap.addEventListener("pointermove", (e) => { if (!dragging) return; e.stopPropagation(); movedPx += Math.abs(e.movementX ?? 0) + Math.abs(e.movementY ?? 0); const cur = toData(e.clientX, e.clientY); const delta = { re: cur.re - last.re, im: cur.im - last.im }; if (Math.hypot(delta.re, delta.im) > 1e-4) { applyPan(delta); last = cur; scheduleRender(); } }, CAP); function endDrag(e, click) { if (!dragging) return; dragging = false; figWrap.style.cursor = "grab"; try { figWrap.releasePointerCapture(e.pointerId); } catch (_) {} if (click && movedPx < 5) { const hit = nearestAt(e.clientX, e.clientY); if (hit) centerOn(hit.n); } } figWrap.addEventListener("pointerup", (e) => endDrag(e, true), CAP); figWrap.addEventListener("pointercancel", (e) => endDrag(e, false), CAP); function nearestAt(clientX, clientY) { const p = toData(clientX, clientY); let best = null, bestD = hitRadiusPx / pxPerUnit; for (const d of hitList) { const dd = Math.hypot(d.x - p.re, d.y - p.im); if (dd < bestD) { bestD = dd; best = d; } } return best; } figWrap.addEventListener("wheel", (e) => { const c = toData(e.clientX, e.clientY); if (Math.hypot(c.re, c.im) > zoomRegionR) return; e.preventDefault(); animToken++; wheelCursor = c; scheduleSpread(spreadTick(spreadTarget ?? spread, e.deltaY < 0 ? 1 : -1)); }, { passive: false }); render(); return { element: container, reset: resetView, goToRoot: () => centerOn(rootNode), centerOn, get cameraMode() { return "orbit"; }, get panLimit() { return panLimitR; }, get spread() { return spread; }, setSpread: (v, opts) => applySpread(v, typeof opts === "boolean" ? { animate: opts } : opts), get stats() { return lastStats; }, get focus() { return focus; }, get transform() { return M; } }; } const ht_root = Array.isArray(ht_treeData) ? d3.stratify() .id((d) => d.name) .parentId((d) => d.name.includes(".") ? d.name.slice(0, d.name.lastIndexOf(".")) : null) (ht_treeData) : d3.hierarchy(ht_treeData); const ht_baseStep = HT_CONFIG.baseSpan / Math.max(1, ht_root.height); const ht_nodes = ht_layout(ht_root, { step: ht_baseStep }); return ht_viewer4(ht_nodes, { ...HT_CONFIG, relayout: (s) => ht_layout(ht_root, { step: ht_baseStep * s }) }); })(); display(ht_chart.element);32:[{"id":"ad0b3f31593a2b841f97dd75480bd0a92e52b7980527288266c7772c8916b8e79adf8cbcf232b477049195164a741422d95d36704a2000e28dda863df2f6e681","href":"https://static.observableusercontent.com/files/ad0b3f31593a2b841f97dd75480bd0a92e52b7980527288266c7772c8916b8e79adf8cbcf232b477049195164a741422d95d36704a2000e28dda863df2f6e681","name":"gtdb-life-genus.json","type":"application/json","lastModified":1788931984720,"size":1117534},{"id":"f74afe33d3a848d2257751c9a83a588338da4d2b1ff0cc494a388e160c51abab9510adafe23ff61fa791c5673f09e633d42abe6cbb9f6436e05f762ccdb2189c","href":"https://static.observableusercontent.com/files/f74afe33d3a848d2257751c9a83a588338da4d2b1ff0cc494a388e160c51abab9510adafe23ff61fa791c5673f09e633d42abe6cbb9f6436e05f762ccdb2189c","name":"mammals.json","type":"application/json","lastModified":1788934156417,"size":271343}] 2f:{"id":"631c67bfe57f0a1c","slug":"hyperbolic-tree-viewer-remix","title":"Hyperbolic Tree Viewer Remix","thumbnail":"dfca4665dd02b26214134693a4a1b2551c0607d0e0b04e4d1e79e1b8910387f4","access_level":"public","create_time":"$D2026-09-09T03:34:47.856Z","update_time":"$D2026-09-09T19:43:07.533Z","view_time":null,"first_public_time":"$D2026-09-09T19:28:26.198Z","fork":{"id":"214bf2e31d6c906d","slug":"hyperbolic-tree-viewer","title":"Hyperbolic Tree Viewer","owner":{"id":"11bfeb572ddbe905","login":"ambassadors","name":"Observable Ambassadors"}},"stars":1,"starred":false,"owner":{"type":"team","id":"cf45be0120eccaad","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/aeddc181df6ca80a347940ba62e17601ac6395e9d2c21142887eca5fd277326a","tier":"starter_2024"},"version":757,"publish_version":757,"role":null,"authored":false,"authors":[{"type":"individual","id":"5da1d0646b8496ac","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/9c14da488e1a68ca1868ed025eb7edcce3d300c8a9f3fbcdae66a3daa9ccca63","tier":null}],"members":[{"type":"individual","id":"5da1d0646b8496ac","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/9c14da488e1a68ca1868ed025eb7edcce3d300c8a9f3fbcdae66a3daa9ccca63","tier":null,"role":"editor"},{"type":"team","id":"cf45be0120eccaad","login":"laotzunami","name":"Lao","avatar_url":"https://avatars-next.observableusercontent.com/aeddc181df6ca80a347940ba62e17601ac6395e9d2c21142887eca5fd277326a","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Hyperbolic Tree Viewer Remix","cells":[{"id":141,"value":"# Hyperbolic Tree Viewer Remix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":143,"value":"This is a fork and remix of [ee2dev](https://observablehq.com/@ee2dev)'s notebook [Hyperbolic Tree Viewer](https://observablehq.com/@ambassadors/hyperbolic-tree-viewer). I love the concept and wanted to try a few variation.\n\n- In hyperbolic space, panning the space in a circle and returning to the same spot [rotates the space](https://youtu.be/zQo_S3yNa2w?t=434), which is called [holonomy](https://en.wikipedia.org/wiki/Holonomy). This makes navigation disorienting. I've anchored the direction to the root node so a slight rotation is applied to counter act this holonomy. This is similar to the difference between trackball and orbit cameras in 3D.\n- I've changed the zoom behavior to adjust the curvature of the space, fanning out the nodes.\n\nIf you like this, don't forget to support the original author! I'm surprised how fun and easy it is to explore large hierarchies. Thanks to [ee2dev](https://observablehq.com/@ee2dev) for the inspiration.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":108,"value":"$31","pinned":false,"hidden":false,"mode":"js","author":"agent","summary":"Mount viewer with pinned root and add go-to-root button"},{"id":142,"value":"const ht_treeData =\n await FileAttachment(\"mammals.json\").json();\n //await FileAttachment(\"gtdb-life-genus.json\").json();\n\ndisplay(ht_treeData);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"2","titling":"auto"}} 30:"$2f:body"