45:["$","title",null,{"children":"Optimized 2D Ball trees | Luis Retondaro | Observable"}] 4d:T471,{ if (_abstract) { return md `** *Abstract:* ** ${tex `-`} Ball trees are hierarchical bounding structures – usually binary trees – where each node consists of a ball (circle, sphere, etc) enclosing its children. Approaches for building an optimal ball tree for a given set of leaves (points or balls enclosing other geometric primitives) typically rely on minimizing some function of the shape of the tree, regardless of the intended application. In this paper we examine the problem of building ball trees for 2D primitives, trying to balance construction time with the efficiency of the produced trees with respect to a set of distance-based queries. In particular, we present three new construction algorithms, propose an optimization whereby each internal node is the smallest ball enclosing all leaves rooted at that node, and describe enhancements to several distance query algorithms. Moreover, an extensive experimental study was conducted in order to evaluate our algorithms with different kinds of data sets, including ball collections that approximate 2D shapes.

` } else { return html `

` } }4e: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 ); }4f:Tb09,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) { 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(); 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:Tfaf,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) { 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 0) { // If the parent has a lesser score, things are in order and we are done. if (score >= this.scoreFunction(this.tree[this.parent(i)])) break; // Otherwise, swap the parent with the current element and continue. this.swap(this.parent(i),i); i = this.parent(i); } } // Moves element at position n towards the bottom as necessary siftDown(i) { // Fetch the element that has to be moved. let element = this.tree[i]; let score = this.scoreFunction(element); let swap = null; // If the score is less than its children elements we need to swap. let left = this.left(i); if (left <= this.tree.length-1) { var child1Score = this.scoreFunction(this.tree[left]); if (child1Score < score) { swap = left; } } let right = this.right(i) if (right <= this.tree.length-1) { var child2Score = this.scoreFunction(this.tree[right]); if (child2Score < (swap == null ? score : child1Score)) { swap = right; } } if (swap) { this.swap(i,swap); this.siftDown(swap); } } // Adds a new element to the heap push(newNode) { // Add the new element to the end of the array. this.tree.push(newNode); // Allow it to sift up. this.siftUp(this.tree.length-1); } // Removes the top of the heap and returns it pop() { if (this.tree.length == 0) return null; // Store the first element so we can return it later. let result = this.tree[0]; // Get the element at the end of the array let end = this.tree.pop() if (this.tree.length > 0) { // Put the end element at the root this.tree[0] = end; // Allow new root element to sift down. this.siftDown(0); } return result; } // Changes the score of node. // This is useful, if H is behaving like a priority queue changePriority(i, p) { if (i < 0) return; let element = this.tree[i]; this.changeScore(element,p); // allow it to sift up or sift down as appropriate. this.siftUp(i); this.siftDown(i); } index(node) { let length = this.tree.length; for (let i=0; i= 0 && (dr * dr)+epsilon > dx * dx + dy * dy; } // returns true iff this ball contains point p containsPoint(p) { let epsilon = 0.001; const dx = this.x - p.x; const dy = this.y - p.y; return (dx * dx + dy * dy) <= (this.r * this.r)+epsilon; } // Returns true iff this b ⊆ this for all b ∈ others. enclosesAll(others) { for (let b of others) if (!this.encloses(b)) return false; return true; } // returns smallest enclosing ball containing this and other union(other) { if (other.encloses(this)) return other; if (this.encloses(other)) return this; const { x: x1, y: y1, r: r1 } = this; const { x: x2, y: y2, r: r2 } = other; const x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1; const l = Math.sqrt(x21 * x21 + y21 * y21); return new Ball( (x1 + x2 + (x21 / l) * r21) / 2, (y1 + y2 + (y21 / l) * r21) / 2, (l + r1 + r2) / 2 ); } // returns true iff the smallest enclosing ball of a and b is neither a nor b static isBasis2(a, b) { return !a.encloses(b) && !b.encloses(a); } // Returns true iff the set {a, b, c} forms a basis. static isBasis3(a, b, c) { return ( Ball.isBasis2(a, b) && !a.union(b).encloses(c) && Ball.isBasis2(a, c) && !a.union(c).encloses(b) && Ball.isBasis2(b, c) && !b.union(c).encloses(a) ); } // If three balls form a 'basis' (see isBasis3), computes the // smallest enclosing circle of these static encloseBasis3(a, b, c) { const { x: x1, y: y1, r: r1 } = a; const { x: x2, y: y2, r: r2 } = b; const { x: x3, y: y3, r: r3 } = c; const a2 = x1 - x2; const a3 = x1 - x3; const b2 = y1 - y2; const b3 = y1 - y3; const c2 = r2 - r1; const c3 = r3 - r1; const d1 = x1 * x1 + y1 * y1 - r1 * r1; const d2 = d1 - x2 * x2 - y2 * y2 + r2 * r2; const d3 = d1 - x3 * x3 - y3 * y3 + r3 * r3; const ab = a3 * b2 - a2 * b3; const xa = (b2 * d3 - b3 * d2) / (ab * 2) - x1; const xb = (b3 * c2 - b2 * c3) / ab; const ya = (a3 * d2 - a2 * d3) / (ab * 2) - y1; const yb = (a2 * c3 - a3 * c2) / ab; const A = xb * xb + yb * yb - 1; const B = 2 * (r1 + xa * xb + ya * yb); const C = xa * xa + ya * ya - r1 * r1; const r = -(A ? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A) : C / B) + 0.2; return new Ball(x1 + xa + xb * r, y1 + ya + yb * r, r + 0.5); } // Given a basis B and a circle p ⊈ B, returns the new basis Bʹ. static extendBasis(B, p) { var i, j; if (p.enclosesAll(B)) return [p]; // If we get here then B must have at least one element. for (i = 0; i < B.length; ++i) { if (!p.encloses(B[i]) && p.union(B[i]).enclosesAll(B)) { return [B[i], p]; } } // If we get here then B must have at least two elements. for (i = 0; i < B.length - 1; ++i) { for (j = i + 1; j < B.length; ++j) { if ( !B[i].union(B[j]).encloses(p) && !B[i].union(p).encloses(B[j]) && !B[j].union(p).encloses(B[i]) && Ball.encloseBasis3(B[i], B[j], p).enclosesAll(B) ) { return [B[i], B[j], p]; } } } // If we get here then something is very wrong. throw new Error(); } // Returns a ball enclosing all balls in L static enclose(L) { const encloseBasis = B => { switch (B.length) { case 1: return Ball.from(B[0]); case 2: return B[0].union(B[1]); case 3: return Ball.encloseBasis3(B[0], B[1], B[2]); } }; var i = 0, n = d3.shuffle((L = L.slice())).length, B = [], p, e; while (i < n) { p = L[i]; if (e && e.encloses(p)) ++i; else (e = encloseBasis((B = Ball.extendBasis(B, p)))), (i = 0); } return e; } // Returns this ball expanded so that it includes at least one point of other expand(other) { const { x: x1, y: y1, r: r1 } = this; const { x: x2, y: y2, r: r2 } = other; const x21 = x2 - x1, y21 = y2 - y1, r21 = r2 - r1; const l = Math.sqrt(x21 * x21 + y21 * y21); if (l <= this.r + other.r) return this; const R = (l - r2 + r1) / 2; return new Ball(x1 + (x21 * (R - r1)) / l, y1 + (y21 * (R - r1)) / l, R); } distance(other) { return Math.max(0, this.center.dist(other.center)-this.r-other.r); } // Returns the distance from a point to this ball dist(p) { return Math.max( 0, Math.sqrt((this.x - p.x) ** 2 + (this.y - p.y) ** 2) - this.r ); } // Area of this ball get area() { return this.r * this.r * Math.PI; } draw(ctx,center) { ctx.beginPath(); ctx.arc(this.x, this.y, this.r, 0, Math.PI * 2); ctx.stroke(); ctx.fill(); if (center) { ctx.beginPath(); ctx.moveTo(this.x - this.r/20, this.y); ctx.lineTo(this.x + this.r/20, this.y); ctx.moveTo(this.x, this.y - this.r/20); ctx.lineTo(this.x, this.y + this.r/20); ctx.stroke(); } } translate(p) { this.x = this.x+p.x; this.y = this.y+p.y; } scale(f) { this.x = this.x*f; this.y = this.y*f; this.r = this.r*f; } mirror(pivot, x,y) { let px = (pivot.x - this.x)*2; let py = (pivot.y - this.y)*2; if (x) this.x = this.x+px; if (y) this.y = this.y+py; } rotate(alpha,pivot) { let radians = alpha*Math.PI/180; let u = Vec(this.x,this.y).sub(pivot); let x = u.x*Math.cos(radians) - u.y*Math.sin(radians); let y = u.x*Math.sin(radians) + u.y*Math.cos(radians); let z = Vec(x,y).add(pivot); this.x = z.x; this.y = z.y; } perpendicularPoint(p) { let u = p.sub(Vec(this.x,this.y)); let x = -u.y; let y = u.x; return Vec(this.x,this.y).sub(Vec(x,y)); } intersectionArea (other) { let pa = Vec(this.x,this.y); let pb = Vec(other.x,other.y); let d = pa.dist(pb); let dx = other.x-this.x; let dy = other.y-this.y; let [r,R] = [this.r,other.r]; //Case 1: if (d >= r+R) return 0; //Case 2: if (d <= Math.abs(r-R)) { if (r 1.0) x1 = x1>0.0?x1/x1:-(x1/x1); if (Math.abs(x2) > 1.0) x2 = x2>0.0?x2/x2:-(x2/x2); //Other cases: return r*r * Math.acos(x1) + R*R * Math.acos(x2) - 0.5 * Math.sqrt((-d+r+R)*(d+r-R)*(d-r+R)*(d+r+R)); } intersectionPoints (other) { let pa = Vec(this.x,this.y); let pb = Vec(other.x,other.y); let d = pa.dist(pb); let dx = other.x-this.x; let dy = other.y-this.y; let [r,R] = [this.r,other.r]; //Case 1: if (d >= r+R) return null; //Case 2: if (d <= Math.abs(r-R)) return null; let d1 = (d*d + r*r - R*R) / (2*d); let d2 = (d*d + R*R - r*r) / (2*d); /* P1 and P2 = Intersection points: P0 is the point where the line through the circle intersection points crosses the line between the circle centers. *******************************************/ let P0 = Vec(this.x + (dx * d1/d), this.y + (dy * d1/d)); /* Determine the distance from P0 to either of the intersection points (P1 and P2). */ let h = Math.sqrt((this.r*this.r) - (d1*d1)); /* Now determine the offsets of the intersection points from P0. */ let rx = -dy * (h/d); let ry = dx * (h/d); let P1 = Vec(P0.x + rx, P0.y + ry); let P2 = Vec(P0.x - rx, P0.y - ry); return [P1, P2]; } separate (other,c1,c2) { let offset; let v = (p,c) => { let v0 = c.sub(p); if (v0.mag() > 0) return v0.normalize(); } let pa = this.center; let pb = other.center let [va, vb] = [v(pa,c1), v(pb,c2)]; let [resultA, resultB] = [ Vec(0,0), Vec(0,0) ]; let d = pa.dist(pb); let dx = other.x-this.x; let dy = other.y-this.y; let [r,R] = [this.r,other.r]; //Case 1: if (d >= r+R) return null; //Case 2: if (d <= Math.abs(r-R)) { offset = d; if (r 0) return c.add(v.normalize().scale(this.r)); return c; } //finds the point on the circle closest to segment line (p,q) and computes the distance closestLine(p,q) { var s = p.dist(q); if (s < 0.00001) return [this.closestPoint(p), this.center.dist(p)]; var v = q.sub(p).scale(1.0/s); var u = this.center.sub(p); var d = u.dot(v); if (d < 0) return [this.closestPoint(p), Math.max(0,this.center.dist(p)-this.r) ]; if (d > s) return [this.closestPoint(q), Math.max(0,this.center.dist(q)-this.r) ]; let pmix = p.mix(q,d/s); return [this.closestPoint(pmix), Math.max(0,pmix.dist(this.center)-this.r)]; } }55:T7b8,class BTNode { constructor (ball, nodeLeft, nodeRight) { this.parent = null; this.left = nodeLeft; this.right = nodeRight; this.ball = ball; if (nodeLeft && (nodeLeft instanceof BTNode)) nodeLeft.parent = this; if (nodeRight && (nodeRight instanceof BTNode)) nodeRight.parent = this; this.epsilon = 0; this.translated = 0; this.visited = false; } leaf() { return !(this.left || this.right) } leaves() { let result = []; let traverse = (node) => { if (node.leaf()) { result.push(node); } traverse(node.left); traverse(node.right); } if (this.leaf()) return [this]; traverse(this); return result; } balls() { let result = []; let traverse = (node) => { if (node.leaf()) { result.push(node.ball); return; } traverse(node.left); traverse(node.right); } if (this.leaf()) return [this.ball]; traverse(this); return result; } encloseLeaves(other) { let b1 = this.balls(); let b2 = other.balls(); let union = b1.concat(b2); let test = Ball.enclose(union); //d3.packEnclose(union); return test; } // Reduces the bounding balls from internal nodes to those // enclosing only the leaves computeEnclosingCircles() { if (!this.leaf()) { let cc = this.balls(); let bv = d3.packEnclose(cc); //Ball.enclose(cc); this.ball = new Ball (bv.x,bv.y,bv.r); this.left.computeEnclosingCircles(); this.right.computeEnclosingCircles(); } } }56:T612e,class BallTree { constructor(node) { this.tree = node; this.findSteps = 0; this.closestSteps = 0; this.closestLeavesSteps = 0; this.visited = []; this.intersectingSteps = 0; this.smallestUnionSteps = 0; this.intersectedSteps = 0; this.intersectingLine = 0; this.closestSegSteps = 0; } origin() { let dx = -(this.tree.ball.x); let dy = -(this.tree.ball.y); this.translate(Vec(dx,dy)); } normalize() { let dimension = this.tree.ball.r*2; let traverse = (node) => { node.ball = new Ball (node.ball.x/dimension, node.ball.y/dimension, node.ball.r/dimension); if (node.left) traverse(node.left); if (node.right) traverse(node.right); } if (this.tree) traverse(this.tree); } // Creates a copy of other BallTree static from(other) { let newBT = null; let traverse = (node,parent,child) => { let newNode; if (!parent) { newNode = newBT.tree; } else { let newBall = new Ball (node.ball.x, node.ball.y, node.ball.r); newNode = new BTNode(newBall,null,null); } newNode.parent = parent; if (child == "left") { parent.left = newNode; } else if (child == "right") { parent.right = newNode; } if (node.left) traverse(node.left,newNode,"left"); if (node.right) traverse(node.right,newNode,"right"); } if (other) { let newBall = new Ball (other.tree.ball.x, other.tree.ball.y, other.tree.ball.r); let n = new BTNode(newBall,null,null); newBT = new BallTree(n); traverse(other.tree,null,"start"); } return newBT; } //set automatic epsilon value :: increment epsilon (collision distance) to all levels setEpsilon(min, max) { //min = applied on the leaf :: max = applied on the root let h = this.height(); if (h < 2) return; let f = (max - min) / (h); let epsilon = max; //initial value to epsilon this.bfs(function(node) { if (node) { if (node.leaf()) { node.epsilon = min; } else { node.epsilon = epsilon; } } else { epsilon -= f; } }); } //The depth-first search algorithm preorder: dfs(node, callback) { let stack = new Stack(); stack.push(node); while (!stack.isEmpty()) { let pointer = stack.pop(); callback(pointer); if (pointer.left) { stack.push(pointer.right); stack.push(pointer.left); } } } //The breadth-first search algorithm (level by level) bfs(callback) { let queue = new Queue(); queue.enqueue(this.tree); queue.enqueue(null); let pointer = queue.dequeue(); let finish = false; while(!finish){ if (pointer == null) { callback(null); if (queue.items.length > 0) { queue.enqueue(null); } else { finish = true; } } else { callback(pointer); } if (pointer instanceof BTNode) { if (pointer.left) { queue.enqueue(pointer.left); queue.enqueue(pointer.right); } } pointer = queue.dequeue(); } } // Height of the tree get height() { let n = -1 this.bfs(function(node) { if (!node) { n++ } }); return n; } get center() { // Returns the center of an array of 2d points let pts = this.leafCenters(); if (pts.length == 0) return null; let sum = [0,0]; for (let i=0; i { if (node.leaf()) { return node; } return traverse(node.left); }; return traverse(this.tree); } //clear visited nodes clearVisited() { this.bfs(function(node) { if (node) { node.visited = false; } }); } //Get the leaves get centerOfMass() { let sum = [0,0]; let totalMass = 0; this.bfs(function(node) { if (node) { if (node.leaf()) { totalMass += node.ball.area sum[0] += node.ball.x*node.ball.area; sum[1] += node.ball.y*node.ball.area; } } }); return Vec(sum[0]/totalMass, sum[1]/totalMass); } // draw all balls draw(ctx, all, cm, center, fn, sn, fl, sl, fv, sv) { let _fn = fn || "#0000000f"; let _sn = sn || "#000000ff"; let _fl = fl || "#0000ff0f"; let _sl = sl || "#0000ffff"; let _fv = fv || "#ff000015"; let _sv = sv || "#ff000050"; this.bfs(function(node) { if (node) { if (node.leaf()) { ctx.fillStyle = _fl; ctx.strokeStyle = _sl; } else { if (node.visited) { ctx.fillStyle = _fv; ctx.strokeStyle = _sv; } else { ctx.fillStyle = _fn; ctx.strokeStyle = _sn; } } if (node.leaf() || all) { node.ball.draw(ctx,center); } } }); let v = this.centerOfMass; if (cm) { ctx.fillStyle = "#ff00ff"; ctx.strokeStyle = "#ffff00"; ctx.beginPath(); ctx.arc(v.x, v.y, 2, 0, Math.PI * 2); ctx.stroke(); ctx.fill(); } } // draw all ball on level drawLevel(ctx,level) { let n = 0 this.bfs(function(node) { if (!node) { n++ } else { if (n == level) { node.ball.draw(ctx); } } }); } // Returns a leaf node which would result in the smallest union with the given ball. // Uses branch and bound to speed the search smallestUnionLeaf(ball) { this.smallestUnionSteps = 0; let best = null; let bestUnionArea = 1e10; let traverse = (node) => { this.smallestUnionSteps++; let expansion = ball.expand(node.ball).area; if (expansion > bestUnionArea) return; if (node.leaf()) { let union = node.ball.union(ball); let area = union.area; if (area < bestUnionArea) { best = node; bestUnionArea = area; } return; } let eleft = ball.expand(node.left.ball); let eright = ball.expand(node.right.ball); if (eleft.area < eright.area) { if (eleft.area < bestUnionArea) traverse(node.left); if (eright.area < bestUnionArea) traverse(node.right); } else { if (eright.area < bestUnionArea) traverse(node.right); if (eleft.area < bestUnionArea) traverse(node.left); } } if (this.tree) traverse (this.tree); return best; } findLeaf (ball) { this.findSteps = 0; let traverse = (node) => { this.findSteps++; if (node.leaf()) { if (node.ball.equals(ball)) return node; return null; } let result = null; if (node.ball.containsPoint(ball.center)) { let dleft = node.left.ball.center.dist(ball.center); let dright = node.right.ball.center.dist(ball.center); if (dleft < dright) { result = traverse(node.left); if (result) return result; result = traverse(node.right); } else { result = traverse(node.right); if (result) return result; result = traverse(node.left); } if (result) return result; } return null; } if (this.tree) return traverse (this.tree); return null; } // Returns the ball in a leaf node whose center is closest to point p. // Uses branch and bound to speed up the search. closest(p) { let best = null; let bestDist = 1e10; this.closestSteps = 0; this.visited = []; let traverse = (node) => { this.closestSteps++; this.visited.push(node); if (node.leaf()) { let d = node.ball.dist(p); if (d < bestDist) [best, bestDist] = [node, d]; return; } let dleft = node.left.ball.dist(p); let dright = node.right.ball.dist(p); if (dleft < dright) { if (dleft < bestDist) traverse(node.left); if (dright < bestDist) traverse(node.right); } else { if (dright < bestDist) traverse(node.right); if (dleft < bestDist) traverse(node.left); } } if (this.tree) traverse(this.tree); return [best, bestDist]; } // Returns a leaf ball containing p, or null, if none exists intersecting(p) { this.intersectingSteps = 0; this.visited = []; let traverse = node => { this.intersectingSteps++; this.visited.push(node); if (node.leaf()) { if (node.ball.containsPoint(p)) return node; return null; } if (!node.ball.containsPoint(p)) return null; let dleft = node.left.ball.dist(p); let dright = node.right.ball.dist(p); if (dleft < dright) { let result = traverse(node.left); if (result) return result; return traverse(node.right); } let result = traverse(node.right); if (result) return result; return traverse(node.left); }; return traverse(this.tree); } // Returns a leaf ball that intersects a segmentline (p,q) and the distance, or null, if none exists intersectLine(p,q,epsilon) { this.intersectingLine = 0; let nodes = null; let intersect = (node) => { let ball = node.ball; let cl = ball.closestLine(p,q); if (cl[1] <= epsilon) { //it is intersecting this.intersectingLine++; if (node.leaf()) { nodes = [cl[0],cl[1],node]; return true; } else { let result = false; result = intersect(node.left); result = result || intersect(node.right); return result; } } else { return false; } } nodes = null; let res = intersect(this.tree); return res ? nodes : null; } translate (p) { let traverse = (node) => { node.ball.translate(p); if (node.left) traverse(node.left); if (node.right) traverse(node.right); } if (this.tree) traverse(this.tree); } scale (f) { this.bfs(function(node) { if (node) { node.ball.scale(f); } }); } mirror(x,y) { let c = this.center; this.bfs(function(node) { if (node) { node.ball.mirror(c,x,y); } }); } intersected (other,epsilon) { this.intersectedSteps = 0; let nodes = null; this.clearVisited(); other.clearVisited(); let intersect = (nodeA, nodeB) => { let ballA = nodeA.ball; let ballB = nodeB.ball; let d = ballA.distance(ballB); if (d <= epsilon) { //it is intersecting this.intersectedSteps++; nodeA.visited = true; nodeB.visited = true; let nA = []; let nB = []; if (nodeA.leaf() && nodeB.leaf()) { let v = ballB.center.sub(ballA.center); nodes = [d,nodeA,nodeB,v]; return true; } else { if (nodeA.leaf()) { nA.push(nodeA); } else { nA.push(nodeA.left); nA.push(nodeA.right); } if (nodeB.leaf()) { nB.push(nodeB); } else { nB.push(nodeB.left); nB.push(nodeB.right); } let result = false; let r = []; for (let i=0; i { return Math.max(node1.ball.center.dist(node2.ball.center)-node1.ball.r-node2.ball.r,0); } let _bound = (node1, node2) => { let [ball1, ball2] = [node1.ball, node2.ball]; let b1 = ball1.closestPoint(ball2.center); let b2 = ball2.closestPoint(ball1.center); let p1 = ball1.perpendicularPoint(b1); let p2 = ball2.perpendicularPoint(b2); if (node1.leaf() && node2.leaf()) { return distance(node1,node2); } return p1.dist(p2); } let PQNode = (n1, n2) => { let dist = n1 ? distance(n1,n2): Number.POSITIVE_INFINITY; let bound = n1 ? _bound(n1,n2) : Number.POSITIVE_INFINITY; let key = n1 ? dist*100000 + bound : Number.POSITIVE_INFINITY; if (n1) n1.visited = true; if (n2) n2.visited = true; return { n1, n2, dist, bound, key}; }; let pq = new Heap(pqnode => pqnode.key); let best = PQNode(null,null); let start = PQNode(this.tree, other.tree); pq.push(start); let tf; if (this.tree.leaf() && other.tree.leaf()) { this.closestSteps = 1; return [distance(this.tree,other.tree),this.tree, other.tree]; } while (pq.size() > 0) { this.pairsSteps++; tf = pq.pop(); if (tf.dist >= best.bound && tf.bound >= best.bound) { //this is the bound in branch and bound break; } else { if (tf.dist < best.bound && tf.bound < best.bound) { best = tf; } let [j,k] = [[],[]]; if (tf.n1.leaf()) { j.push(tf.n1); } else { j.push(tf.n1.left); j.push(tf.n1.right); } if (tf.n2.leaf()) { k.push(tf.n2); } else { k.push(tf.n2.left); k.push(tf.n2.right); } for (let jj=0; jj { if (node.leaf()) { let cl = node.ball.closestLine(p,q); return [cl[0],cl[1],node]; } let dleft = node.left.ball.closestLine(p,q); let dright = node.right.ball.closestLine(p,q); if (dleft[1] < dright[1]) { let result = traverse(node.left); if (result) return result; return traverse(node.right); } let result = traverse(node.right); if (result) return result; return traverse(node.left); }; return traverse(this.tree); } closestSegsNew (p,q) { this.closestSegSteps = 0; let PQNode = (node) => { let dist; if (node) { dist = node.ball.closestLine(p,q)[1]; } else { dist = Number.POSITIVE_INFINITY; } return { node, dist}; }; let pq = new Heap(pqnode => pqnode.dist); let best = PQNode(null,null); let start = PQNode(this.tree); pq.push(start); let tf; while (pq.size() > 0) { this.closestSegSteps++; tf = pq.pop(); if (tf.dist >= best.dist && tf.node.leaf()) { //this is the bound in branch and bound break; } else { if (tf.dist < best.dist && tf.node.leaf()) { best = tf; } if (!tf.node.leaf()) { pq.push(PQNode(tf.node.left)); pq.push(PQNode(tf.node.right)); } } } return best; } } 57: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); } } 58:Ta5e,/** * 2D Vector class, based on https://observablehq.com/@esperanc/2d-geometry-utils#Vector **/ Vector = { // Determinant of a 3x3 matrix let det = (t00, t01, t02, t10, t11, t12, t20, t21, t22) => t00 * (t11 * t22 - t12 * t21) + t01 * (t12 * t20 - t10 * t22) + t02 * (t10 * t21 - t11 * t20); class Vector { constructor(x = 0, y = 0) { [this.x, this.y] = [x, y]; } array() { return [this.x, this.y]; } clone() { // A copy of this vector return new Vector(this.x, this.y); } mag() { // Magnitude (length) return Math.sqrt(this.dot(this)); } set(other) { // Set from another vector [this.x, this.y] = [other.x, other.y]; } add(v) { // Vector sum return new Vector(this.x + v.x, this.y + v.y); } sub(v) { // Vector subtraction return new Vector(this.x - v.x, this.y - v.y); } dist(q) { // Distance to point return this.sub(q).mag(); } dot(q) { // Dot product return this.x * q.x + this.y * q.y; } angle(v) { // Returns the angle between this vector and v return Math.acos( Math.min(Math.max(this.dot(v) / this.mag() / v.mag(), -1), 1) ); } signedAngle(v) { // Returns the _signed_ angle between this vector and v // so that a rotation of this by angle makes it colinear with v let a = this.angle(v); if (new Vector(0, 0).orient(this, v) > 0) return -a; return a; } scale(alpha) { // Multiplication by scalar return new Vector(this.x * alpha, this.y * alpha); } rotate(angle) { // Returns this vector rotated by angle radians let [c, s] = [Math.cos(angle), Math.sin(angle)]; return new Vector(c * this.x - s * this.y, s * this.x + c * this.y); } mix(q, alpha) { // this vector * (1-alpha) + q * alpha return new Vector( this.x * (1 - alpha) + q.x * alpha, this.y * (1 - alpha) + q.y * alpha ); } normalize() { // this vector normalized return this.scale(1 / this.mag()); } distSegment(p, q) { // Distance to line segment var s = p.dist(q); if (s < 0.00001) return this.dist(p); var v = q.sub(p).scale(1.0 / s); var u = this.sub(p); var d = u.dot(v); if (d < 0) return this.dist(p); if (d > s) return this.dist(q); return p.mix(q, d / s).dist(this); } orient(p, q) { // Returns the orientation of triangle (this,p,q) return Math.sign(det(1, 1, 1, this.x, p.x, q.x, this.y, p.y, q.y)); } } return Vector; }59:T532,function treeDistance(tree1, tree2, nodeRank = minDistRank) { const nodePair = (node1, node2) => { let { dist, rank } = nodeRank(node1, node2); return { node1, node2, dist, rank }; }; let Q = new Heap((pair) => pair.rank); let minDist = Number.POSITIVE_INFINITY; let minNode1 = null, minNode2 = null; Q.push(nodePair(tree1.tree, tree2.tree)); let pairCount = 0; while (Q.size() > 0) { let { node1, node2, dist } = Q.pop(); pairCount++; if (dist > minDist) break; if (node1.leaf()) { if (node2.leaf()) { if (dist < minDist) { minNode1 = node1; minNode2 = node2; minDist = dist; if (minDist <= 0) break; } } else { Q.push(nodePair(node1, node2.left)); Q.push(nodePair(node1, node2.right)); } } else if (node2.leaf()) { Q.push(nodePair(node1.left, node2)); Q.push(nodePair(node1.right, node2)); } else { Q.push(nodePair(node1.left, node2.left)); Q.push(nodePair(node1.right, node2.left)); Q.push(nodePair(node1.left, node2.right)); Q.push(nodePair(node1.right, node2.right)); } } return { pairCount, qSize : Q.size(), node1: minNode1, node2: minNode2, dist: Math.max(0, minDist), totalOps: pairCount * 2 + Q.size() }; }5a:T478,function treeIntersection(tree1, tree2, nodeRank = minDistRank) { const nodePair = (node1, node2) => { let { dist, rank } = nodeRank(node1, node2); return { node1, node2, dist, rank }; }; let Q = new Heap((pair) => pair.rank); Q.push(nodePair(tree1.tree, tree2.tree)); let minDist = Number.POSITIVE_INFINITY; let pairCount = 0; let result = false; while (Q.size() > 0) { let { node1, node2, dist } = Q.pop(); pairCount++; if (dist > 0) continue; // No intersection if (node1.leaf()) { if (node2.leaf()) { result = true; break; } else { Q.push(nodePair(node1, node2.left)); Q.push(nodePair(node1, node2.right)); } } else if (node2.leaf()) { Q.push(nodePair(node1.left, node2)); Q.push(nodePair(node1.right, node2)); } else { Q.push(nodePair(node1.left, node2.left)); Q.push(nodePair(node1.right, node2.left)); Q.push(nodePair(node1.left, node2.right)); Q.push(nodePair(node1.right, node2.right)); } } return { pairCount, qSize: Q.size(), result, totalOps: pairCount * 2 + Q.size() }; }5b:T4e3,/* QuickSort Algorithm It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. By default, it implements the classic value sorting algorithm. By defining f function other behaviors can be implemented. For instance function (x) { return -x } can be used to define a sorting algorithm in descending order. ********************************************************************************************** */ function quickSort (A, f = x => x) { let low = 0; let high = A.length-1; let partition = (A,low,high) => { let pivot = f(A[high]); let i = low - 1; for (let j = low; j < high; j++) { if (f(A[j]) < pivot) { i++; [A[i],A[j]] = [A[j],A[i]]; } } if (pivot < f(A[i+1])) { [A[i+1],A[high]] = [A[high],A[i+1]]; } return i+1; } let qSort = (A, low, high) => { if (low < high) { let p = partition(A, low, high); qSort(A, low, p-1); qSort(A, p+1, high); } return A } return qSort (A,low,high); }5c:Tca5,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, [50, 50]); 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; ctx.fillStyle = '#0000000a'; ctx.scale(1, 1); ctx.translate(50, 50); tree.draw(ctx); ctx.strokeStyle = 'red'; ctx.fillStyle = '#ff000020'; ctx.lineWidth = 3; 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}

`; }5d:[{"id":"17963e8afd8c1c4d14e11227b3a82d9cdeeee39deba45f059a65c56554691d6410edd2b88871ac09a1bae8cc1f42be19e1da801a5ec9293e0669691d0325b57a","href":"https://static.observableusercontent.com/files/17963e8afd8c1c4d14e11227b3a82d9cdeeee39deba45f059a65c56554691d6410edd2b88871ac09a1bae8cc1f42be19e1da801a5ec9293e0669691d0325b57a","name":"btshapes3.png","type":"image/png","lastModified":1630088280551.693,"size":99241},{"id":"65352a86799e497d9ca269831d4b7159ee3a62fde83aec11712969ed81ef2a437d4acec84c69fbf4dc8bc50c0808101c9b3462ef3b74d6909d5d8ef0ee4c3ac3","href":"https://static.observableusercontent.com/files/65352a86799e497d9ca269831d4b7159ee3a62fde83aec11712969ed81ef2a437d4acec84c69fbf4dc8bc50c0808101c9b3462ef3b74d6909d5d8ef0ee4c3ac3","name":"cristo-2.csv","type":"text/csv","lastModified":1630086292960.122,"size":10875},{"id":"6df9555db3ec69468ac0a444c4f38a356c936bcd89fc591786ec9bbe6c7639f3bb650960dba81cb527d9b60033706b9831047b57151b4b3c869ecaa5b72acaf0","href":"https://static.observableusercontent.com/files/6df9555db3ec69468ac0a444c4f38a356c936bcd89fc591786ec9bbe6c7639f3bb650960dba81cb527d9b60033706b9831047b57151b4b3c869ecaa5b72acaf0","name":"fish.csv","type":"text/csv","lastModified":1630086317671.809,"size":17492},{"id":"6ca1e5076ec4cbf4a54960521435325ca13fd251dba59ed5f8bd7db4f14f47f7677ef35f40ef1d03f7f598fd53c0177bbc91abefa53a7bf4b0809fe20f20e5fb","href":"https://static.observableusercontent.com/files/6ca1e5076ec4cbf4a54960521435325ca13fd251dba59ed5f8bd7db4f14f47f7677ef35f40ef1d03f7f598fd53c0177bbc91abefa53a7bf4b0809fe20f20e5fb","name":"rabbit.csv","type":"text/csv","lastModified":1630086371714.847,"size":8845}] 49:{"id":"4df2d747c3e219ec","slug":"optimized-2d-ball-trees","title":"Optimized 2D Ball trees","thumbnail":"7c75a4540ebb760d3d9a657aae3448cd50ec6932f3e0351128195567b550fbae","access_level":"public","create_time":"$D2021-08-26T15:10:53.291Z","update_time":"$D2022-01-07T13:49:22.037Z","view_time":null,"first_public_time":"$D2021-08-26T15:17:19.079Z","has_unpublished_edits":null,"fork":false,"stars":1,"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":390,"publish_version":390,"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":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Optimized 2D Ball trees","cells":[{"id":0,"value":"# Optimized 2D Ball trees\n\nThis application is discussed in the paper [Optimized 2D ball trees](https://ieeexplore.ieee.org/document/9643116), published in 2021 34th SIBGRAPI Conference on Graphics, Patterns and Images (SIBGRAPI), Oct. 2021.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"md `**View abstract:** ${bindCheckbox('_abstract', viewof _abstract)}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":385,"value":"shapes = FileAttachment(\"btshapes3.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"## Interactive Demo","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"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":347,"value":"title(\"Examples:\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":354,"value":"showTree(BTKd, \"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":358,"value":"showTree(BTOnline, \"Online algorithm\",\" \")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":361,"value":"showTree(BTBottomUp, \"Bottom-up algorithm\",\" \")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":364,"value":"showTree(BTQ02, \"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":367,"value":"showTree(BTQ05, \"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":370,"value":"showTree(BTV0, \"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":373,"value":"showTree(BTV1, \"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":213,"value":"## Ball tree construction algorithms","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":222,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":225,"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":228,"value":"//BRUTE FORCE\n//=============================\nbottomUpBF = (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":232,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"$50","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":244,"value":"$52","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":67,"value":"## Classes & Basic Data Structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"$53","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":85,"value":"class Queue {\n constructor(...items) {\n this.items = items;\n }\n\n clear() {\n this.items.length = 0;\n }\n\n clone() {\n return new Queue(...this.items);\n }\n\n contains(item) {\n return this.items.includes(item);\n }\n\n peek() {\n var item = null;\n \n if (this.items.length > 0) {\n item = this.items[0];\n }\n \n return item;\n }\n\n dequeue() {\n var removedItem = this.items.shift();\n return removedItem;\n }\n\n enqueue(item) {\n this.items.push(item);\n return item;\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":88,"value":"class Stack {\n // Array is used to implement stack \n constructor() \n { \n this.items = []; \n } \n \n push(element) \n { \n // push element into the items \n this.items.push(element); \n } \n \n // pop function \n pop() \n { \n // return top most element in the stack \n // and removes it from the stack \n // Underflow if stack is empty \n if (this.items.length == 0) \n return \"Underflow\"; \n return this.items.pop(); \n } \n \n // peek function \n peek() \n { \n // return the top most element from the stack \n // but does'nt delete it. \n return this.items[this.items.length - 1]; \n } \n \n // isEmpty function \n isEmpty() \n { \n // return true if stack is empty \n return this.items.length == 0; \n } \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":91,"value":"$54","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"$55","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"$56","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":218,"value":"$57","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":71,"value":"$58","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"// Convenience function to instantiate vectors. Thanks to Claudio Esperança (@esperanc).\nVec = (x,y)=>new Vector(x,y)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"md `## Ball tree queries:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"md `### Distance functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"function ballDist(a, b) {\n return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2) - a.r - b.r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":122,"value":"function maxBallDist(a, b) {\n return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2) + a.r + b.r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"sonsNodeDist = (node1, node2) => {\n if (node1.leaf()) {\n if (node2.leaf()) return ballDist(node1.ball, node2.ball);\n else\n return Math.min(\n ballDist(node1.ball, node2.left.ball),\n ballDist(node1.ball, node2.right.ball)\n );\n } else {\n if (node2.leaf())\n return Math.min(\n ballDist(node1.left.ball, node2.ball),\n ballDist(node1.right.ball, node2.ball)\n );\n else\n return Math.min(\n ballDist(node1.left.ball, node2.left.ball),\n ballDist(node1.left.ball, node2.right.ball),\n ballDist(node1.right.ball, node2.left.ball),\n ballDist(node1.right.ball, node2.right.ball)\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"sonsMaxNodeDist = (node1, node2) => {\n if (node1.leaf()) {\n if (node2.leaf()) return maxBallDist(node1.ball, node2.ball);\n else\n return Math.min(\n maxBallDist(node1.ball, node2.left.ball),\n maxBallDist(node1.ball, node2.right.ball)\n );\n } else {\n if (node2.leaf())\n return Math.min(\n maxBallDist(node1.left.ball, node2.ball),\n maxBallDist(node1.right.ball, node2.ball)\n );\n else\n return Math.min(\n maxBallDist(node1.left.ball, node2.left.ball),\n maxBallDist(node1.left.ball, node2.right.ball),\n maxBallDist(node1.right.ball, node2.left.ball),\n maxBallDist(node1.right.ball, node2.right.ball)\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":131,"value":"lineDist = (ball,p,q) => {\n let s = p.dist(q);\n if (s < 0.00001) return [ball.closestPoint(p), ball.center.dist(p)];\n let v = q.sub(p).scale(1.0/s);\n let u = ball.center.sub(p);\n let d = u.dot(v);\n if (d < 0) return ball.center.dist(p)-ball.r ;\n if (d > s) return ball.center.dist(q)-ball.r ;\n let pmix = p.mix(q,d/s);\n return pmix.dist(ball.center)-ball.r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"maxLineDist = (ball,p,q) => {\n let s = p.dist(q);\n if (s < 0.00001) return [ball.closestPoint(p), ball.center.dist(p)];\n let v = q.sub(p).scale(1.0/s);\n let u = ball.center.sub(p);\n let d = u.dot(v);\n if (d < 0) return ball.center.dist(p)+ball.r ;\n if (d > s) return ball.center.dist(q)+ball.r ;\n let pmix = p.mix(q,d/s);\n return pmix.dist(ball.center)+ball.r;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":137,"value":"sonsLineDist = (node,p,q) => {\n if (node.leaf()) {\n return lineDist(node.ball,p,q);\n } else {\n return Math.min(\n lineDist(node.left.ball, p,q),\n lineDist(node.right.ball, p,q)\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":143,"value":"sonsMaxLineDist = (node,p,q) => {\n if (node.leaf()) {\n return maxLineDist(node.ball,p,q);\n } else {\n return Math.min(\n maxLineDist(node.left.ball, p,q),\n maxLineDist(node.right.ball, p,q)\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":147,"value":"md `### Priority Queue ranking functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"md `#### 1) rank according to minimum distance`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":153,"value":"minDistRank = (node1, node2) => {\n let d = ballDist(node1.ball, node2.ball);\n return { dist: Math.max(0, d), rank: d };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"minLineDistRank = (node, p,q) => {\n let d = lineDist(node.ball, p,q);\n return { dist: Math.max(0, d), rank: d };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"md `#### 2) rank according to minimum distance, breaking ties with the maximum distance`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":161,"value":"minMaxDistRank = (node1, node2) => {\n let d = ballDist(node1.ball, node2.ball);\n let maxD = maxBallDist(node1.ball, node2.ball);\n return { dist: Math.max(0, d), rank: Math.max(0, d) * 10000 + maxD };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"minMaxLineDistRank = (node, p,q) => {\n let d = lineDist(node.ball, p,q);\n let maxD = maxLineDist(node.ball, p,q);\n return { dist: Math.max(0, d), rank: Math.max(0, d) * 10000 + maxD };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":167,"value":"md `#### 3) rank according with minimum distance among sons`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":170,"value":"sonsMinDistRank = (node1, node2) => {\n let d = sonsNodeDist(node1, node2);\n return { dist: Math.max(0, d), rank: d };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":173,"value":"sonsMinLineDistRank = (node, p,q) => {\n let d = sonsLineDist(node, p,q);\n return { dist: Math.max(0, d), rank: d };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"md `#### 4) rank according with minimum distance among sons, breaking ties with the maximum distance among sons!`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":179,"value":"sonsMinMaxDistRank = (node1, node2) => {\n let d = sonsNodeDist(node1, node2);\n let maxD = sonsMaxNodeDist(node1, node2);\n return { dist: Math.max(0, d), rank: Math.max(0, d) * 10000 + maxD };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"sonsMinMaxLineDistRank = (node, p,q) => {\n let d = sonsLineDist(node, p,q);\n let maxD = sonsMaxLineDist(node, p,q);\n return { dist: Math.max(0, d), rank: Math.max(0, d) * 10000 + maxD };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":185,"value":"md `### Query algorithms`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":188,"value":"$59","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":191,"value":"$5a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"//\n// Omohundro nearest neighbor\n//\nfunction nearestNeighbor(\n node,\n ball,\n best = { neighbor: null, steps: 1, dist: Number.POSITIVE_INFINITY }\n) {\n let dist = Math.max(0, ballDist(node.ball, ball));\n best.steps++;\n if (node.leaf()) {\n if (dist < best.dist) {\n best.dist = dist;\n best.neighbor = node;\n }\n } else {\n let dleft = ballDist(node.left.ball, ball);\n let dright = ballDist(node.right.ball, ball);\n if (dleft < dright) {\n if (dleft < best.dist) nearestNeighbor(node.left, ball, best);\n if (dright < best.dist) nearestNeighbor(node.right, ball, best);\n } else {\n if (dright < best.dist) nearestNeighbor(node.right, ball, best);\n if (dleft < best.dist) nearestNeighbor(node.left, ball, best);\n }\n }\n return best;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":197,"value":"function smallestUnionLeaf(tree, ball) {\n let nodeRank = (node,b) => {\n let exp = b.expand(node.ball).area;\n return { expansion: exp, rank: exp };\n }\n const nodePQ = (node,_b) => {\n let { expansion, rank } = nodeRank(node,_b);\n return { node, expansion, rank };\n };\n let Q = new Heap((pq) => pq.rank);\n let bestUnionArea = Number.POSITIVE_INFINITY;\n let bestNode = null;\n Q.push(nodePQ(tree.tree,ball));\n let nodeCount = 0;\n while (Q.size() > 0) {\n let { node, expansion } = Q.pop();\n nodeCount++;\n if (expansion > bestUnionArea) break;\n if (node.leaf()) {\n let union = node.ball.union(ball);\n let area = union.area;\n if (area < bestUnionArea) {\n bestNode = node;\n bestUnionArea = area;\n }\n } else {\n Q.push(nodePQ(node.left,ball));\n Q.push(nodePQ(node.right,ball));\n }\n }\n return {\n nodeCount,\n qSize : Q.size(),\n node: bestNode,\n totalOps: nodeCount * 2 + Q.size()\n };\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":200,"value":"function lineIntersection(tree, p, q, nodeRank = minLineDistRank) {\n const nodePQ = (node, p,q) => {\n let { dist, rank } = nodeRank(node, p,q);\n return { node, dist, rank };\n };\n let Q = new Heap((pq) => pq.rank);\n Q.push(nodePQ(tree.tree, p,q));\n let minDist = Number.POSITIVE_INFINITY;\n let nodeCount = 0;\n let result = false;\n while (Q.size() > 0) {\n let { node, dist } = Q.pop();\n nodeCount++;\n if (dist > 0) continue; // No intersection\n if (node.leaf()) {\n result = true;\n break;\n } else {\n Q.push(nodePQ(node.left,p,q));\n Q.push(nodePQ(node.right,p,q));\n }\n }\n return {\n nodeCount,\n qSize: Q.size(),\n result,\n totalOps: nodeCount * 2 + Q.size()\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"function lineDistance(tree, p,q, nodeRank = minLineDistRank) {\n const nodePQ = (node, p,q) => {\n let { dist, rank } = nodeRank(node, p,q);\n return { node, dist, rank };\n };\n let Q = new Heap((pq) => pq.rank);\n let minDist = Number.POSITIVE_INFINITY;\n let minNode = null\n Q.push(nodePQ(tree.tree, p,q));\n let nodeCount = 0;\n while (Q.size() > 0) {\n let { node, dist } = Q.pop();\n nodeCount++;\n if (dist > minDist) break;\n if (node.leaf()) {\n if (dist < minDist) {\n minNode = node;\n minDist = dist;\n if (minDist <= 0) break;\n }\n } else {\n Q.push(nodePQ(node.left,p,q));\n Q.push(nodePQ(node.right,p,q));\n }\n }\n return {\n nodeCount,\n qSize : Q.size(),\n node: minNode,\n dist: Math.max(0, minDist),\n totalOps: nodeCount * 2 + Q.size()\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":206,"value":"md `#### Translate Tree`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":209,"value":"function translateTree(tree, dx = 0, dy = 0) {\n let { ball, left, right } = tree.tree;\n if (left) left = translateTree(left, dx, dy);\n if (right) right = translateTree(right, dx, dy);\n ball = new Ball(ball.x + dx, ball.y + dy, ball.r);\n let node = new BTNode(ball, left, right);\n return new BallTree(node);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":103,"value":"## General Functions","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"$5b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":246,"value":"shuffleArray = (arr) => {\n let result = [];\n let s = shuffle(arr.length);\n for (let i=0; i {\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":335,"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":329,"value":"$5c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":344,"value":"title = (txt) => {\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":253,"value":"## Built Ball trees","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":326,"value":"BTKd = {\n return kdConstruction(balls,false);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":323,"value":"BTOnline = {\n return Online(balls)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":319,"value":"BTBottomUp = {\n return bottomUp(balls,false);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":313,"value":"BTQ02 = { \n return Q(balls,0.2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":316,"value":"BTQ05 = { \n return Q(balls,0.5);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"BTV0 = { \n return V0(balls,3);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"BTV1 = { \n return V1(balls);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"## Variables","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"viewof _abstract = new View(false)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":277,"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":280,"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":292,"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":298,"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":331,"value":"mutable queryPoint = ({ x: 0, y: 0 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":301,"value":"syms = [\"Custom\",\"Rabbit\",\"Fish\",\"Rio\",]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":240,"value":"_width = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"rabbit = shapeData(d3.csvParse(await FileAttachment(\"rabbit.csv\").text(), d3.autoType))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":260,"value":"rio = shapeData(d3.csvParse(await FileAttachment(\"cristo-2.csv\").text(), d3.autoType))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":268,"value":"fish = shapeData(d3.csvParse(await FileAttachment(\"fish.csv\").text(), d3.autoType))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":275,"value":"ballsRandom = Array.from({length: _numberOfBalls}, () => ([\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":296,"value":"balls = {\n let result = [];\n let dataBalls;\n let dataB = [null,rabbit,fish,rio];\n \n let ind = syms.indexOf(_simulation);\n dataBalls = dataB[ind] \n \n if (ind < 1) {\n result = coordBalls();\n } else {\n for (let i=0; i\n p { max-width: 1024; }\n .tit {\n max-width: 100%;\n margin-top: 0px;\n margin-bottom:0px;\n padding-left: 10px;\n font-weight:bold;\n font-size:20px;\n background-color:#f9f9f9;\n border-style: inset;\n border-color:steelblue;\n }\n .normal {\n max-width: 100%;\n margin-top: 0px;\n margin-bottom:0px;\n padding-left: 10px;\n font-weight:normal;\n font-size:20px;\n }\n .note {\n max-width: 100%;\n margin-top: 0px;\n margin-bottom:0px;\n padding-left: 10px;\n font-weight:normal;\n font-size:12px;\n font-style:italic;\n }\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"## Dependencies","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"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":61,"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":64,"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":16,"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"}],"files":"$W5d","stdlib":"1"}} 44:null