Computer Graphics & Visualization @ufrj.br
Point k-d trees with queries
// A sample k-d tree
kdtree = {
reset;
let t = new KDTree();
for (let i = 0; i < 16; i++) t.insert(randomPoint());
return t;
}
k = 2
/**
* Represents a node for a k-dimensional k-d tree
**/
class KDNode {
constructor(point, cutDim, left, right, size = 1) {
Object.assign(this, { point, cutDim, left, right, size });
}
}
//
// Returns dimension to cut given a node's level
//
function levelToCutDim (level) {
return level % k
}
/**
* Represents a k-dimensional k-d tree
**/
class KDTree {
// Builds a k-d tree having KDNode root at its root
constructor(root = null) {
this.root = root;
}
// A textual representation of the tree
toString() {
if (this.root) {
return `${this.root.point}`;
}
return "null";
}
// Inserts point q into the k-d-tree
insert(q, level = 0) {
if (this.root == null) {
this.root = new KDNode(
q,
levelToCutDim(level),
new KDTree(),
new KDTree(),
1
);
} else {
let { point, cutDim, left, right } = this.root;
if (q[cutDim] >= point[cutDim]) right.insert(q, level + 1);
else left.insert(q, level + 1);
this.root.size += 1;
}
}
// Finds the point with minimum i'th coordinate
findMin(i) {
if (this.root) {
let { point, cutDim, left, right } = this.root;
if (cutDim == i) {
if (left.root) return left.findMin(i);
return point;
} else {
if (left.root) {
let q = left.findMin(i);
if (q[i] < point[i]) point = q;
}
if (right.root) {
let q = right.findMin(i);
if (q[i] < point[i]) point = q;
}
return point;
}
}
}
// Deletes point q from the k-d-tree.
delete(q) {
if (!this.root) throw `not in tree: ${q}`;
this.root.size--;
let { point, cutDim, left, right } = this.root;
if (pointEquals(point, q)) {
// found point
if (!left.root && !right.root) {
this.root = null;
} else {
if (right.root) {
let r = right.findMin(cutDim);
right.delete(r);
//this.root.size++;
this.root.point = r;
} else {
let r = left.findMin(cutDim);
left.delete(r);
//this.root.size++;
this.root.point = r;
this.root.right.root = left.root;
this.root.left.root = null;
}
}
} else if (q[cutDim] < point[cutDim]) {
left.delete(q);
} else {
right.delete(q);
}
}
// Returns the number of points contained in rectangle r
// Side effect: all visited cells (rectangles) are stored in array 'visited'. Used for
// debugging and demonstration drawings
rangeCount(r, cell = world, visited = []) {
if (!this.root) return 0; // empty subtree
visited.push(cell);
if (r.isDisjointFrom(cell)) return 0; // no overlap with range
if (r.containsRectangle(cell))
// range contains our entire cell?
return this.root.size; // include all points in the count
// range partially overlaps cell
let count = 0;
if (r.containsPoint(this.root.point))
// consider this point
count++;
// apply recursively to children
count += this.root.left.rangeCount(
r,
cell.leftPart(this.root.cutDim, this.root.point),
visited
);
count += this.root.right.rangeCount(
r,
cell.rightPart(this.root.cutDim, this.root.point),
visited
);
return count;
}
// Returns an array with all points contained in rectangle r
rangeSelect(r, cell = world, points = []) {
if (!this.root) return points; // empty subtree
if (r.isDisjointFrom(cell)) return points; // no overlap with range
// range overlaps cell
if (r.containsPoint(this.root.point))
// consider this point
points.push(this.root.point);
// apply recursively to children
this.root.left.rangeSelect(
r,
cell.leftPart(this.root.cutDim, this.root.point),
points
);
this.root.right.rangeSelect(
r,
cell.rightPart(this.root.cutDim, this.root.point),
points
);
return points;
}
// Returns the distance to the point closest to q
// Side effect: all visited cells (rectangles) are stored in array 'visited'. Used for
// debugging and demonstration drawings
nearestNeighbor(q, cell = world, bestDist = Infinity, visited = []) {
if (this.root) {
let { point, cutDim, left, right } = this.root;
bestDist = Math.min(bestDist, pointDistance(point, q));
visited.push(cell);
let toVisit = [];
if (left.root) {
let rect = cell.leftPart(cutDim, point);
let dist = rect.distanceToPoint(q);
toVisit.push({ rect, dist, tree: left });
}
if (right.root) {
let rect = cell.rightPart(cutDim, point);
let dist = rect.distanceToPoint(q);
toVisit.push({ rect, dist, tree: right });
}
if (toVisit.length == 2 && toVisit[0].dist > toVisit[1].dist)
toVisit.reverse();
for (let { rect, dist, tree } of toVisit) {
if (dist < bestDist)
bestDist = Math.min(
bestDist,
tree.nearestNeighbor(q, rect, bestDist, visited)
);
}
}
return bestDist;
}
}
//
// Returns true if points a and b have the same coordinates
//
function pointEquals(a, b) {
for (let i = 0; i < k; i++) if (a[i] != b[i]) return false;
return true;
}
//
// Returns the Euclidian distance between points a and b
//
function pointDistance(a, b) {
let sum = 0;
for (let i = 0; i < k; i++) sum += (a[i] - b[i]) ** 2;
return Math.sqrt(sum);
}
/**
* Represents a multidimensional rectangle
**/
class Rectangle {
// Constructor from two points
constructor(a, b) {
if (Math.min(a.length, a.length) < k)
throw `Wrong number of dimensions: ${a} ${b}`;
let low = [],
high = [];
for (let i = 0; i < k; i++) {
low[i] = Math.min(a[i], b[i]);
high[i] = Math.max(a[i], b[i]);
}
Object.assign(this, { low, high });
}
// Returns true iff rectangle contains point q
containsPoint(q) {
for (let i = 0; i < k; i++) {
if (q[i] < this.low[i] || q[i] > this.high[i]) return false;
}
return true;
}
// Returns true iff rectangle contains rect c
containsRectangle(c) {
for (let i = 0; i < k; i++) {
if (c.low[i] < this.low[i] || c.high[i] > this.high[i]) return false;
}
return true;
}
// Returns true iff rectangle is disjoint from rect c
isDisjointFrom(c) {
for (let i = 0; i < k; i++) {
if (c.low[i] > this.high[i] || c.high[i] < this.low[i]) return true;
}
return false;
}
// Returns the Euclidian distance to point q
distanceToPoint(q) {
let sum = 0;
for (let i = 0; i < k; i++) {
sum +=
(q[i] < this.low[i]
? this.low[i] - q[i]
: q[i] > this.high[i]
? q[i] - this.high[i]
: 0) ** 2;
}
return Math.sqrt(sum);
}
// Returns the left part of a rectangle after it has been cut by
// a hyperplane perpendicular to coordinate cd passing through s
leftPart(cd, s) {
let low = [...this.low];
let high = [...this.high];
high[cd] = s[cd];
return new Rectangle(low, high);
}
// Returns the right part of a rectangle after it has been cut by
// a hyperplane perpendicular to coordinate cd passing through s
rightPart(cd, s) {
let low = [...this.low];
let high = [...this.high];
low[cd] = s[cd];
return new Rectangle(low, high);
}
}
//
// Known range for each coordinate of a point in a k-d tree.
// (replace values with -Infinity, Infinity, if not known)
//
range = ({ min: 0, max: 100 })
//
// Returns a random point in the allowed range for the k-d tree
//
function randomPoint() {
let p = [];
for (let i = 0; i < k; i++)
p[i] = Math.round(range.min + Math.random() * (range.max - range.min));
return p;
}
//
// A rectangle with the bounds for the representable world
//
world = {
let low = [],
high = [];
for (let i = 0; i < k; i++) {
low[i] = range.min;
high[i] = range.max;
}
return new Rectangle(low, high);
}
d3.scaleLinear().domain([range.min, range.max]).range([10, 380])
/**
* Function for drawing 2d k-d trees.
* Assumes points have coordinates within [range.min, range.max]
**/
function drawKDTree(t, options = {}) {
let { size = 400, margin = 10 } = options;
let scale = d3
.scaleLinear()
.domain([range.min, range.max])
.range([margin, size - margin]);
let [viewmin, viewsz] = [
range.min - margin,
range.max - range.min + margin * 2
];
let svg = htl.svg`<svg width=${size} height=${size} >`;
svg.append(
htl.svg`<rect x=${scale(range.min)} y=${scale(range.min)} width=${
scale(range.max) - scale(range.min)
} height=${scale(range.max) - scale(range.min)} stroke=black fill=none >`
);
function draw(t, min, max) {
if (t.root) {
let { point, cutDim, left, right } = t.root;
if (cutDim == 0) {
svg.append(
htl.svg`<line x1=${scale(point[0])} x2=${scale(point[0])} y1=${scale(
min[1]
)} y2=${scale(max[1])} stroke=black >`
);
draw(left, min, [point[0], max[1]]);
draw(right, [point[0], min[1]], max);
} else {
svg.append(
htl.svg`<line x1=${scale(min[0])} x2=${scale(max[0])} y1=${scale(
point[1]
)} y2=${scale(point[1])} stroke=black >`
);
draw(left, min, [max[0], point[1]]);
draw(right, [min[0], point[1]], max);
}
svg.append(
htl.svg`<circle cx=${scale(point[0])} cy=${scale(
point[1]
)} r=4 fill=blue >`
);
svg.append(
htl.svg`<text x=${scale(point[0])} y=${
scale(point[1]) - 8
} text-anchor=middle stroke=white stroke-width=0.5 fill=black
style="font:bold 12px sans-serif; user-select:none;">${
point[0]
},${point[1]}</text>`
);
}
}
draw(t, [range.min, range.min], [range.max, range.max]);
svg.scale = scale;
return svg;
}
graphViz = function (kdtree) {
let result = `digraph{`;
let count = 0;
let traverse = (tree) => {
if (tree.root) {
if (tree.root.left.root) {
result += `< ${tree.toString()} > -> < ${tree.root.left.toString()} >;\n`;
traverse(tree.root.left);
} else {
result += "null" + ++count + '[shape = none, label=""];\n';
result += `< ${tree.toString()} > -> ${
"null" + count
} [arrowhead="tee"];\n`;
}
if (tree.root.right.root) {
result += `< ${tree.toString()} > -> < ${tree.root.right.toString()} >;\n`;
traverse(tree.root.right);
} else {
result += "null" + ++count + '[shape = none, label=""];\n';
result += `< ${tree.toString()} > -> ${
"null" + count
} [arrowhead="tee"];\n`;
}
}
};
traverse(kdtree);
return result + "}";
}
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.
