Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingHash table with separate chainingOmohundro balltree construction algorithmsCounting and radix sortMergeSort and QuickSortSkipListSplay TreesTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Point k-d trees
k = 2
function levelToCutDim (level) {
return level % k
}
class KDNode {
constructor(point, cutDim, left, right) {
Object.assign(this, { point, cutDim, left, right});
}
}
class KDTree {
constructor(root = null) {
this.root = root;
}
toString() {
if (this.root) {
return `${this.root.point}`;
}
return "null";
}
insert(q, level = 0) {
if (this.root == null) {
this.root = new KDNode(
q,
levelToCutDim(level),
new KDTree(),
new KDTree()
);
} else {
let { point, cutDim, left, right } = this.root;
if (q[cutDim] >= point[cutDim]) right.insert(q, level + 1);
else left.insert(q, level + 1);
}
}
}
range = ({ min: 0, max: 100 })
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;
}
kdtree = {
let t = new KDTree();
for (let i = 0; i < 16; i++) t.insert(randomPoint());
return t;
}
{
let div = htl.html`<div >`;
let w = width / 2;
let drawing = drawKDTree(kdtree, { size: w });
let graph = dot`${graphViz(kdtree)}`;
graph.style.width = `${w}px`;
div.append(drawing);
div.append(graph);
return div;
}
/**
* 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 f = (x) =>
margin + ((x - range.min) / (range.max - range.min)) * (size - margin * 2);
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=${f(range.min)} y=${f(range.min)} width=${
f(range.max) - f(range.min)
} height=${f(range.max) - f(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=${f(point[0])} x2=${f(point[0])} y1=${f(
min[1]
)} y2=${f(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=${f(min[0])} x2=${f(max[0])} y1=${f(
point[1]
)} y2=${f(point[1])} stroke=black >`
);
draw(left, min, [max[0], point[1]]);
draw(right, [min[0], point[1]], max);
}
svg.append(
htl.svg`<circle cx=${f(point[0])} cy=${f(point[1])} r=4 fill=blue >`
);
svg.append(
htl.svg`<text x=${f(point[0])} y=${
f(point[1]) - 8
} text-anchor=middle stroke=white stroke-width=0.5 fill=black style="font:bold 12px sans-serif;">${
point[0]
},${point[1]}</text>`
);
}
}
draw(t, [range.min, range.min], [range.max, range.max]);
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.
