44:["$","title",null,{"children":"Quadtree vs R-tree | Fati CHEN | Observable"}] 4c:T42b,{ if (preview === null) { return md`**Select a row in the table to preview**`; } const trees = [showquadtree({ showRegions }), showrtree({ showRegions })]; const quadtree = showquadtree(); const rtree = showrtree(); const $div = htl.html`

${md`Hover to see the retrieved candidates (in blue) and those who are within the mouse perimeter in green.`}

${trees}`; const trott = _.throttle( function (e) { const pointer = d3.pointer(e); trees.map(async (tree) => tree.value(...pointer, mouseRadius, timeSamples) ); }, 30, // trailing: true makes it very jiggly :( { leading: true, trailing: false } ); d3.select($div) .selectAll("canvas") .on("pointermove click pointerout", null) .on("pointermove click", trott) .on("pointerout", function (e) { const pointer = d3.pointer(e); trees.map(async (tree) => tree.value(...pointer, 0, timeSamples)); }); return $div; }4d:Ta2d,function figure({ regions = [], preview = { radius: 0, shape: 0 }, size = 512, drawRegion = (i) => i, retrieve = () => [], foundCircle = (i) => i, showRegions = true, mouseRadius = 10 } = {}) { const shape = 2 * preview.radius + preview.shape; const scale = size / shape; const invscale = shape / size; const context = DOM.context2d(size, size); const regionsctx = DOM.context2d(size, size); // yield context.canvas; context.scale(scale, scale); regionsctx.scale(scale, scale); function drawRegions(context) { context.globalAlpha = points.length > 200 ? 0.4 : 0.8; context.strokeStyle = `#000`; regions.forEach(drawRegion(context)); } if (showRegions) drawRegions(regionsctx); const $time = htl.html``; const $measure = htl.html``; const $count = htl.html``; const $div = htl.html`

${context.canvas}

it took ${$time}ms mean(${$measure}) to find the ${$count} overlap candidates.`; let times = []; function draw(x, y, mouseRadius, samples = 30) { context.clearRect(0, 0, shape, shape); context.drawImage(plotPoints, 0, 0, shape, shape); context.drawImage(regionsctx.canvas, 0, 0, shape, shape); const mouseCircle = { x: x * invscale, y: y * invscale, r: mouseRadius }; const start = performance.now(); const found = retrieve(mouseCircle); const end = performance.now(); if (found.length > 0) { times.push(end - start); times = times.slice(-samples); $time.textContent = d3.mean(times).toFixed(2); $measure.textContent = times.length; } context.globalAlpha = 1; context.strokeStyle = "#000"; for (const f of found) { context.beginPath(); context.lineWidth = 1; const c = foundCircle(f); context.arc(c.x, c.y, c.r, 0, 2 * Math.PI); context.fillStyle = overlap(c, mouseCircle) ? "green" : "#3388ff"; context.stroke(); context.fill(); } context.fillStyle = "red"; context.beginPath(); context.lineWidth = 5; context.arc(mouseCircle.x, mouseCircle.y, mouseCircle.r, 0, 2 * Math.PI); context.stroke(); } draw(); const trott = _.throttle( function (e) { draw(...d3.pointer(e), mouseRadius); }, 30, // trailing: true makes it very jiggly :( { leading: true, trailing: false } ); d3.select(context.canvas) .style("touch-action", "none") .style("cursor", "crosshair") .on("pointermove click", trott) .on("pointerout", function (e) { draw(...d3.pointer(e), 0); }); return Object.assign($div, { value: draw }); }4e:[] 48:{"id":"0ce5fc26b8a29fa6","slug":"quadtree-vs-rtree","title":"Quadtree vs R-tree","thumbnail":"5deeb1da565859f5079e6478f767fd7413c2de30f5cb53f51def4284ca96b4a2","access_level":"public","create_time":"$D2021-09-30T12:26:25.218Z","update_time":"$D2022-06-25T14:32:33.588Z","view_time":null,"first_public_time":"$D2021-09-30T21:09:01.588Z","has_unpublished_edits":null,"fork":false,"stars":15,"starred":false,"owner":{"type":"team","id":"ffbcf8ce47e293f4","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":"starter_2024","bio":"Ph.D in DataViz","followed_by_you":false,"follows_you":false},"version":1087,"publish_version":1087,"role":null,"authored":false,"authors":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null,"bio":"Ph.D in DataViz","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"7affeb11879b11eb","login":"stardisblue","name":"Fati CHEN","avatar_url":"https://avatars-next.observableusercontent.com/c3f14cf2d58aebca19459fc111e35113235be85745ae353f37b7731ea9a84d79","tier":null,"role":"editor"}],"comments":[{"id":"bd1eecac4140e432","reply_to_id":null,"content":"I recommend setting a default selection for the table. Otherwise it's not immediately apparent that rows can be selected to show their trees.","create_time":"$D2021-10-09T09:43:47.555Z","update_time":null,"resolved":true,"user":{"type":"individual","id":"07362516b5994994","login":"mootari","name":"Fabian Iwand","avatar_url":"https://avatars-next.observableusercontent.com/0d7defa821f38094c03bad23b9b360a5364e6e97e21fc238c39ddc48db7994ad","tier":null}}],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Quadtree vs R-tree","cells":[{"id":0,"value":"# Quadtree vs R-tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":918,"value":"I'm all in if you have any idea of how to improve perf on either of these algorithms :), please comment :)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"viewof preview = Inputs.table(filtered, {\n multiple: false,\n sort: \"qte\",\n format: {\n samples: (s) =>\n histogram(s, {\n domain: [0, 1],\n thresholds: 20,\n width: 100,\n color: { fill: \"#1e90ff\" },\n domainline: { size: 0.25, stroke: \"black\" }\n })\n // radius: (s) =>\n // svg`