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; } }