44:["$","title",null,{"children":"Basic Data Structures | Luis Retondaro | Observable"}] 4c:T13a4,class Heap { /* By default, implements a binary min heap. By defining scoreFunction other behaviors can be implemented. - For instance function (x) { return -x } can be used to define a max heap. BY defining changeScore we can change the score, as in a priority queue. - For instance: function (x,k) { x.y = k; return; } ***************************************************************************** */ constructor(scoreFunction,changeScore) { this.tree = []; this.scoreFunction = scoreFunction || function (x) { return x }; this.changeScore = changeScore || function (x,k) { x = k; return; }; } size() { return this.tree.length; } parent(i) { return Math.floor((i+1)/2)-1; } left(i) { return (2*(i+1))-1; } right(i) { return (2*(i+1)); } swap (i,j) { let e_i = this.tree[i]; let e_j = this.tree[j]; this.tree[i] = e_j; this.tree[j] = e_i; } // Moves element at position n towards the top as necessary siftUp(i) { // Fetch the element that has to be moved. let element = this.tree[i]; let score = this.scoreFunction(element); while (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)]; } }4e:T859,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; this.type = 0; } 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 bc = [] for (let c of cc) { bc.push(new Ball(c.x,c.y,c.r)); } let bv = Ball.enclose(bc); //d3.packEnclose(cc); this.ball = new Ball (bv.x,bv.y,bv.r); this.left.computeEnclosingCircles(); this.right.computeEnclosingCircles(); } } }4f:T6d8b,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; //this.pivot = this.centerOfMass; } 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 newNode = new BTNode( 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); } //create a tree by grafting a set of other trees //the input balls are the root nodes of each grafted tree static engraft(gTrees,alg) { let balls=[] for (let b of gTrees) { balls.push(b.tree.ball); } let tree = alg(balls,0.5); let [left,right] = [0,1]; let getTree = (b) => { for (let g of gTrees) { if (g.tree.ball.equals(b)) { return g; } } return null; } let traverse = (node,side) => { if (node.leaf()) { let gt = getTree(node.ball); if (gt) { gt.tree.parent = node.parent; gt.tree.type = 1; //graft if (node.parent) { if (side == left) { node.parent.left = gt.tree; } else { node.parent.right = gt.tree; } } } return } traverse(node.left,left); traverse(node.right,right); }; if (tree.tree.leaf()) return gTrees[0]; traverse(tree.tree); tree.tree.computeEnclosingCircles(); return tree; } prune() { let result = []; this.bfs(function(node) { if (node) { if (node.type == 1) { //it's a graft ! node.type = 0; node.parent = null; result.push(node); } } }); return result; } //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 centerA = Vec(nodeA.ball.x, nodeA.ball.y); //let centerB = Vec(nodeB.ball.x, nodeB.ball.y); //let realD = centerA.dist(centerB)-nodeA.ball.r-nodeB.ball.r; //let d = Math.max(realD,0); 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 = centerB.sub(centerA); let v = ballB.center.sub(ballA.center); //v = v.normalize(); //let va = v.add(centerA) //let vb = v.add(centerB) // 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]; if (node1.leaf() && node2.leaf()) { return distance(node1,node2); } return ball1.maxDistance(ball2);*/ 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; } } 50: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() }; }51: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() }; }52:T4c6,function treeWithin(tree1, tree2, threshold, 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 > threshold) continue; // dist(tree1, tree2) > threshold if (node1.leaf()) { if (node2.leaf()) { if (dist <= threshold) { 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() }; }53:[] 48:{"id":"255ff8b670e49554","slug":"basic-data-structures","title":"Basic Data Structures","thumbnail":"c97b367f42e23281d599c2b064da0ccca3b148ed75abafe5b072fa82acdfc02c","access_level":"public","create_time":"$D2021-01-27T14:27:17.664Z","update_time":"$D2022-01-04T23:01:19.292Z","view_time":null,"first_public_time":"$D2021-01-27T19:42:09.668Z","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":2345,"publish_version":2345,"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":0,"collection":{"id":"aac69fe6b3972389","slug":"utility-library","title":"Utility & Library","owner":{"id":"71e5ea5268419c5a","login":"lretondaro","name":"Luis Retondaro"}},"type":"notebook","body":{"titling":"auto","title":"Basic Data Structures","cells":[{"id":0,"value":"md`# Basic Data Structures`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"md `## Heap`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":249,"value":"md `## Queue`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"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":256,"value":"md `## Stack`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"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":241,"value":"md `## Ball tree`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":261,"value":"$4d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"$4e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"$4f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1808,"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":1838,"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":1843,"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":1845,"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":1846,"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":1848,"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":1987,"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":1991,"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":1993,"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":1995,"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":1850,"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":1834,"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":1833,"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":1997,"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":1829,"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":1828,"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":1999,"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":1824,"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":1823,"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":2001,"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":1816,"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":1815,"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":2003,"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":1854,"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":1857,"value":"$50","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1859,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2334,"value":"$52","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1862,"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":1967,"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":2006,"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":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2008,"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":1881,"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":1880,"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":19,"value":"html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":264,"value":"md `## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"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":455,"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"}],"files":"$W53","stdlib":"1"}} 24:null