25:["$","title",null,{"children":"Test SpeedUp PolyLabel | XiongBiao | Observable"}] 49:T4fc,{ const poly = water2[0]; const start = performance.now(); const incircle = polylabel(poly, precision); const end = performance.now(); const start2 = performance.now(); const incircle2 = polylabel_speedup([poly], precision); const end2 = performance.now(); const r = new Renderer(600, 400) .stroke() .text(`No-Speedup: ${end-start} ms`, 0, 20) .fit(flatCoords(poly), 25) .fill("rgba(180,90,45,0.2)") .stroke("black") .polygon(poly) .fill() .stroke("red") .ellipse(...incircle) .stroke() .fill("red") .points([[incircle[0], incircle[1]]]) .render(); const r2 = new Renderer(600, 400) .stroke() .text(`Speedup: ${end2-start2} ms`, 0, 20) .fit(flatCoords(poly), 25) .fill("rgba(180,90,45,0.2)") .stroke("black") .polygon(poly) .fill() .stroke("red") .ellipse(...[...incircle2, incircle2.distance]) .stroke() .fill("red") .points([[incircle2[0], incircle2[1]]]) .render(); return html`

${r}

${r2}

`; }4a:Te44,function polylabel_speedup(polygon, precision = 1.0, debug = false) { // find the bounding box of the outer ring let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity; for (const [x, y] of polygon[0]) { if (x < minX) minX = x; if (y < minY) minY = y; if (x > maxX) maxX = x; if (y > maxY) maxY = y; } const width = maxX - minX; const height = maxY - minY; const cellSize = Math.max(precision, Math.min(width, height)); if (cellSize === precision) { const result = [minX, minY]; result.distance = 0; return result; } // flatten the polygon rings into a single contiguous coordinate buffer for // cache-friendly, pointer-chase-free access in the hot distance loop let numPoints = 0; for (const ring of polygon) numPoints += ring.length; const coords = new Float64Array(numPoints * 2); const ringEnds = []; // end offset into coords for each ring (start = previous end, or 0) let c = 0; for (const ring of polygon) { for (let i = 0; i < ring.length; i++) { coords[c++] = ring[i][0]; coords[c++] = ring[i][1]; } ringEnds.push(c); } const blocks = buildBlocks(coords, ringEnds); // a priority queue of cells in order of their "potential" (max distance to polygon) const cellQueue = new TinyQueue([], (a, b) => b.max - a.max); // take centroid as the first best guess let bestCell = getCentroidCell(coords, ringEnds, blocks); // second guess: bounding box centroid const bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, coords, ringEnds, blocks, -Infinity, null); if (bboxCell.d > bestCell.d) bestCell = bboxCell; let numProbes = 2; function potentiallyQueue(x, y, h, seed) { // a cell is only useful if it can beat the best (d > bestCell.d) or is // worth subdividing (max = d + h·√2 > bestCell.d + precision). Both fail // once d ≤ threshold, so the distance scan can bail there early. const threshold = bestCell.d - Math.max(0, h * Math.SQRT2 - precision); const cell = new Cell(x, y, h, coords, ringEnds, blocks, threshold, seed); numProbes++; if (cell.max > bestCell.d + precision) cellQueue.push(cell); // update the best cell if we found a better one if (cell.d > bestCell.d) { bestCell = cell; if (debug) console.log(`found best ${Math.round(1e4 * cell.d) / 1e4} after ${numProbes} probes`); } } // cover polygon with initial cells let h = cellSize / 2; for (let x = minX; x < maxX; x += cellSize) { for (let y = minY; y < maxY; y += cellSize) { potentiallyQueue(x + h, y + h, h, null); } } while (cellQueue.length) { // pick the most promising cell from the queue const cell = cellQueue.pop(); // do not drill down further if there's no chance of a better solution if (cell.max - bestCell.d <= precision) break; // split the cell into four cells, seeding each with the parent's nearest segment h = cell.h / 2; potentiallyQueue(cell.x - h, cell.y - h, h, cell); potentiallyQueue(cell.x + h, cell.y - h, h, cell); potentiallyQueue(cell.x - h, cell.y + h, h, cell); potentiallyQueue(cell.x + h, cell.y + h, h, cell); } if (debug) { console.log(`num probes: ${numProbes}\nbest distance: ${bestCell.d}`); } const result = [bestCell.x, bestCell.y]; result.distance = bestCell.d; return result; }4b:Td74,// signed distance from cell center to polygon outline (negative if outside), // also recording the nearest segment on the cell. maxD is a distance threshold: // if a partial result proves the center is no farther than maxD from the outline, // the scan bails out early and returns maxD, since the caller has already // determined such a cell can't beat the best. seed is the parent cell (or null); // its nearest segment is checked first so boundary cells reach the early-out // threshold without scanning the whole outline. function pointToPolygonDist(cell, coords, ringEnds, blocks, maxD, seed) { const x = cell.x; const y = cell.y; let inside = false; let minDistSq = Infinity; const thresholdSq = maxD > 0 ? maxD * maxD : -1; if (seed !== null) { cell.nsx1 = seed.nsx1; cell.nsy1 = seed.nsy1; cell.nsx2 = seed.nsx2; cell.nsy2 = seed.nsy2; minDistSq = getSegDistSq(x, y, seed.nsx1, seed.nsy1, seed.nsx2, seed.nsy2); if (minDistSq <= thresholdSq) return maxD; } const stride = K * 2; const numRings = ringEnds.length; let g = 0; // running block index into bboxes let ringStart = 0; for (let r = 0; r < numRings; r++) { const ringEnd = ringEnds[r]; // previous vertex (b), starting from the last point in the ring; carried // across blocks so each block's first edge connects to the prior vertex let bx = coords[ringEnd - 2]; let by = coords[ringEnd - 1]; for (let s = ringStart; s < ringEnd; s += stride, g += 4) { let end = s + stride; if (end > ringEnd) end = ringEnd; const bminX = blocks[g], bminY = blocks[g + 1], bmaxX = blocks[g + 2], bmaxY = blocks[g + 3]; // lower bound on the distance from (x, y) to any edge in this block const dx = x < bminX ? bminX - x : x > bmaxX ? x - bmaxX : 0; const dy = y < bminY ? bminY - y : y > bmaxY ? y - bmaxY : 0; const skipDist = dx * dx + dy * dy >= minDistSq; // this block's edges can only flip ray-cast parity if its bbox straddles // y and extends right of x; else no edge crosses the rightward ray const skipCross = y < bminY || y >= bmaxY || x > bmaxX; if (skipDist && skipCross) { bx = coords[end - 2]; by = coords[end - 1]; continue; } for (let i = s; i < end; i += 2) { const ax = coords[i]; const ay = coords[i + 1]; if (!skipCross && (ay > y !== by > y) && (x < (bx - ax) * (y - ay) / (by - ay) + ax)) inside = !inside; if (!skipDist) { const distSq = getSegDistSq(x, y, ax, ay, bx, by); if (distSq < minDistSq) { minDistSq = distSq; cell.nsx1 = ax; cell.nsy1 = ay; cell.nsx2 = bx; cell.nsy2 = by; // the point is already close enough to the outline that this cell // can't possibly contain a better label position — stop scanning if (minDistSq <= thresholdSq) return maxD; } } bx = ax; by = ay; } } ringStart = ringEnd; } return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq); }4c:T607,// precompute one bounding box per block of K consecutive edges (over both // endpoints of every edge in it) so the distance scan can skip whole blocks in // O(1). The block layout mirrors the flattened coords/ringEnds and is re-derived // in the scan, so only the bboxes need storing: a flat [minX,minY,maxX,maxY] run // per block, sized upfront from the ring lengths. function buildBlocks(coords, ringEnds) { const stride = K * 2; let numBlocks = 0; let ringStart = 0; for (let r = 0; r < ringEnds.length; r++) { numBlocks += Math.ceil((ringEnds[r] - ringStart) / stride); ringStart = ringEnds[r]; } const blocks = new Float64Array(numBlocks * 4); let g = 0; ringStart = 0; for (let r = 0; r < ringEnds.length; r++) { const ringEnd = ringEnds[r]; for (let s = ringStart; s < ringEnd; s += stride, g += 4) { const end = s + stride < ringEnd ? s + stride : ringEnd; const prev = s === ringStart ? ringEnd - 2 : s - 2; let minX = coords[prev], minY = coords[prev + 1]; let maxX = minX, maxY = minY; for (let i = s; i < end; i += 2) { const px = coords[i], py = coords[i + 1]; if (px < minX) minX = px; else if (px > maxX) maxX = px; if (py < minY) minY = py; else if (py > maxY) maxY = py; } blocks[g] = minX; blocks[g + 1] = minY; blocks[g + 2] = maxX; blocks[g + 3] = maxY; } ringStart = ringEnd; } return blocks; }4d:[{"id":"a0597d26b72f894d89b2564498ed787b2f9c0e166f6533855285952deb752672ed48ab970e0e0f8538be098a03071fd7bfbd1469e31a018665784fb189cebd23","href":"https://static.observableusercontent.com/files/a0597d26b72f894d89b2564498ed787b2f9c0e166f6533855285952deb752672ed48ab970e0e0f8538be098a03071fd7bfbd1469e31a018665784fb189cebd23","name":"Greenland.dat","type":"application/octet-stream","lastModified":1782723828853.697,"size":10402600},{"id":"2d570dada6166e6bb824558a525194bb36fa3d7f2d09b4220ee651a1eed502b14efef14976f98bf5406e08fa1511d151ecfc1ddfd3aed32eae7f11186dff6790","href":"https://static.observableusercontent.com/files/2d570dada6166e6bb824558a525194bb36fa3d7f2d09b4220ee651a1eed502b14efef14976f98bf5406e08fa1511d151ecfc1ddfd3aed32eae7f11186dff6790","name":"Africa.dat","type":"application/octet-stream","lastModified":1782722824323.175,"size":20230664}] 29:{"id":"c658dc189f07c7fa","slug":null,"title":"Test SpeedUp PolyLabel","thumbnail":"d24a4cbfa2dc7cc80656d4cde9d52d5e668c86222847448d8ad1d253420bc624","access_level":"public","create_time":"$D2026-06-29T07:21:33.142Z","update_time":"$D2026-06-29T09:04:11.393Z","view_time":null,"first_public_time":"$D2026-06-29T07:21:33.142Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/a95188709ffcb422fcc635f47420feb25f69fd7305881a42b4a9907e87d2aaf0","tier":"free_2026","bio":"","followed_by_you":false,"follows_you":false},"version":216,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"fc82b550d8112553","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/caf2b8f3d51ea1f56efa20730077b94beb57622ab029080cdb84a9ad89ac467d","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"team","id":"189a68e88fe366bd","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/a95188709ffcb422fcc635f47420feb25f69fd7305881a42b4a9907e87d2aaf0","tier":"free_2026","role":"editor"},{"type":"individual","id":"fc82b550d8112553","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/caf2b8f3d51ea1f56efa20730077b94beb57622ab029080cdb84a9ad89ac467d","tier":null,"role":"editor"}],"comments":[{"id":"8f60faa66f5279e0","reply_to_id":null,"content":"I had missed https://github.com/mapbox/polylabel/pull/127 ; impressive!","create_time":"$D2026-06-30T13:19:20.916Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}},{"id":"c4264893f176b458","reply_to_id":"8f60faa66f5279e0","content":"Absolutely brilliant!","create_time":"$D2026-07-02T12:36:59.544Z","update_time":null,"resolved":false,"user":{"type":"individual","id":"fc82b550d8112553","login":"xiongbiao","name":"XiongBiao","avatar_url":"https://avatars-next.observableusercontent.com/caf2b8f3d51ea1f56efa20730077b94beb57622ab029080cdb84a9ad89ac467d","tier":null}}],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Test SpeedUp PolyLabel","cells":[{"id":0,"value":"# Test SpeedUp PolyLabel","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":112,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":106,"value":"precision = 0.0000000001","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"water1 = await d3.json(\"https://raw.githubusercontent.com/mapbox/polylabel/refs/heads/master/test/fixtures/water1.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"water2 = await d3.json(\"https://raw.githubusercontent.com/mapbox/polylabel/refs/heads/master/test/fixtures/water2.json\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"// number of consecutive edges grouped under a single bounding box for block-skip\nK = 32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"function Cell(x, y, h, coords, ringEnds, blocks, maxD, seed) {\n this.x = x; // cell center x\n this.y = y; // cell center y\n this.h = h; // half the cell size\n // nsx1..nsy2 hold the nearest segment found below, so child cells can seed\n // their scan with it (a child is almost always nearest to the same segment)\n this.nsx1 = 0; this.nsy1 = 0; this.nsx2 = 0; this.nsy2 = 0;\n this.d = pointToPolygonDist(this, coords, ringEnds, blocks, maxD, seed); // distance from cell center to polygon\n this.max = this.d + h * Math.SQRT2; // max distance to polygon within a cell\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":34,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"// get polygon centroid (over the outer ring, coords[0..ringEnds[0]))\nfunction getCentroidCell(coords, ringEnds, blocks) {\n let area = 0;\n let x = 0;\n let y = 0;\n const end = ringEnds[0];\n\n for (let i = 0, j = end - 2; i < end; j = i, i += 2) {\n const ax = coords[i];\n const ay = coords[i + 1];\n const bx = coords[j];\n const by = coords[j + 1];\n const f = ax * by - bx * ay;\n x += (ax + bx) * f;\n y += (ay + by) * f;\n area += f * 3;\n }\n const centroid = new Cell(x / area, y / area, 0, coords, ringEnds, blocks, -Infinity, null);\n if (area === 0 || centroid.d < 0) return new Cell(coords[0], coords[1], 0, coords, ringEnds, blocks, -Infinity, null);\n return centroid;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"// get squared distance from a point to a segment\nfunction getSegDistSq(px, py, x, y, bx, by) {\n let dx = bx - x;\n let dy = by - y;\n\n if (dx !== 0 || dy !== 0) {\n const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);\n\n if (t > 1) {\n x = bx;\n y = by;\n\n } else if (t > 0) {\n x += dx * t;\n y += dy * t;\n }\n }\n\n dx = px - x;\n dy = py - y;\n\n return dx * dx + dy * dy;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":101,"value":"function arrayDepth(v) {\n return Array.isArray(v) ? 1 + Math.max(0, ...v.map(arrayDepth)) : 0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":99,"value":"function flatCoords(poly) {\n return arrayDepth(poly) <= 2 ? poly : flatCoords(poly.flat());\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"import {Renderer} from \"@jwolondon/renderer\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"import {TinyQueue} from \"@jwolondon/polylabel\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"import {polylabel} from \"@jwolondon/polylabel\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"{\n const poly = africa;\n \n const start2 = performance.now();\n const incircle2 = polylabel_speedup([poly], precision);\n const end2 = performance.now();\n \n return [incircle2, end2-start2];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"africa = {\n const buffer = await FileAttachment(\"Greenland.dat\").arrayBuffer();\n const view = new DataView(buffer);\n const coords = Array.from(\n {length: (buffer.byteLength - 8) / 16},\n (_, i) => [\n view.getFloat64(8 + i * 16, true),\n view.getFloat64(16 + i * 16, true)\n ]\n )\n return coords;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4d","stdlib":"1"}} 24:null