Computer Graphics & Visualization @ufrj.br
Published
Edited
Jan 1, 2022
Importers
9 stars
showTree(testQuadratic, "Quadratic algorithm")
//
// Ball base class
//
class Ball {
constructor(x, y, r) {
[this.x, this.y, this.r] = [x, y, r];
}
// Creates a copy of other ball
static from(other) {
return new Ball(other.x, other.y, other.r);
}
// Returns true iff this and other are "equal", i.e., same center and radius
equals(other) {
const dx = this.x - other.x;
const dy = this.y - other.y;
const dr = this.r - other.r;
return dx * dx == 0 && dy * dy == 0 && dr * dr == 0;
}
// Returns true iff this other ⊆ this.
encloses(other) {
const dr = this.r - other.r + 1e-6; //
const dx = this.x - other.x;
const dy = this.y - other.y;
return dr >= 0 && dr * dr > dx * dx + dy * dy;
}
// returns true iff this ball contains point p
containsPoint(p) {
const dx = this.x - p.x;
const dy = this.y - p.y;
return dx * dx + dy * dy <= this.r * this.r;
}
// Returns true iff this ball intersects other
intersects(other) {
const dx = this.x - other.x;
const dy = this.y - other.y;
return Math.sqrt(dx * dx + dy * dy) < this.r + other.r;
}
// 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 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 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 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);
}
// 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;
/**
** This deviates from the implementation in d3.packEnclose(), which
** throws an error for
**
** d3.packEnclose ([
** { x: 14.5, y: 48.5, r: 7.585 },
** { x: 9.5, y: 79.5, r: 2.585 },
** { x: 15.5, y: 73.5, r: 8.585 }
** ])
**
** (see https://github.com/d3/d3-hierarchy/issues/188)
**/
const r = -(Math.abs(A) > 1e-10
? (B + Math.sqrt(B * B - 4 * A * C)) / (2 * A)
: C / B);
return new Ball(x1 + xa + xb * r, y1 + ya + yb * r, r);
}
// 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 "Something Weird happened";
}
// Returns a ball enclosing all balls in L
static enclose(L) {
// let { x, y, r } = d3.packEnclose(L);
// return new Ball(x, y, r);
const encloseBasis = (B) => {
switch (B.length) {
case 1:
return 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 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, fill = true, stroke = true) {
ctx.beginPath();
ctx.arc(this.x, this.y, this.r, 0, Math.PI * 2);
if (stroke) ctx.stroke();
if (fill) ctx.fill();
}
}
//
// Balltree node base class
//
class BTNode {
// Entry is a Ball, while left and right are BT's
constructor (entry,left=null,right=null) {
Object.assign(this,{entry,left,right});
}
// Returns true iff this is a leaf node
leaf () {
return !(this.left || this.right)
}
}
//
// Balltree base class
//
class BT {
// Builds a balltree contaning a BTnode (or an empty balltree)
constructor(node = null) {
this.node = node;
}
// Height of the tree
height() {
if (!this.node) return -1;
if (this.node.leaf()) return 0;
return Math.max(this.node.left.height() + 1, this.node.right.height() + 1);
}
// Visits the tree in inorder, yielding (generating) all nodes
*inorder() {
if (this.node) {
if (this.node.left) yield* this.node.left.inorder();
yield this.node;
if (this.node.right) yield* this.node.right.inorder();
}
}
// Visits the tree generating all nodes at level l
*level(l) {
if (l == 0) yield this.node;
else {
if (this.node.left) yield* this.node.left.level(l - 1);
if (this.node.right) yield* this.node.right.level(l - 1);
}
}
// Similar to level, but includes leaf nodes if at level shallower than l
*approximation(l) {
if (l == 0 || this.node.leaf()) yield this.node;
else {
if (this.node.left) yield* this.node.left.approximation(l - 1);
if (this.node.right) yield* this.node.right.approximation(l - 1);
}
}
// Generates all leaf nodes of this tree
*leafBalls() {
if (this.node.leaf()) yield this.node.entry;
else {
yield* this.node.left.leafBalls();
yield* this.node.right.leafBalls();
}
}
// Generates all leaf notes within distance d of point p
*within(p, d) {
let self = this;
self.withinSteps = 0;
function* traverse(node) {
let dnode = node.entry.dist(p);
self.withinSteps++;
if (dnode <= d) {
if (node.leaf()) yield node;
else {
let dleft = node.left.node.entry.dist(p);
let dright = node.right.node.entry.dist(p);
if (dleft < dright) {
yield* traverse(node.left.node);
yield* traverse(node.right.node);
} else {
yield* traverse(node.left.node);
yield* traverse(node.right.node);
}
}
}
}
if (this.node) yield* traverse(this.node);
}
// Reduces the bounding balls from internal nodes to those
// enclosing only the leaves
computeEnclosingCircles() {
if (!this.node.leaf()) {
this.node.entry = Ball.enclose([...this.leafBalls()]);
//Ball.from(d3.packEnclose([...this.leafBalls()]));
this.node.left.computeEnclosingCircles();
this.node.right.computeEnclosingCircles();
}
return this;
}
// Total area of the tree
area() {
if (this.node.leaf()) return this.node.entry.area;
return (
this.node.entry.area + this.node.left.area() + this.node.right.area()
);
}
// Draws all balls using context ctx
draw(ctx) {
for (let node of this.inorder()) {
node.entry.draw(ctx);
}
}
// Finds a leaf matching position and radius with the given ball
// returns a pair {node, ancestors} where node is
// the leaf node with the found ball, and ancestor is an array of
// tree objects [T0, T1, ... Tn], such that Ti+1 is the parent of Ti,
// Tn is the tree containing node
find(ball) {
this.findSteps = 0;
this.visited = [];
let traverse = (ancestors) => {
let n = ancestors.length;
let node = ancestors[n - 1].node;
this.visited.push(node);
this.findSteps++;
if (node.leaf()) {
if (node.entry.equals(ball)) return { node, ancestors };
return null;
}
let result = null;
if (node.entry.containsPoint(ball)) {
let dleft = node.left.node.entry.dist(ball);
let dright = node.right.node.entry.dist(ball);
if (dleft < dright) {
ancestors.push(node.left);
result = traverse(ancestors);
if (result) return result;
ancestors.pop();
ancestors.push(node.right);
result = traverse(ancestors);
} else {
ancestors.push(node.right);
result = traverse(ancestors);
if (result) return result;
ancestors.pop();
ancestors.push(node.left);
result = traverse(ancestors);
}
if (result) return result;
ancestors.pop();
}
return null;
};
if (this.node) return traverse([this]);
}
// 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.entry.containsPoint(p)) return node.entry;
return null;
}
if (!node.entry.containsPoint(p)) return null;
let dleft = node.left.node.entry.dist(p);
let dright = node.right.node.entry.dist(p);
if (dleft < dright) {
let result = traverse(node.left.node);
if (result) return result;
return traverse(node.right.node);
}
let result = traverse(node.right.node);
if (result) return result;
return traverse(node.left.node);
};
return traverse(this.node);
}
// Returns a list of balls enclosed in the given ball
findInCircle(ball) {
this.findInCircleSteps = 0;
this.visited = [];
let result = [];
let traverse = (node) => {
this.findInCircleSteps++;
this.visited.push(node);
if (node.leaf()) {
if (ball.encloses(node.entry)) result.push(node.entry);
} else {
if (node.left.node.entry.intersects(ball)) traverse(node.left.node);
if (node.right.node.entry.intersects(ball)) traverse(node.right.node);
}
};
if (this.node.entry.intersects(ball)) traverse(this.node);
return result;
}
// 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 = Number.POSITIVE_INFINITY;
this.closestSteps = 0;
this.visited = [];
let traverse = (node) => {
if (bestDist == 0) return;
this.closestSteps++;
this.visited.push(node);
if (node.leaf()) {
let d = node.entry.dist(p);
if (d < bestDist) [best, bestDist] = [node.entry, d];
return;
}
let dleft = node.left.node.entry.dist(p);
let dright = node.right.node.entry.dist(p);
if (dleft < dright) {
if (dleft < bestDist) traverse(node.left.node);
if (dright < bestDist) traverse(node.right.node);
} else {
if (dright < bestDist) traverse(node.right.node);
if (dleft < bestDist) traverse(node.left.node);
}
};
if (this.node) traverse(this.node);
return best;
}
// 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) {
let best = null;
let bestUnionArea = Number.POSITIVE_INFINITY;
this.smallestUnionSteps = 0;
this.visited = [];
let traverse = (node) => {
this.smallestUnionSteps++;
this.visited.push(node);
let expansion = ball.expand(node.entry).area;
if (expansion > bestUnionArea) return;
if (node.leaf()) {
let union = node.entry.union(ball);
let area = union.area;
if (area < bestUnionArea) {
best = node;
bestUnionArea = area;
}
return;
}
let eleft = ball.expand(node.left.node.entry);
let eright = ball.expand(node.right.node.entry);
if (eleft.area < eright.area) {
if (eleft.area < bestUnionArea) traverse(node.left.node);
if (eright.area < bestUnionArea) traverse(node.right.node);
} else {
if (eright.area < bestUnionArea) traverse(node.right.node);
if (eleft.area < bestUnionArea) traverse(node.left.node);
}
};
if (this.node) traverse(this.node);
return best;
}
}
// Locates every leaf of the tree starting from the root and returns
// the average number of steps required
function averageFindCost(tree) {
let totalSteps = 0;
let n = 0;
for (let ball of tree.leafBalls()) {
n++;
let result = tree.find(ball);
console.assert(result);
totalSteps += tree.findSteps;
if (!result) throw "Something Wrong with find";
}
return totalSteps / n;
}
function* balls(n, minRadius = 0.01, maxRadius = 0.01) {
while (n--)
yield new Ball(
Math.random(),
Math.random(),
Math.random() * (maxRadius - minRadius) + minRadius
);
}
class OnlineBT extends BT {
constructor(...args) {
super(...args);
}
// Finds a leaf having the given ball as entry (must be the same object!).
// Returns a pair {node, ancestors} where node is
// the leaf node with the found ball, and ancestor is an array of
// tree objects [T0, T1, ... Tn], such that Ti+1 is the parent of Ti,
// Tn is the tree containing node
find(ball) {
this.findSteps = 0;
this.visited = [];
let traverse = ancestors => {
let n = ancestors.length;
let node = ancestors[n - 1].node;
this.visited.push(node);
this.findSteps++;
if (node.leaf()) {
if (node.entry == ball) return { node, ancestors };
return null;
}
let result = null;
if (node.entry.containsPoint(ball)) {
let dleft = node.left.node.entry.dist(ball);
let dright = node.right.node.entry.dist(ball);
if (dleft < dright) {
ancestors.push(node.left);
result = traverse(ancestors);
if (result) return result;
ancestors.pop();
ancestors.push(node.right);
result = traverse(ancestors);
} else {
ancestors.push(node.right);
result = traverse(ancestors);
if (result) return result;
ancestors.pop();
ancestors.push(node.left);
result = traverse(ancestors);
}
if (result) return result;
ancestors.pop();
}
return null;
};
if (this.node) return traverse([this]);
}
remove(ball) {
let findResult = this.find(ball);
if (!findResult) {
throw "Trying to remove inexistant ball";
}
let { node, ancestors } = findResult;
if (ancestors.length > 1) {
ancestors.pop(); // Pop tree containing ball
let parent = ancestors[ancestors.length - 1];
if (node == parent.node.left.node) {
parent.node = parent.node.right.node;
} else {
parent.node = parent.node.left.node;
}
ancestors.pop(); // Parent tree now has a leaf node
// Update ancestors of parent
while (ancestors.length > 0) {
let tree = ancestors.pop();
tree.node.entry = tree.node.left.node.entry.union(
tree.node.right.node.entry
);
}
} else {
// Root node was removed
this.node = null;
}
}
insert(ball) {
if (!this.node) {
this.node = new BTNode(ball);
return;
}
let PQNode = (tree, ancestorExpansion, parentpq) => {
let union = tree.node.entry.union(ball);
let cost = union.area + ancestorExpansion;
let aexp = ancestorExpansion;
return { tree, union, cost, aexp, parentpq };
};
let pq = new BinaryHeap(pqnode => pqnode.aexp);
let best = PQNode(this, 0, null);
pq.push(best);
while (pq.size() > 0) {
let pqnode = pq.pop();
if (pqnode.aexp >= best.cost) break;
let e = pqnode.aexp + pqnode.cost - pqnode.tree.node.entry.area;
if (pqnode.tree.node.left) {
let left = PQNode(pqnode.tree.node.left, e, pqnode);
if (left.cost < best.cost) best = left;
pq.push(left, e);
}
if (pqnode.tree.node.right) {
let right = PQNode(pqnode.tree.node.right, e, pqnode);
if (right.cost < best.cost) best = right;
pq.push(right, e);
}
}
// Make ball a sibling of best node
best.tree.node = new BTNode(
best.tree.node.entry.union(ball), //best.union,
new OnlineBT(best.tree.node),
new OnlineBT(new BTNode(ball))
);
// Update ancestor bounding balls
let pqnode = best;
while (pqnode.parentpq) {
pqnode = pqnode.parentpq;
let node = pqnode.tree.node;
let union = node.left.node.entry.union(node.right.node.entry);
node.entry = union;
}
}
}
testOnlineBT = {
let t0 = performance.now();
let tree = new OnlineBT();
for (let ball of testData) {
tree.insert(ball);
}
if (config.encloseLeaves) tree.computeEnclosingCircles();
let t1 = performance.now();
mutable times["online"] = t1 - t0;
return tree;
}
function bottomUpBF(balls) {
let trees = balls.map(b => new BT(new BTNode(b)));
while (trees.length > 1) {
let best = null,
bestArea = Number.POSITIVE_INFINITY;
for (let i = 0; i < trees.length; i++) {
for (let j = i + 1; j < trees.length; j++) {
let union = trees[i].node.entry.union(trees[j].node.entry);
if (union.area < bestArea) {
best = [i, j, union];
bestArea = union.area;
}
}
}
let [i, j, union] = best;
trees[i] = new BT(new BTNode(union, trees[i], trees[j]));
trees.splice(j, 1);
//return { trees, best };
}
return trees[0];
}
testBottomUpBF = {
if (showBruteForce) {
let tree = bottomUpBF(testData);
if (config.encloseLeaves) tree.computeEnclosingCircles();
return tree;
}
return null;
}
function bottomUp(balls) {
let trees = balls.map(b => new BT(new BTNode(b)));
let PQNode = (i, j, unionArea) => ({ i, j, unionArea });
let pq = new BinaryHeap(pqnode => pqnode.unionArea);
let auxtree = new OnlineBT();
// 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].node.entry.union(trees[j].node.entry).area;
if (unionArea < bestArea) {
bestArea = unionArea;
best = PQNode(i, j, bestArea);
}
}
pq.push(best);
trees[i].node.entry.index = i;
auxtree.insert(trees[i].node.entry);
}
// insert pairs from the priority queue pq
let iteration = 0;
while (pq.size() > 1) {
iteration++;
let pqnode = pq.pop();
let pqtop = pq.content[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].node.entry;
auxtree.remove(ball);
let mate = auxtree.smallestUnionLeaf(ball).entry;
let union = Ball.from(ball.union(mate)); // Make a copy
if (union.area <= pqtop.unionArea) {
let parent = new BT(
new BTNode(union, trees[ball.index], trees[mate.index])
);
trees[ball.index] = null;
trees[mate.index] = null;
auxtree.remove(mate);
union.index = trees.length;
trees.push(parent);
let bestParentMate = auxtree.smallestUnionLeaf(union);
if (!bestParentMate) break;
auxtree.insert(union);
pq.push(
PQNode(
union.index,
bestParentMate.entry.index,
union.union(bestParentMate.entry).area
)
);
} else {
auxtree.insert(ball);
pq.push(PQNode(i, mate.index, union.area));
}
}
let pqnode = pq.pop();
return trees[trees.length - 1];
}
testBottomUp = {
let t0 = performance.now();
let tree = bottomUp(testData);
if (config.encloseLeaves) tree.computeEnclosingCircles();
let t1 = performance.now();
mutable times["bottom up"] = t1 - t0;
return tree;
}
function kdconstruct(balls) {
let trees = balls.map(b => new BT(new BTNode(b)));
const bbox = trees => {
let min = { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY };
let max = { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY };
for (let tree of trees) {
let ball = tree.node.entry;
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 build = trees => {
if (trees.length == 1) return trees[0];
let { min, max } = bbox(trees);
if (max.x - min.x > max.y - min.y) {
medianSort(trees, tree => tree.node.entry.x);
} else {
medianSort(trees, tree => tree.node.entry.y);
}
let k = trees.length >> 1;
let left = build(trees.slice(0, k));
let right = build(trees.slice(k));
return new BT(
new BTNode(left.node.entry.union(right.node.entry), left, right)
);
};
let result = build(trees);
return result;
}
testKDConstruct = {
let t0 = performance.now();
let result = kdconstruct(testData);
if (config.encloseLeaves) result.computeEnclosingCircles();
let t1 = performance.now();
mutable times["KD"] = t1 - t0;
return result;
}
// Moves the median of A to its proper place in the array, that is,
// to position A.length/2. Function f can be used to establish the
// sort order, i.e., considers f(A[i]) rather than A[i].
// Returns the sorted array
function medianSort(A, f = x => x) {
// Partitions A [i ... i+n-1] using A[i] as pivot;
// Returns the number of elements < pivot;
const partition = (i, n) => {
let x = f(A[i]);
let m = 0;
for (let j = i + 1; j < i + n; j++) {
if (f(A[j]) < x) {
m++;
[A[j], A[i + m]] = [A[i + m], A[j]];
}
}
[A[i], A[i + m]] = [A[i + m], A[i]];
return m;
};
// Recursively find the median using the quicksort rationale
const select = (k, i, n) => {
let j = ~~(Math.random() * n) + i;
[A[i], A[j]] = [A[j], A[i]];
let m = partition(i, n);
if (m == k) return m;
if (m < k) return m + 1 + select(k - m - 1, i + m + 1, n - m - 1);
return select(k, i, m);
};
select(A.length >> 1, 0, A.length);
return A;
}
function quadratic(balls) {
let trees = balls.map((b) => new BT(new BTNode(b)));
const treeSort = (trees) => {
// random order
// return d3.shuffle(trees);
// sort in order of size
trees.sort((a, b) => a.node.entry.r - b.node.entry.r);
return trees;
// sort in order of position w.r.t. largest dispersion axis
let min = { x: Number.POSITIVE_INFINITY, y: Number.POSITIVE_INFINITY };
let max = { x: Number.NEGATIVE_INFINITY, y: Number.NEGATIVE_INFINITY };
for (let t of trees) {
let { x, y } = t.node.entry;
if (x < min.x) min.x = x;
if (y < min.y) min.y = y;
if (x > max.x) max.x = x;
if (y > max.y) max.y = y;
}
if (max.x - min.x > max.y - min.y)
trees.sort(
(a, b) =>
a.node.entry.x - a.node.entry.r - b.node.entry.x + b.node.entry.r
);
else
trees.sort(
(a, b) =>
a.node.entry.y - a.node.entry.r - b.node.entry.y + b.node.entry.r
);
};
while (trees.length > 1) {
treeSort(trees);
let before = trees.length;
let newTrees = [],
remainder = [];
for (let i = 0; i < trees.length; i++) {
if (!trees[i]) continue;
let best = null;
let bestArea = Number.POSITIVE_INFINITY;
for (let j = i + 1; j < trees.length; j++) {
if (!trees[j]) continue;
let union = trees[i].node.entry.union(trees[j].node.entry);
if (union.area < bestArea) {
best = [j, union];
bestArea = union.area;
}
}
if (best) {
let [j, union] = best;
newTrees.push(new BT(new BTNode(union, trees[i], trees[j])));
trees[j] = trees[i] = null;
} else {
remainder.push(trees[i]);
}
}
// Use only about half of the new trees
let n = Math.min(newTrees.length, 1 + Math.trunc(newTrees.length * 0.5));
newTrees.sort((a, b) => a.node.entry.r - b.node.entry.r); // sort in order of size
trees = newTrees.slice(0, n);
for (let i = n; i < newTrees.length; i++) {
let t = newTrees[i];
trees.push(t.node.left, t.node.right);
}
for (let t of remainder) trees.push(t);
if (trees.length >= before) throw "too slow";
}
return trees[0];
}
testQuadratic = {
let t0 = performance.now();
let tree = quadratic(testData);
if (config.encloseLeaves) tree.computeEnclosingCircles();
let t1 = performance.now();
mutable times["quadratic"] = t1 - t0;
return tree;
}
mutable times = ({})
testData = [...balls(config.nballs, ...config.radiusRange)]
mutable queryPoint = ({ x: 0, y: 0 })
function showTree(tree, name = "") {
let title = md`### ${name}`;
let level = html`<input type=number min=0 max=${tree.height()} step=1 value=${tree.height()} style="width:3em;">`;
let label = html`<span> Highlight level: </span>`;
let area = html`<span> Total area: </span> ${tree.area()}`;
let cost = html`<span> Average find cost: </span> ${averageFindCost(tree)}`;
let closestSteps = html`<span></span>`;
let closestInfo = html`<span> Steps to locate closest leaf to query point: </span>`;
let intersectingSteps = html`<span></span>`;
let intersectingInfo = html`<span> Steps to locate leaf containing query point: </span>`;
let smallestUnionSteps = html`<span></span>`;
let smallestUnionInfo = html`<span> Steps to locate leaf that yields smallest union with point: </span>`;
closestInfo.append(closestSteps);
intersectingInfo.append(intersectingSteps);
smallestUnionInfo.append(smallestUnionSteps);
let width = 600;
let canvas = DOM.canvas(width, width);
let ctx = canvas.getContext("2d");
let mat2d = glmatrix.mat2d;
let transform = mat2d.fromScaling([], [width, width]);
mat2d.translate(transform, transform, [0.25, 0.25]);
mat2d.scale(transform, transform, [0.5, 0.5]);
let inverse = mat2d.invert([], transform);
let queryBall = new Ball(queryPoint.x, queryPoint.y, 0.0);
const queryRadius = 0.3;
let refresh = () => {
ctx.save();
ctx.clearRect(0, 0, width, width);
ctx.lineWidth = 1 / width;
ctx.fillStyle = "#0000000a";
ctx.setTransform(...transform);
tree.draw(ctx);
let l = level.value;
ctx.strokeStyle = "red";
ctx.fillStyle = "#ff000020";
ctx.lineWidth = 3 / width;
for (let node of tree.level(l)) node.entry.draw(ctx);
let closest = tree.closest(queryPoint);
closestSteps.innerHTML = tree.closestSteps;
let intersecting = tree.intersecting(queryPoint);
intersectingSteps.innerHTML =
(intersecting ? "(successful) " : "(unsuccessful) ") +
tree.intersectingSteps;
let smallestUnionNode = tree.smallestUnionLeaf(queryBall);
let smallestUnion = smallestUnionNode.entry.union(queryBall);
smallestUnionSteps.innerHTML = tree.smallestUnionSteps;
ctx.fillStyle = "#0000ff70";
ctx.strokeStyle = "blue";
closest.draw(ctx);
ctx.fillStyle = "#ffffff70";
if (intersecting) intersecting.draw(ctx);
ctx.setLineDash([3 / width, 3 / width]);
ctx.strokeStyle = "green";
smallestUnionNode.entry.draw(ctx);
smallestUnion.draw(ctx, false, true);
ctx.setLineDash([]);
ctx.strokeStyle = "blue";
ctx.beginPath();
ctx.moveTo(queryPoint.x - 0.02, queryPoint.y);
ctx.lineTo(queryPoint.x + 0.02, queryPoint.y);
ctx.moveTo(queryPoint.x, queryPoint.y - 0.02);
ctx.lineTo(queryPoint.x, queryPoint.y + 0.02);
ctx.stroke();
ctx.setLineDash([5 / width, 5 / width]);
ctx.fillStyle = "#00000000";
new Ball(queryBall.x, queryBall.y, queryRadius).draw(ctx);
ctx.strokeStyle = "yellow";
ctx.setLineDash([]);
for (let node of tree.within(queryPoint, queryRadius)) {
node.entry.draw(ctx);
}
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`<div>
${title}${label}${level}<br>
${area}<br>
${cost}<br>
${closestInfo}<br>
${intersectingInfo}<br>
${smallestUnionInfo}<br>
${canvas}</div>`;
}
glmatrix = import('https://unpkg.com/gl-matrix@3.3.0/esm/index.js?module')
vec2 = glmatrix.vec2
import { BinaryHeap } from "@esperanc/2d-geometry-utils"
import { number, checkbox } from "@jashkenas/inputs"
import { rangeSlider } from "@mootari/range-slider"
import { combo } from "@esperanc/aggregated-inputs"
d3 = require("d3@6")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
