44:["$","title",null,{"children":"Optimal Ball Trees | Luis Retondaro | Observable"}] 4c:T54d,md`# Optimal Ball Trees This is a collaborative work, based on the good ideas of [Professor Claudio Esperança](https://observablehq.com/@esperanc/omohundro-balltree-construction-algorithms?collection=@esperanc/computacao-grafica). Here, I compare a few different algorithms for constructing balltrees considering new heuristics to perform and improve: (1) smallest total tree area, (2) shortest run time and (3) queries that are efficiently supported by the balltree structure. Ball trees are hierachical bounding structures -- usually binary trees -- where each node consists of a ball (circle, sphere, etc) enclosing all descendant nodes. The problem of building optimal ball trees, i.e., those containing the tightest possible enclosing balls, is clearly exponential on the number of leaves. The many strategies for building ball trees can be classified into two groups: top-down and bottom-up. Bottom-up strategies seem to yield the best results (see ["Five Balltree Construction Algorithms" by Stephen Omohundro, 1989](https://www.icsi.berkeley.edu/icsi/node/2291)). In most strategies, however, the ball at the root of a given subtree is computed as the smallest ball containing the two immediate descendants, while we are interested here in hierarchies where the ball for each node is the *smallest ball enclosing all descendant leaf nodes*. `4d:T57e,kdConstruction = (balls) => { if (balls.length == 1) return new BallTree(new BTNode (new Ball(balls[0].x,balls[0].y,balls[0].r))); const bbox = nodes => { let min = { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY }; let max = { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY }; for (let node of nodes) { let ball = node.ball; min.x = Math.min(ball.x, min.x); min.y = Math.min(ball.y, min.y); max.x = Math.max(ball.x, max.x); max.y = Math.max(ball.y, max.y); } return { min, max }; }; let nodes = balls.map(b => new BTNode(b,null,null)); let build = (nodes) => { if (nodes.length == 1) return nodes[0]; let { min, max } = bbox(nodes); if (max.x - min.x > max.y - min.y) { quickSort(nodes, node => node.ball.x); } else { quickSort(nodes, node => node.ball.y); } let k = Math.floor(nodes.length/2); let left = build(nodes.slice(0, k)); let right = build(nodes.slice(k)); return new BTNode(left.ball.union(right.ball), left, right) } let bnode = build(nodes); return new BallTree( bnode ); }4e:T1693,class OnlineBallTree extends BallTree { constructor(...args) { super(...args); } bestSibling (newLeaf) { /*return the best sibling node ******************************* */ let PQNode = (element, ancestorExpansion) => { let union = element.ball.union(newLeaf.ball); let cost = union.area + ancestorExpansion; let node = element; let aexp = ancestorExpansion; return { node, union, aexp, cost }; }; if (!this.tree) return null; let result = this.tree; let frng = new Heap(pqnode => pqnode.aexp); let tb = result.ball.union(newLeaf.ball); let tf,best; if (result.leaf()) { return result; } else { best = PQNode(result,0.0); frng.push(best); } while (frng.size() > 0) { tf = frng.pop(); if (tf.aexp >= best.cost) { //this is the bound in branch and bound break; } else { let e = tf.aexp + tf.cost - tf.node.ball.area; //new ancestor expansion let v; /* Do left node: ***************** */ if (tf.node.left) { let left = PQNode(tf.node.left,e); if (left.cost < best.cost) { best = left; } frng.push(left); } /* Do right node: ****************** */ if (tf.node.right) { let right = PQNode(tf.node.right,e); if (right.cost < best.cost) { best = right; } frng.push(right); } } } return best.node; } cheaperBestSibling (newLeaf) { if (!this.tree) return null; let result = this.tree; let tb = result.ball.union(newLeaf.ball); let wv = tb.area; let bcost = wv; let ae = 0; //ancestor expansion starts at zero let nd = result; while (!nd.leaf()) { ae=ae+wv-nd.ball.area; //correct for both children if (ae>=bcost) break; //can’t do any better tb = nd.left.ball.union(newLeaf.ball); let left = tb.area; tb = nd.right.ball.union(newLeaf.ball); let right = tb.area; if (ae+left<=bcost) { result = nd.left; bcost = ae+left; } if (ae+right<=bcost) { result= nd.right; bcost = ae+right; } if (left-nd.left.area <= right-nd.right.area) { //left expands less wv = left; nd = nd.left; } else { wv = right; nd = nd.right; } } return nd; } insert (newLeaf,cheaper) { /* Make newLeaf be n’s sibling ******************************** */ let n; if (cheaper) { n = this.cheaperBestSibling(newLeaf); } else { n = this.bestSibling(newLeaf); } if (!this.tree) { this.tree = newLeaf; } else { let b = newLeaf.ball.union(n.ball); let newParent = new BTNode (b,null,null); let nPar = n.parent; if (!n.parent) { this.tree = newParent; //insert at top } else { newParent.parent = nPar; if (Object.is(n.parent.left,n)) { n.parent.left = newParent; } else { n.parent.right = newParent; } } newParent.left = n; newParent.right = newLeaf; newLeaf.parent = newParent; n.parent = newParent; this.repair_parents(newParent); } } repair_parents (n) { if (!n.parent) return; let sibling; if (Object.is(n.parent.left,n)) { sibling = n.parent.right; } else { sibling = n.parent.left; } let index = null; if (n.parent.ball.index) { index = n.parent.ball.index; } n.parent.ball = sibling.ball.union(n.ball); if (index) n.parent.ball.index = index; this.repair_parents(n.parent); } adjust_balls(ns) { if (!ns) return; let index = null; if (ns.ball.index) { index = ns.ball.index; } ns.ball = ns.left.ball.union(ns.right.ball); if (index) ns.ball.index = index; this.adjust_balls(ns.parent); } remove (ball) { let delIndex = null; let n = this.findLeaf(ball); if (!n) { throw "Trying to remove inexistant ball"; } if (!n.parent) { this.tree = null; return; } let sibling; if (Object.is(n.parent.left,n)) { sibling = n.parent.right; } else { sibling = n.parent.left; } if (!n.parent.parent) { this.tree = sibling; } else { if (Object.is(n.parent.parent.left,n.parent)) { n.parent.parent.left = sibling; } else { n.parent.parent.right = sibling; } } sibling.parent = n.parent.parent; this.adjust_balls(sibling.parent); } } 4f:Tb91,function bottomUp(balls,clever=false) { if (balls.length == 1) return new BallTree(new BTNode (new Ball(balls[0].x,balls[0].y,balls[0].r))); let trees = balls.map(b => new BTNode(b,null,null)); let PQNode = (i, j, unionArea) => ({ i, j, unionArea }); let pq = new Heap(pqnode => pqnode.unionArea); let auxtree = new OnlineBallTree(); // Build auxliary tree and priority queue for (let i = 0; i < trees.length; i++) { let best = null; let bestArea = Number.POSITIVE_INFINITY; for (let j = 0; j < trees.length; j++) { if (i == j) continue; let unionArea = trees[i].ball.union(trees[j].ball).area; if (unionArea < bestArea) { bestArea = unionArea; best = PQNode(i, j, bestArea); } } pq.push(best); trees[i].ball.index = i; auxtree.insert(trees[i],clever); } // insert pairs from the priority queue pq while (pq.tree.length > 1) { //console.log("BTUP - pq.tree.length",pq.tree.length); let pqnode = pq.pop(); let pqtop = pq.tree[0]; let { i, unionArea } = pqnode; // Check whether this ball has already been inserted if (!trees[i]) continue; // Recompute the best mate for tree i let ball = trees[i].ball; let nodeBall = trees[i]; auxtree.remove(ball); let mate = auxtree.smallestUnionLeaf(ball); let union = Ball.from(ball.union(mate.ball)); if (union.area <= pqtop.unionArea) { console.assert(ball.index == i); union.index = trees.length; auxtree.remove(mate.ball); let parent = new BTNode(union, trees[ball.index], trees[mate.ball.index]); let auxNode = new BTNode(union, null, null); trees[ball.index] = null; trees[mate.ball.index] = null; trees.push(parent); let bestParentMate = auxtree.smallestUnionLeaf(union); if (!bestParentMate) break; auxtree.insert(auxNode,clever); pq.push( PQNode( union.index, bestParentMate.ball.index, union.union(bestParentMate.ball).area ) ); } else { let auxNode = new BTNode(ball, null, null); auxtree.insert(auxNode,clever); pq.push(PQNode(i, mate.ball.index, union.area)); } } let pqnode = pq.pop(); //if (shrink) trees[trees.length-1].computeEnclosingCircles(); return new BallTree(trees[trees.length - 1]); }50:T783,Q = function(balls,part=0.5) { if (balls.length == 1) return new BallTree(new BTNode (new Ball(balls[0].x,balls[0].y,balls[0].r))); let sortArray = (no) => { quickSort(no, node => node.ball.r); return no } let level = balls.map(b => new BTNode(new Ball(b.x,b.y,b.r),null,null)); while (level.length > 1) { level = sortArray(level); let before = level.length; let newLevel = []; let remainder=[]; for (let i=0; i= before) throw "too slow"; } return new BallTree(level[0]); } 51:T101b,function V0 (balls,ord=3) { if (balls.length == 1) return new BallTree(new BTNode (new Ball(balls[0].x,balls[0].y,balls[0].r))); const bbox = nodes => { let min = { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY }; let max = { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY }; for (let node of nodes) { let ball = node.ball; min.x = Math.min(ball.x, min.x); min.y = Math.min(ball.y, min.y); max.x = Math.max(ball.x, max.x); max.y = Math.max(ball.y, max.y); } return { min, max }; }; const bboxc = center => { let min = { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY }; let max = { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY }; for (let ball of center) { //let ball = node.ball; min.x = Math.min(ball.x, min.x); min.y = Math.min(ball.y, min.y); max.x = Math.max(ball.x, max.x); max.y = Math.max(ball.y, max.y); } return { min, max }; }; let nodes = balls.map(b => new BTNode(b,null,null)); let centersIndex = (nodes) => { let centers = []; let index = []; let aux=[]; for (let i=0; i max.y - min.y) { quickSort(aux, b => b.x); } else { quickSort(aux, b => b.y); } } else if (ord==3) { quickSort(aux, b => b.r); } for (let i=0; i max.y - min.y) { quickSort(nodes, node => node.ball.x); } else { quickSort(nodes, node => node.ball.y); } } else if (ord == 1){ quickSort(nodes, node => node.ball.r); } let count = nodes.length; let centers,index,bestIndex; while (count > 1) { [centers,index] = centersIndex(nodes); let delaunay = d3.Delaunay.from(centers); let voronoi = delaunay.voronoi([0, 0, _width*2 , _width ]); for (let i=0; i new BTNode(b,null,null)); let centersIndex = (nodes) => { let centers = []; let index = []; for (let i=0; i 1) { [centers,index] = centersIndex(nodes); let delaunay = d3.Delaunay.from(centers); let voronoi = delaunay.voronoi([0, 0, _width*2 , _width ]); for (let i=0; i ({ i, j, len }); let PQNodeNeighbor = (j, area) => ({j, area}); let nodes = balls.map(b => new BTNode(b,null,null)); let centersIndex = (nodes) => { let centers = []; let index = []; for (let i=0; i 1) { [centers,index] = centersIndex(nodes); let delaunay = d3.Delaunay.from(centers); let voronoi = delaunay.voronoi([0, 0, _width*2, _width ]); let pq = new Heap(pqnode => pqnode.len); for (let i=0; i pqnode.area); for (let j=0; j 0) { let pqnode = pq.pop(); if (pqnode) { let left = nodes[pqnode.i]; let right = nodes[pqnode.j]; if (left && right) { let bi = left.balls(); let bj = right.balls(); let union = Ball.enclose(bi.concat(bj)); nodes[pqnode.i] = new BTNode(union, left, right); nodes[pqnode.j] = null; bestIndex = pqnode.i; count--; } } } } return new BallTree(nodes[bestIndex]); }54:Td68,function showTree(tree, name = "", desc = "") { let title = md`### ${name}`; let subtitle = md`##### ${desc}` let level = html``; let label = html` Highlight level: `; let area = html` Total area: ${tree.area}`; let cost = html` Average find cost: ${averageFindCost(tree)}`; let closestSteps = html``; let closestInfo = html` Steps to locate closest leaf to query point: `; let intersectingSteps = html``; let intersectingInfo = html` Steps to locate leaf containing query point: `; let smallestUnionSteps = html``; let smallestUnionInfo = html` Steps to locate leaf that yields smallest union with point: `; closestInfo.append(closestSteps); intersectingInfo.append(intersectingSteps); smallestUnionInfo.append(smallestUnionSteps); let width = _width; let canvas = DOM.canvas(width*2, width); let ctx = canvas.getContext("2d"); let mat2d = glmatrix.mat2d; let transform = mat2d.fromScaling([], [1, 1]); //mat2d.translate(transform, transform, [0.25, 0.25]); mat2d.translate(transform, transform, [50, 50]); //mat2d.scale(transform, transform, [0.5, 0.5]); let inverse = mat2d.invert([], transform); let queryBall = new Ball(queryPoint.x, queryPoint.y, 0.0); let refresh = () => { ctx.save(); ctx.clearRect(0, 0, width*2, width); ctx.lineWidth = 1; // / width; ctx.fillStyle = '#0000000a'; ctx.scale(1, 1); //ctx.translate(0.25, 0.25); //ctx.scale(0.5, 0.5); ctx.translate(50, 50); tree.draw(ctx); ctx.strokeStyle = 'red'; ctx.fillStyle = '#ff000020'; ctx.lineWidth = 3;// / width; tree.drawLevel(ctx,level.value); let closest = tree.closest(queryPoint)[0]; closestSteps.innerHTML = tree.closestSteps; let intersecting = tree.intersecting(queryPoint); intersectingSteps.innerHTML = (intersecting ? "(successful) " : "(unsuccessful) ") + tree.intersectingSteps; let smallestUnionNode = tree.smallestUnionLeaf(queryBall); let smallestUnion = smallestUnionNode.ball.union(queryBall); smallestUnionSteps.innerHTML = tree.smallestUnionSteps; ctx.fillStyle = '#0000ff70'; ctx.strokeStyle = 'blue'; closest.ball.draw(ctx); ctx.fillStyle = '#ffffff70'; if (intersecting) intersecting.ball.draw(ctx); ctx.setLineDash([3, 3]); ctx.strokeStyle = 'green'; smallestUnionNode.ball.draw(ctx); smallestUnion.draw(ctx, false, true); ctx.setLineDash([]); ctx.strokeStyle = 'blue'; ctx.beginPath(); ctx.moveTo(queryPoint.x - 2, queryPoint.y); ctx.lineTo(queryPoint.x + 2, queryPoint.y); ctx.moveTo(queryPoint.x, queryPoint.y - 2); ctx.lineTo(queryPoint.x, queryPoint.y + 2); ctx.stroke(); ctx.restore(); }; canvas.onclick = e => { let [x, y] = vec2.transformMat2d([], [e.offsetX, e.offsetY], inverse); mutable queryPoint = { x, y }; refresh(); }; refresh(); level.oninput = () => refresh(); return html`

${title}${subtitle}${label} ${level}
${area}
${cost}
${closestInfo}
${intersectingInfo}
${smallestUnionInfo}
${canvas}

`; }55:T470,specific_balls = [ new Ball ( 205, 300, 10), new Ball ( 140, 290, 10), new Ball ( 175, 230, 10), new Ball ( 330, 85, 10), new Ball ( 360, 280, 10), new Ball ( 435, 185, 10), new Ball ( 15, 320, 10), new Ball ( 145, 240, 10), new Ball ( 80, 289, 10), new Ball ( 350, 150, 10), new Ball ( 180, 300, 10), new Ball ( 55, 20, 10), new Ball ( 455, 100, 10), new Ball ( 370, 200, 10) /* {x:567.74, y:134.52, r:31.53}, {x:317.9, y:142.29, r:15.07}, {x:574.89, y:224.415, r:28.73}, {x:517.25, y:249.52, r:30.98}, {x:419.39, y:221.38, r:67.09}, {x:274.10, y:206.86, r:27.61}, {x:312.97, y:238.75, r:28.78}*/ ] 56:[{"id":"65352a86799e497d9ca269831d4b7159ee3a62fde83aec11712969ed81ef2a437d4acec84c69fbf4dc8bc50c0808101c9b3462ef3b74d6909d5d8ef0ee4c3ac3","href":"https://static.observableusercontent.com/files/65352a86799e497d9ca269831d4b7159ee3a62fde83aec11712969ed81ef2a437d4acec84c69fbf4dc8bc50c0808101c9b3462ef3b74d6909d5d8ef0ee4c3ac3","name":"cristo@2.csv","type":"text/csv","lastModified":1611749017926.623,"size":10875},{"id":"06164b2da9778f172faf2f7f59a6eb5eeb1fdf8d6b630095e20dac2f458d87f633822401fb6764d3459710588e3ff4c20b124561f0f2e22cf26e08aef755f994","href":"https://static.observableusercontent.com/files/06164b2da9778f172faf2f7f59a6eb5eeb1fdf8d6b630095e20dac2f458d87f633822401fb6764d3459710588e3ff4c20b124561f0f2e22cf26e08aef755f994","name":"car@1.csv","type":"text/csv","lastModified":1611749017926.623,"size":26220},{"id":"6df9555db3ec69468ac0a444c4f38a356c936bcd89fc591786ec9bbe6c7639f3bb650960dba81cb527d9b60033706b9831047b57151b4b3c869ecaa5b72acaf0","href":"https://static.observableusercontent.com/files/6df9555db3ec69468ac0a444c4f38a356c936bcd89fc591786ec9bbe6c7639f3bb650960dba81cb527d9b60033706b9831047b57151b4b3c869ecaa5b72acaf0","name":"fish.csv","type":"text/csv","lastModified":1611749017926.623,"size":17492},{"id":"52341dbe4be128df6fcd598b12491ff22af5a9d0038c169c53c58b0f316e24a006e48275832aaa6f954e15213ae5541d8163241e03b1bf846f454609a094a3f4","href":"https://static.observableusercontent.com/files/52341dbe4be128df6fcd598b12491ff22af5a9d0038c169c53c58b0f316e24a006e48275832aaa6f954e15213ae5541d8163241e03b1bf846f454609a094a3f4","name":"pangram.csv","type":"text/csv","lastModified":1611749017926.623,"size":34958},{"id":"6ca1e5076ec4cbf4a54960521435325ca13fd251dba59ed5f8bd7db4f14f47f7677ef35f40ef1d03f7f598fd53c0177bbc91abefa53a7bf4b0809fe20f20e5fb","href":"https://static.observableusercontent.com/files/6ca1e5076ec4cbf4a54960521435325ca13fd251dba59ed5f8bd7db4f14f47f7677ef35f40ef1d03f7f598fd53c0177bbc91abefa53a7bf4b0809fe20f20e5fb","name":"sites.csv","type":"text/csv","lastModified":1611749017926.623,"size":8845}] 48:{"id":"583cfa2fcd89361e","slug":"optimal-ball-trees","title":"Optimal Ball Trees","thumbnail":"1b01f55ac39da00b71d202dd16f6471f7a34d9e4f68cd8218a34df73608b7265","access_level":"public","create_time":"$D2021-01-27T12:03:37.926Z","update_time":"$D2022-03-24T18:51:00.864Z","view_time":null,"first_public_time":"$D2021-03-17T17:53:37.186Z","has_unpublished_edits":null,"fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":"starter_2024","bio":".","followed_by_you":false,"follows_you":false},"version":15661,"publish_version":15661,"role":null,"authored":false,"authors":[{"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":"146ee3f34bbcc61d","login":"lretondaro","name":"Luis Retondaro","avatar_url":"https://avatars-next.observableusercontent.com/d5e7faa70402437c197456859137585a1f5ae86f61b37fee567d63511c467d09","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"0781ac0b2927381a","slug":"wip","title":"WIP","owner":{"id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro"}},"type":"notebook","body":{"titling":"auto","title":"Optimal Ball Trees","cells":[{"id":0,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1986,"value":"md `## Interactive Demo`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1038,"value":"{\n let painel0 = html `

Data Simulation: ${bindSelect({options:syms}, viewof _simulation)}

`\n let painel1 = html `\n Balls: ${bindSlider({min:4, max:2000, step: 1,size:'100px'}, viewof _numberOfBalls)} ${bindNumber({min:4, max:2000, step: 1,size:'50px'}, viewof _numberOfBalls)} Distribution: ${bindRadioGroup ({options:['Random','Cantor']}, viewof _distribution)} Uniform mode: ${bindCheckbox('_uniform', viewof _uniform)}
`\n \n if (_simulation == syms[0]) {\n return md `${painel0}${painel1}`;\n } else {\n return md `${painel0}`;\n }\n\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13520,"value":"title(\"Examples:\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13772,"value":"showTree(BTKdOrig[0], \"KD Construction algorithm\",\"Top-down approach\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13722,"value":"showTree(BTOnlineOrig[0], \"Online algorithm\",\" \")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14892,"value":"showTree(BTBottomUp[0], \"Bottom-up algorithm\",\" \")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14494,"value":"showTree(BTQ[0], \"Q(0.2) algorithm\",\"Quadratic\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15506,"value":"showTree(BTQ[1], \"Q(0.5) algorithm\",\"Quadratic\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14681,"value":"showTree(BTV0[3], \"V0 algorithm\",\"voronoi-based\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14583,"value":"showTree(BTV1[0], \"V1 algorithm\",\"voronoi-based\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5267,"value":"md `## Implementation`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13994,"value":"md `### Algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13761,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13651,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15586,"value":"function Online (balls) {\n let Bt = new OnlineBallTree();\n for (let b of balls) {\n let n = new BTNode(b, null, null);\n Bt.insert(n);\n }\n return Bt;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13747,"value":"bottomUpBF = (balls) => {\n if (balls.length == 1) return new BallTree(new BTNode (new Ball(balls[0].x,balls[0].y,balls[0].r)));\n \n let nodes = balls.map(b => new BTNode(b,null,null));\n \n while (nodes.length > 1) {\n let best = null,\n bestArea = 1e10;\n for (let i = 0; i < nodes.length; i++) {\n for (let j = i + 1; j < nodes.length; j++) {\n let union = nodes[i].ball.union(nodes[j].ball);\n if (union.area < bestArea) {\n best = [i, j, union];\n bestArea = union.area;\n }\n }\n }\n let [i, j, union] = best;\n nodes[i] = new BTNode(union, nodes[i], nodes[j]);\n nodes.splice(j, 1);\n }\n \n let b = new BallTree(nodes[0]);\n \n return b;\n}\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15035,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15497,"value":"$50","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15525,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15409,"value":"$52","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15354,"value":"$53","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14003,"value":"md `### Ball trees`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13768,"value":"BTKdOrig = {\n let t0 = performance.now();\n let b = kdConstruction(balls,false);\n let t1 = performance.now();\n return [b,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13703,"value":"BTOnlineOrig = {\n let debug = [];\n let t0 = performance.now();\n let Bt = Online(balls)\n /*let Bt = new OnlineBallTree();\n for (let b of balls) {\n let n = new BTNode(b, null, null);\n Bt.insert(n);\n }*/\n let t1 = performance.now();\n return [Bt,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15250,"value":"BTOnlineShrink = {\n let debug = [];\n let t0 = performance.now();\n let Bt = new OnlineBallTree();\n for (let b of balls) {\n let n = new BTNode(b, null, null);\n Bt.insert(n);\n }\n Bt.tree.computeEnclosingCircles();\n let t1 = performance.now();\n return [Bt,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13753,"value":"/*BTBottomUpBF = bottomUpBF(balls)*/","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14886,"value":"BTBottomUp = {\n let t0 = performance.now();\n let b = bottomUp(balls,false,true);\n let t1 = performance.now();\n return [b,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13833,"value":"BTBottomUpCheaper = { let t0 = performance.now();\n let b =bottomUp(balls,true,true);\n let t1 = performance.now();\n return [b,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15501,"value":"BTQ = { \n let t0 = performance.now();\n let b = Q(balls,0.2);\n let t1 = performance.now();\n let b2 = Q(balls,0.5);\n let t2 = performance.now();\n return [b,b2,t1-t0,t2-t1];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15277,"value":"BTV0 = { \n let t0 = performance.now();\n let b = V0(balls,0);\n let t1 = performance.now();\n let b1 = V0(balls,1);\n let t2 = performance.now();\n let b2 = V0(balls,2);\n let t3 = performance.now();\n let b3 = V0(balls,3);\n let t4 = performance.now();\n return [b,b1,b2,b3,t1-t0,t2-t1,t3-t2,t4-t3];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15412,"value":"BTV1 = { \n let t0 = performance.now();\n let b = V1(balls);\n let t1 = performance.now();\n return [b,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14677,"value":"BTV2 = { \n let t0 = performance.now();\n let b = V2(balls);\n let t1 = performance.now();\n return [b,t1-t0];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13997,"value":"md `### Library`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14690,"value":"// Locates every leaf of the tree starting from the root and returns\n// the average number of steps required\nfunction averageFindCost(tree) {\n let totalSteps = 0;\n let n = 0;\n let lb = tree.leafBalls();\n let task = false;\n let nb = null;\n for (let node of lb) {\n n++;\n let result = tree.findLeaf(node.ball);\n console.assert(result);\n totalSteps += tree.findSteps;\n if (!result) throw \"Something Wrong with find\";\n }\n return totalSteps / n;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":638,"value":"function remove(array, element) {\n const index = array.indexOf(element);\n if (index !== -1) {\n array.splice(index, 1);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":8545,"value":"shuffleArray = (arr) => {\n let result = [];\n let s = shuffle(arr.length);\n for (let i=0; i {\n return html `

${txt}

`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13576,"value":"$54","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14950,"value":"function shapeData (shape) {\n let result = [];\n for (let i=0; i ([\n //Math.random(),\n //Math.random(),\n getRandomArbitrary(2,180),\n getRandomArbitrary(2,180),\n _uniform? 3:getRandomArbitrary(5,15)\n ]))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13642,"value":"coordBalls = () => {\n let result = [];\n for (let i=0; i 0.5 ? 3 : 1;\n let n = len;\n let nmin = 0;\n let nmax = len;\n for (let i=0;i 0.5 ? 3 : 1;\n }\n n = getRandomArbitrary(nmin, nmax);\n return n;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1243,"value":"viewof _numberOfBalls = new View(8)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4496,"value":"viewof _distribution = new View('Random')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10935,"value":"viewof _uniform = new View(true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6933,"value":"viewof _simulation = new View(syms[0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5312,"value":"colors = [\"blue\",\"orangered\",\"lime\",\"goldenrod\",\"mediumseagreen\",\"purple\", \"yellow\"];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7616,"value":"syms = [\"Custom\",\"Rabbit\",\"Pangram\",\"Fish\",\"Car\",\"Rio\",\"Specific\"]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7135,"value":"md `## CSS`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7132,"value":"util_styles = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15407,"value":"DOM.download(new Blob([d3.csvFormat(balls)], {type: \"text/csv\"}), \"balls.csv\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15347,"value":"DOM.download(serialize(balls), null, \"Download CSV\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15345,"value":"function serialize (data) {\n let parser = new json2csv.Parser();\n let csv = parser.parse(data);\n return new Blob([csv], {type: \"text/csv\"}) \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"md `## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14716,"value":"glmatrix = import('https://unpkg.com/gl-matrix@3.3.0/esm/index.js?module')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14720,"value":"vec2 = glmatrix.vec2","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13655,"value":"import {Heap, Queue, Stack, Ball, BallTree, BTNode} from '@lretondaro/basic-data-structures'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13812,"value":"import {quickSort} from '@lretondaro/utils-library' ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"d3 = require(\"d3@5\", \"d3-delaunay@^5.2\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1138,"value":"import { bind, bindSelect, bindSliderNumber, bindSlider, bindNumber, bindCheckbox, bindCheckGroup, bindRadioGroup, View} from \"@esperanc/inline-inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13027,"value":"math = require(\"mathjs@7.6.0\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":14772,"value":"import { Vector, Vec } from \"@esperanc/2d-geometry-utils\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15343,"value":"json2csv = require(\"json2csv\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W56","stdlib":"1"}} 24:null