34:["$","title",null,{"children":"Approximating shapes with ball and rectangle trees | Claudio Esperança | Observable"}] 3c:T1252,# Approximating shapes with ball and rectangle trees We want to approximate a given shape using a collection of balls (circles) or rectangles. This collection is then organized using a *bounding volume hierarchy* (BVH) which can be used to answer proximity queries, such as returning the closest ball/rectangle to a given point. In a nutshell, the question we are trying to answer here is: _which is better - circles or rectangles ?_ Clearly, it all depends. More specifically, two issues deserve investigation: 1. How well can we approximate a given shape using circles / rectangles? 2. When these circle/rectangle collections are organized in a BVH, how efficiently does each hierarchy answer proximity queries? ## Background For circles, we have investigated both issues in previous notebooks. Specifically, [shape approximation with balls](https://observablehq.com/d/9761ebfa33a5220f) implements two algorithms that compute a collection of balls that cover a given binary (black and white) image, while [Omohundro ball tree construction algorithms](https://observablehq.com/@esperanc/omohundro-balltree-construction-algorithms) implements three types of ball trees with methods that compute proximity based queries. From the perspective of rectangles, the [Rectangle Approximation (RA) trees](https://observablehq.com/d/a8b35859f33908c1) notebook proposes a way of approximating images with rectangles. These trees can also be used for answering queries, as they are bounding volume hierarchies. ## Methodology We try to answer the question about approximation fidelity by testing shapes generated from text rendered with customizable fonts and sizes. A [binary (black and white) image](#letterImage) is then produced, and algorithms for ball and rectangle approximation are applied. Approximation error is assessed by using a [scaled version of the shape](#zoomedShape) as ground truth. Similarly scaled renderings of the [ball collection](#ballApproximation) and of the [rectangle collection](#rectApproximation) are then produced. Error is measured by counting the different pixels. Below you will find these renderings for the chosen text sample and font, as well as charts summarizing how the algorithms for producing ball / rectangle collections can be tuned with respect to primitive count and approximation error rates. For the produced ball and rectangle collections, a corresponding ball tree / RA tree is built. We assess the issue of proximity query efficiency by counting the number of steps required by ball trees and rectangle approximation trees to answer point distance queries. More precisely, we sample a region around the shape that is three times as large in both the _x_ and _y_ dimensions with ${tex`30 \times 30=900`} points. The number of steps is the number of nodes visited by a simple recursive branch-and-bound algorithm that is implemented for both tree kinds. Below you will find charts that show the results of these experiments. ## Conclusions In general, ball sets obtained with the SDT+filter approach produce better approximation than rectangle sets, when considering the same number of primitives per set. Exceptions to this rule can be observed in shapes containing many strictly horizontal or vertical edges, as is the case with text string "DEF" when typeset with a normal or bold font. In these cases, it is possible to use relatively few rectangles with low error rates, but many balls are needed to faithfully reproduce the same edges. It is possible to reduce even further the number of balls obtained with the SDT+filter approach by increasing the value of *epsilon* (approximation tolerance). Although the number of rectangles can also be reduced by using cuts with shallower levels and/or modifying fill rate thresholds (see [RA trees](https://observablehq.com/d/a8b35859f33908c1)), the resulting approximation error increases much more steeply with lower primitive counts than balls. When considering the "distance to point" query performance, ball trees generally perform worse for close points than rects. This tendency is reversed in the case of distant points. This can be attributed to the fact that RA trees behave as space partitioning hierarchies, so the size of leaves tend to diminish logarithmically with level. On the other hand, the set of balls computed by the SDT+filter approach tend to be relatively large on average and thus the search must examine leaves at deeper levels for points close to the shape. As a whole, except for the cases mentioned above where shapes have long horizontal or vertical edges, the lower primitive count of ball approximations seem to favor ball trees over rectangle trees. 3d:T5b4,function computeChartsData() { let inputs = { textSettings, zoom, ballSet, epsilon, raTreeCut, nodeFillRate }; let out = pipeline(inputs); let data = []; for (let e = 1 / 8; e <= 3; e += 1 / 8) { out.pieceBalls = out.pieceTree = out.ballApproximation = out.ballApproximationErrorImage = out.ballApproximationErrorImagePoints = null; inputs.epsilon = e; out = pipeline(inputs, out); data.push({ epsilon: e, type: "ball", primitives: out.pieceBalls.length, errorPixels: out.ballApproximationErrorImagePoints.length, errorPercent: (out.ballApproximationErrorImagePoints.length / out.groundPoints.length) * 100 }); } let h = out.pieceRaTree.height(); for (let cut = h - 2; cut <= h; cut++) { for (let rate = 1; rate >= 0.7; rate *= 0.95) { out.pieceRects = out.pieceRaCutTree = out.rectApproximation = out.rectApproximationErrorImage = out.rectApproximationErrorImagePoints = null; inputs.raTreeCut = cut; inputs.nodeFillRate = rate; out = pipeline(inputs, out); data.push({ cut: cut, rate: rate, type: "rect", primitives: out.pieceRects.length, errorPixels: out.rectApproximationErrorImagePoints.length, errorPercent: (out.rectApproximationErrorImagePoints.length / out.groundPoints.length) * 100 }); } } return data; }3e:Tfb3,// // This function encapsulates all the computation in a single function that depends only // on the input parameters. To speed up computation, an object with some of the values of // previous run of the pipeline can be provided // function pipeline(inputs, prevOutputs = {}) { let { textSettings, zoom, ballSet, epsilon, raTreeCut, nodeFillRate } = inputs; let { piece, pieceImageData, piecePoints, zoomedShape, pieceBalls, pieceTree, pieceRaTree, pieceRaCutTree, ballApproximation, ballApproximationErrorImage, ballApproximationErrorImagePoints, pieceRects, rectApproximation, rectApproximationErrorImage, rectApproximationErrorImagePoints, groundPoints } = prevOutputs; piece = piece || textImage( textSettings.text, textSettings.fontSize, textSettings.fontFamily, textSettings.fontVariant ); pieceImageData = pieceImageData || binarizeImageData(getImageData(piece), 128); zoomedShape = zoomedShape || textImage( textSettings.text, textSettings.fontSize, textSettings.fontFamily, textSettings.fontVariant, zoom ); groundPoints = groundPoints || imageDataPoints(getImageData(zoomedShape)); piecePoints = piecePoints || imageDataPoints(pieceImageData); pieceBalls = pieceBalls || (function () { if (ballSet == "SDT+filter") return ballCoverNew(pieceImageData, epsilon); if (ballSet == "DMA") return ballCover(pieceImageData); const pixelRadius = Math.SQRT2 / 2; return piecePoints.map(({ x, y }) => new Ball(x, y, pixelRadius)); })(); // pieceTree = // pieceTree || // (function () { // let pieceTree = bottomUp(pieceBalls); // pieceTree.computeEnclosingCircles(); // return pieceTree; // })(); pieceRaTree = pieceRaTree || new RA(piecePoints); pieceRaCutTree = pieceRaCutTree || pieceRaTree.cutTree(raTreeCut).approxTree(nodeFillRate); ballApproximation = ballApproximation || (function () { const [w, h] = [piece.width * zoom, piece.height * zoom]; const ctx = DOM.context2d(w, h, 1); ctx.canvas.style.cssText = ` image-rendering: crisp-edges; image-rendering: pixelated; -webkit-image-rendering: pixelated; -webkit-image-rendering: crisp-edges;`; let balls = pieceBalls.map( ({ x, y, r }) => new Ball(x * zoom, y * zoom, r * zoom) ); drawBalls(ctx, balls); return ctx.canvas; })(); ballApproximationErrorImage = ballApproximationErrorImage || errorImage(zoomedShape, ballApproximation); ballApproximationErrorImagePoints = ballApproximationErrorImagePoints || imageDataPoints(getImageData(ballApproximationErrorImage)); pieceRects = pieceRects || [...pieceRaCutTree.approximation(20)].map((t) => t.box); rectApproximation = rectApproximation || (function () { const [w, h] = [piece.width * zoom, piece.height * zoom]; const ctx = DOM.context2d(w, h, 1); ctx.canvas.style.cssText = ` image-rendering: crisp-edges; image-rendering: pixelated; -webkit-image-rendering: pixelated; -webkit-image-rendering: crisp-edges;`; let boxes = pieceRects; let raster = rasterizeBoxes(boxes, w, h, zoom); ctx.putImageData(raster, 0, 0); return ctx.canvas; })(); rectApproximationErrorImage = rectApproximationErrorImage || errorImage(zoomedShape, rectApproximation); rectApproximationErrorImagePoints = rectApproximationErrorImagePoints || imageDataPoints(getImageData(rectApproximationErrorImage)); return { piece, pieceImageData, piecePoints, zoomedShape, pieceBalls, pieceTree, pieceRaTree, pieceRaCutTree, ballApproximation, ballApproximationErrorImage, ballApproximationErrorImagePoints, pieceRects, rectApproximation, rectApproximationErrorImage, rectApproximationErrorImagePoints, groundPoints }; }3f:[] 38:{"id":"77ad76683d49dc61","slug":"approximating-shapes-with-ball-and-rectangle-trees","title":"Approximating shapes with ball and rectangle trees","thumbnail":"6ad03aa8a5fd17657a1e7eb231f20d85d2a6998857e817f619a08af4720c64af","access_level":"public","create_time":"$D2021-12-23T21:55:15.525Z","update_time":"$D2022-04-11T14:20:37.301Z","view_time":null,"first_public_time":"$D2022-01-02T16:56:15.750Z","has_unpublished_edits":null,"fork":false,"stars":9,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024","bio":"Computer Graphics & Visualization @ufrj.br ","followed_by_you":false,"follows_you":false},"version":1277,"publish_version":1277,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"bio":"Computer Graphics & Visualization @ufrj.br ","followed_by_you":false,"follows_you":false},{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"bio":".","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"},{"type":"individual","id":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Approximating shapes with ball and rectangle trees","cells":[{"id":0,"value":"$3c","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":925,"value":"
\n## Text Settings","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":900,"value":"viewof textSettings = Inputs.form({\n fontFamily: Inputs.radio([\"serif\", \"sans-serif\"], {\n value: \"serif\",\n label: \"Font family\"\n }),\n fontSize: Inputs.radio([40, 80, 100, 120], {\n value: 100,\n label: \"Font size\"\n }),\n fontVariant: Inputs.radio([\"normal\", \"bold\", \"italic\", \"bold italic\"], {\n label: \"Font variant\",\n value: \"normal\"\n }),\n text: Inputs.radio([\"abc\", \"ABC\", \"def\", \"DEF\", \"ghi\", \"GHI\", \"&#$\", \"●▲■\"], {\n label: \"Text\",\n value: \"abc\"\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":520,"value":"shapeTitle = md`
\n## Model shape`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"letterImage = //out.piece\ntextImage(\n textSettings.text,\n textSettings.fontSize,\n textSettings.fontFamily,\n textSettings.fontVariant\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"Input image has ${piece.width} by ${piece.height} pixels, with ${piecePoints.length} black pixels","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":550,"value":"## Zoomed shape \n(used as ground truth)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":557,"value":"viewof zoom = Inputs.range([1, 10], { label: \"Zoom\", value: 5, step: 1 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":817,"value":"Number of black pixels: ${groundPoints.length}","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":562,"value":"zoomedShape = textImage(\n textSettings.text,\n textSettings.fontSize,\n textSettings.fontFamily,\n textSettings.fontVariant,\n zoom\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":525,"value":"## Approximation with balls","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":289,"value":"viewof ballSet = Inputs.radio([\"DMA\", \"SDT+filter\"], {\n value: \"SDT+filter\",\n label: \"Ball Set\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":494,"value":"viewof epsilon = Inputs.range([0, 4], {\n label: \"Epsilon (SDT+filter)\",\n value: 1.5,\n step: 0.1\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":669,"value":"Ball approximation has ${pieceBalls.length} balls","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":510,"value":"ballApproximation = {\n const [w, h] = [piece.width * zoom, piece.height * zoom];\n const ctx = DOM.context2d(w, h, 1);\n ctx.canvas.style.cssText = `\n image-rendering: crisp-edges;\n image-rendering: pixelated;\n -webkit-image-rendering: pixelated;\n -webkit-image-rendering: crisp-edges;\n`;\n let balls = [...pieceTree.approximation(20)].map((t) => {\n let { x, y, r } = t.entry;\n return new Ball(x * zoom, y * zoom, r * zoom);\n });\n drawBalls(ctx, balls);\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1270,"value":"ballApproximationStroke = {\n const [w, h] = [piece.width * zoom, piece.height * zoom];\n const ctx = DOM.context2d(w, h, 1);\n ctx.canvas.style.cssText = `\n image-rendering: crisp-edges;\n image-rendering: pixelated;\n -webkit-image-rendering: pixelated;\n -webkit-image-rendering: crisp-edges;\n`;\n let balls = [...pieceTree.approximation(20)].map((t) => {\n let { x, y, r } = t.entry;\n return new Ball(x * zoom, y * zoom, r * zoom);\n });\n ctx.fillStyle = `#00000000`;\n drawBalls(ctx, balls);\n return ctx.canvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":591,"value":"
\n## Approximation with rects","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":703,"value":"viewof raTreeCut = Inputs.range([0, pieceRaTreeHeight], {\n value: pieceRaTreeHeight,\n step: 1,\n label: \"Cut to use as approximation\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1239,"value":"viewof nodeFillRate = Inputs.range([0.5, 1], {\n value: 1,\n step: 0.01,\n label: \"Node fill rate\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":675,"value":"Rectangle approximation has ${[...pieceRaCutTree.approximation(20)].length} rectangles","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":519,"value":"rectApproximation = {\n const [w, h] = [piece.width * zoom, piece.height * zoom];\n const ctx = DOM.context2d(w, h, 1);\n ctx.canvas.style.cssText = `\n image-rendering: crisp-edges;\n image-rendering: pixelated;\n -webkit-image-rendering: pixelated;\n -webkit-image-rendering: crisp-edges;\n`;\n let boxes = [...pieceRaCutTree.approximation(20)].map((t) => t.box);\n let raster = rasterizeBoxes(boxes, w, h, zoom);\n ctx.putImageData(raster, 0, 0);\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1272,"value":"rectApproximationBoxes = {\n const [w, h] = [piece.width * zoom, piece.height * zoom];\n const ctx = DOM.context2d(w, h, 1);\n ctx.canvas.style.cssText = `\n image-rendering: crisp-edges;\n image-rendering: pixelated;\n -webkit-image-rendering: pixelated;\n -webkit-image-rendering: crisp-edges;\n`;\n let boxes = [...pieceRaCutTree.approximation(20)].map((t) => t.box);\n for (let b of boxes) {\n ctx.strokeRect(\n b.min.x * zoom,\n b.min.y * zoom,\n (b.size().x + 1) * zoom,\n (b.size().y + 1) * zoom\n );\n }\n // let raster = rasterizeBoxes(boxes, w, h, zoom);\n // ctx.putImageData(raster, 0, 0);\n return ctx.canvas;\n return boxes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":806,"value":"## Ball approximation error image","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":814,"value":"{\n let errorPixels = imageDataPoints(getImageData(ballApproximationErrorImage))\n .length;\n return md`Total of ${errorPixels} error pixels, or ${(\n (errorPixels / groundPoints.length) *\n 100\n ).toFixed(1)}%`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":811,"value":"ballApproximationErrorImage = errorImage(zoomedShape, ballApproximation)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":829,"value":"## Rectangle approximation error image","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":848,"value":"{\n let errorPixels = imageDataPoints(getImageData(rectApproximationErrorImage))\n .length;\n return md`Total of ${errorPixels} error pixels, or ${(\n (errorPixels / groundPoints.length) *\n 100\n ).toFixed(1)}%`;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":834,"value":"rectApproximationErrorImage = errorImage(zoomedShape, rectApproximation)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1048,"value":"## Ball/Rect approximations error comparison\n\nSince these charts take a while to recompute, you must press the button below to recompute them every time you change the parameters (text settings, zoom, etc)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1060,"value":"{\n let recomputeCharts = Inputs.button(\"recompute charts\");\n recomputeCharts.onmousedown = () => {\n mutable chartsData = computeChartsData();\n };\n return recomputeCharts;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1117,"value":"md`### Ball approximation error by epsilon`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1069,"value":"chartsData\n ? Plot.plot({\n width: 800,\n height: 450,\n style: \"font:14px sans-serif\",\n grid: true,\n margin: 50,\n y: {\n label: \"↑ error (%)\"\n },\n marks: [\n Plot.line(\n chartsData.filter((d) => d.type == \"ball\"),\n { x: \"epsilon\", y: \"errorPercent\" }\n ),\n Plot.ruleY([0])\n ]\n })\n : htl.html`
\n## Ball tree level cuts\nA cut for a level = (nodes at that level) + (leaves at shallower levels).
\nNumbers indicate the total number of nodes of the cut.\n\nTree has height ${pieceTreeHeight}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":55,"value":"{\n const n = pieceTree.height() + 1;\n let slotWidth = piece.width + margin;\n let slotHeight = piece.height + margin * 2 + 14;\n let totalWidth = slotWidth * n + margin;\n let rows = Math.ceil(totalWidth / width);\n const ctx = DOM.context2d(width, slotHeight * rows);\n ctx.textBaseline = \"bottom\";\n ctx.textAlign = \"center\";\n ctx.font = \"14px sans-serif\";\n ctx.save();\n let [dx, dy] = [margin, margin];\n ctx.translate(dx, dy);\n for (let l = 0; l < n; l++) {\n let balls = [...pieceTree.approximation(l)].map((t) => t.entry);\n ctx.fillStyle = \"#ffffff00\";\n drawBalls(ctx, balls);\n ctx.fillStyle = \"black\";\n ctx.fillText(\"\" + balls.length, piece.width / 2, piece.height + margin);\n dx += slotWidth;\n if (dx + slotWidth > width) {\n dx = margin;\n dy += slotHeight;\n }\n ctx.restore();\n ctx.save();\n ctx.translate(dx, dy);\n }\n ctx.restore();\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":639,"value":"
\n## Rectangle tree level cuts\n\nA cut for a level = (nodes at that level) + (leaves at shallower levels).
\nNumbers indicate the total number of nodes of the cut.\n\nTree has height ${pieceRaCutTree.height()}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":167,"value":"{\n const n = pieceRaTree.height() + 1;\n let slotWidth = piece.width + margin;\n let slotHeight = piece.height + margin * 2 + 14;\n let totalWidth = slotWidth * n + margin;\n let rows = Math.ceil(totalWidth / width);\n const ctx = DOM.context2d(width, slotHeight * rows);\n\n ctx.textBaseline = \"bottom\";\n ctx.textAlign = \"bottom\";\n ctx.font = \"14px sans-serif\";\n ctx.save();\n let [dx, dy] = [margin, margin];\n ctx.translate(dx, dy);\n for (let l = 0; l < n; l++) {\n let boxes = [...pieceRaCutTree.approximation(l)].map((t) => t.box);\n ctx.fillStyle = \"#ffffff00\";\n drawBoxes(ctx, boxes);\n ctx.fillStyle = \"black\";\n ctx.fillText(\"\" + boxes.length, piece.width / 2, piece.height + margin);\n dx += slotWidth;\n if (dx + slotWidth > width) {\n dx = margin;\n dy += slotHeight;\n }\n ctx.restore();\n ctx.save();\n ctx.translate(dx, dy);\n }\n ctx.restore();\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":443,"value":"
\n## Average number of steps for point distance queries by distance bracket","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":390,"value":"Plot.plot({\n style: \"font:14px sans-serif\",\n grid: true,\n width: width,\n margin: 50,\n facet: {\n data: sampleDistances,\n x: \"tree\"\n },\n marks: [\n Plot.rectY(\n sampleDistances,\n Plot.binX({ y: \"mean\" }, { x: \"dist\", y: \"steps\", fill: \"tree\" })\n ),\n Plot.text(\n sampleDistances,\n Plot.binX(\n { y: \"mean\" },\n {\n x: \"dist\",\n y: \"steps\",\n fill: \"tree\",\n dy: -5,\n text: (bin) => d3.mean(bin, (d) => d.steps).toFixed(1),\n fontSize: 11,\n fill: \"black\"\n }\n )\n ),\n Plot.ruleY([0])\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":617,"value":"Plot.plot({\n style: \"font:14px sans-serif\",\n grid: true,\n width: 400,\n margin: 50,\n facet: {\n data: sampleDistances,\n x: \"tree\"\n },\n fx: {\n paddingInner: 0.2\n },\n marks: [\n Plot.rectY(\n sampleDistances,\n Plot.binX(\n { y: \"mean\" },\n { x: { value: \"dist\", thresholds: 2 }, y: \"steps\", fill: \"tree\" }\n )\n ),\n Plot.text(\n sampleDistances,\n Plot.binX(\n { y: \"mean\" },\n {\n x: { value: \"dist\", thresholds: 2 },\n y: \"steps\",\n fill: \"tree\",\n dy: -5,\n text: (bin) => d3.mean(bin, (d) => d.steps).toFixed(1),\n fontSize: 14,\n fill: \"black\"\n }\n )\n ),\n Plot.ruleY([0])\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":448,"value":"
\n## Number of steps for point distance queries","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":377,"value":"Plot.plot({\n style: \"overflow: visible;font:14px sans-serif\",\n width: width - 40,\n y: {\n grid: true,\n label: \"↑ steps\"\n },\n marks: [\n Plot.ruleY([0]),\n Plot.ruleX([0]),\n Plot.line(sampleDistances, {\n x: \"dist\",\n y: \"steps\",\n z: \"tree\",\n sort: \"dist\",\n stroke: \"tree\"\n }),\n Plot.text(\n sampleDistances,\n Plot.selectLast({\n x: \"dist\",\n y: \"steps\",\n z: \"tree\",\n sort: \"dist\",\n text: \"tree\",\n textAnchor: \"start\",\n dx: 20\n })\n )\n ]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"
\n## Implementation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":222,"value":"margin = 20","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"piece = letterImage","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":133,"value":"pieceImageData = binarizeImageData(getImageData(piece), 128)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":"pieceBalls = {\n if (ballSet == \"SDT+filter\") return ballCoverNew(pieceImageData, epsilon);\n if (ballSet == \"DMA\") return ballCover(pieceImageData);\n const pixelRadius = Math.SQRT2 / 2;\n return piecePoints.map(({ x, y }) => new Ball(x, y, pixelRadius));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"function drawBalls(ctx, balls) {\n for (let { x, y, r } of balls) {\n ctx.beginPath();\n ctx.arc(x, y, Math.max(0.5, r), 0, Math.PI * 2);\n ctx.fill();\n ctx.stroke();\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":186,"value":"function drawPoints(ctx, points) {\n ctx.strokeStyle = \"black\";\n for (let { x, y } of points) {\n ctx.strokeRect(x, y, 0.001, 0.001);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":162,"value":"function drawBoxes(ctx, boxes) {\n ctx.strokeStyle = \"black\";\n for (let b of boxes) {\n let size = b.size();\n ctx.fillRect(b.min.x, b.min.y, size.x, size.y);\n ctx.strokeRect(b.min.x, b.min.y, size.x + 0.01, size.y + 0.01);\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"pieceTree = {\n let tree = bottomUp(pieceBalls);\n return tree;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":704,"value":"pieceTreeHeight = pieceTree.height()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"sampleDistances = btSamples.concat(raSamples)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"function sample(tree, w, h, nx = 30, ny = 30) {\n const dx = (w * 3) / (nx - 1),\n dy = (h * 3) / (ny - 1);\n const x0 = -w,\n y0 = -h;\n let [treeType, dist, stepCount] =\n tree instanceof RA\n ? [\"Rect\", (p) => tree.distance(p), () => tree.distanceSteps]\n : [\"Ball\", (p) => tree.closest(p).dist(p), () => tree.closestSteps];\n let samples = [];\n for (let ix = 0; ix < nx; ix++) {\n let x = x0 + ix * dx;\n for (let iy = 0; iy < ny; iy++) {\n let y = y0 + iy * dy;\n let p = Vec(x, y);\n samples.push({ p, dist: dist(p), steps: stepCount(), tree: treeType });\n }\n }\n return samples;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":729,"value":"raSamples = sample(pieceRaCutTree, piece.width, piece.height)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":739,"value":"btSamples = sample(pieceTree, piece.width, piece.height)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":142,"value":"pieceRaTree = new RA(piecePoints)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":707,"value":"pieceRaTreeHeight = pieceRaTree.height()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":716,"value":"pieceRaCutTree = pieceRaTree.cutTree(raTreeCut).approxTree(nodeFillRate)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":136,"value":"piecePoints = imageDataPoints(pieceImageData)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":770,"value":"groundPoints = imageDataPoints(getImageData(zoomedShape))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1062,"value":"mutable chartsData = null","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1053,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1127,"value":"{\n textSettings, zoom, ballSet, epsilon, raTreeCut;\n mutable chartsData = null;\n return md`*This cell resets the \\`chartsData\\` object whenever parameters change *`;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":994,"value":"$3e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"## Imports","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":10,"value":"import { Vec, Curve, MBR } from \"@esperanc/2d-geometry-utils\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":893,"value":"import {\n RA,\n textImage,\n errorImage,\n rasterizeBoxes,\n imageDataPoints\n} from \"a8b35859f33908c1\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":483,"value":"import {\n ballCover,\n ballCoverNew,\n binarizeImageData,\n getImageData\n} from \"9761ebfa33a5220f\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"import {\n Ball,\n BT,\n kdconstruct,\n bottomUp\n} from \"@esperanc/omohundro-balltree-construction-algorithms\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3f","stdlib":"1"}} 33:null