25:["$","title",null,{"children":"Point k-d trees with queries | Studies Zuilho | Observable"}] 49:T125a,{ let div = htl.html`

`; let w = width / 2; let drawing, graph, queryDrawing; const display = () => { div.querySelectorAll("*").forEach((r) => r.remove()); drawing = drawKDTree(kdtree, { size: w, margin: 20 }); queryDrawing = htl.svg``; drawing.append(queryDrawing); graph = dot`${graphViz(kdtree)}`; graph.style.width = `${w}px`; graph.style.maxHeight = `${w}px`; div.append(drawing); div.append(graph); }; display(); const scale = drawing.scale; const rectSVG = (r, options = {}) => { const { strokeWidth = 2, stroke = "red", fill = "rgba(0,0,0,0.02)" } = options; return htl.svg``; }; const eventPoint = (e) => [scale.invert(e.offsetX), scale.invert(e.offsetY)]; if (operation == "insert") { // point insertion let onmousedown = (e) => { let p = eventPoint(e).map((x) => Math.round(x)); if (world.containsPoint(p)) kdtree.insert(p); display(); drawing.onmousedown = onmousedown; }; drawing.onmousedown = onmousedown; } else if (operation == "delete") { // range delete let query = null; const updateQueryDrawing = () => { queryDrawing.querySelectorAll("*").forEach((r) => r.remove()); if (query) { queryDrawing.append(rectSVG(query.rect, { fill: "none" })); } }; let p; const onmousedown = (e) => { query = null; p = eventPoint(e); updateQueryDrawing(); }; const onmousemove = (e) => { if (e.buttons) { let q = eventPoint(e); query = { rect: new Rectangle(p, q) }; updateQueryDrawing(); } }; const onmouseup = (e) => { if (query) { const points = kdtree.rangeSelect(query.rect); for (let p of points) { kdtree.delete(p); } query = null; updateQueryDrawing(); display(); Object.assign(drawing, { onmousedown, onmousemove, onmouseup }); } }; Object.assign(drawing, { onmousedown, onmousemove, onmouseup }); } else if (operation == "rangeCount") { // Rectangle count query let query = null; const updateQueryDrawing = () => { queryDrawing.querySelectorAll("*").forEach((r) => r.remove()); if (query) { for (let r of query.visited) { queryDrawing.append( rectSVG(r, { stroke: "rgba(255,0,0,0.5)", strokeWidth: 5 }) ); } queryDrawing.append(rectSVG(query.rect, { fill: "none" })); let [x, y] = [ (query.rect.high[0] + query.rect.low[0]) / 2, (query.rect.high[1] + query.rect.low[1]) / 2 ]; queryDrawing.append( htl.svg` ${ query.result }` ); } }; let p; drawing.onmousedown = (e) => { query = null; p = eventPoint(e); updateQueryDrawing(); }; drawing.onmousemove = (e) => { if (e.buttons) { let q = eventPoint(e); query = { rect: new Rectangle(p, q), visited: [] }; query.result = kdtree.rangeCount(query.rect, world, query.visited); updateQueryDrawing(); } }; drawing.onmouseup = (e) => { updateQueryDrawing(); }; } else if (operation == "nearestNeighbor") { // nearest neighbor query let query = null; const updateQueryDrawing = () => { queryDrawing.querySelectorAll("*").forEach((r) => r.remove()); if (query) { for (let r of query.visited) { queryDrawing.append( rectSVG(r, { stroke: "rgba(255,0,0,0.5)", strokeWidth: 5 }) ); } let [x, y] = query.point.map(scale); let r = scale(query.dist) - scale(0); queryDrawing.append( htl.svg`` ); } }; let p; drawing.onmousedown = drawing.onmousemove = (e) => { if (e.buttons) { let q = eventPoint(e); query = { point: q, visited: [] }; query.dist = kdtree.nearestNeighbor(q, world, Infinity, query.visited); updateQueryDrawing(); } }; drawing.onmouseup = (e) => { query = null; updateQueryDrawing(); }; } return div; }4a:T18e6,/** * 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) return null; // empty tree let minPoint = this.root.point; let minCoord = minPoint[i]; let currentNode = this.root; while (currentNode) { const { point, cutDim, left, right } = currentNode; if (point[i] < minCoord) { minPoint = point; minCoord = point[i]; } if (minCoord > point[cutDim]) { currentNode = right.root; } else { currentNode = left.root; } } return minPoint; } // Deletes point q from the k-d-tree. delete(q) { if (!this.root) throw `not in tree: ${q}`; let parent = null; let currentNode = this.root; while (currentNode) { const { point, left, right } = currentNode; if (pointEquals(point, q)) { // Found the node to delete // Case 1: Node to delete is a leaf if (!left.root && !right.root) { if (!parent) { // Node to delete is the root this.root = null; } else if (parent.left.root === currentNode) { parent.left.root = null; } else { parent.right.root = null; } return; } // Case 2: Node to delete has a right subtree if (!left.root && right.root) { if (!parent) { // Node to delete is the root this.root = right.root; } else if (parent.left.root === currentNode) { parent.left.root = right.root; } else { parent.right.root = right.root; } return; } // Case 3: Node to delete has a left subtree if (left.root && !right.root) { if (!parent) { // Node to delete is the root this.root = left.root; } else if (parent.left.root === currentNode) { parent.left.root = left.root; } else { parent.right.root = left.root; } return; } // Case 4: Node to delete has both left and right subtrees // Find the successor node (minimum node in the right subtree) let successorParent = currentNode; let successor = right.root; while (successor.left.root) { successorParent = successor; successor = successor.left.root; } // Replace the node to delete with the successor node currentNode.point = successor.point; // Delete the successor node (it is guaranteed to have at most one child) if (successorParent.left.root === successor) { successorParent.left.root = successor.right.root; } else { successorParent.right.root = successor.right.root; } return; } parent = currentNode; if (q[currentNode.cutDim] >= point[currentNode.cutDim]) { currentNode = right.root; } else { currentNode = left.root; } } throw `not in tree: ${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 let count = 0; const stack = [{ node: this.root, cell }]; while (stack.length > 0) { const { node, cell } = stack.pop(); visited.push(cell); if (r.containsRectangle(cell)) { count += node.size; } else if (!r.isDisjointFrom(cell)) { const { point, cutDim, left, right } = node; if (r.containsPoint(point)) { count++; } if (left.root) { const leftCell = cell.leftPart(cutDim, point); stack.push({ node: left.root, cell: leftCell }); } if (right.root) { const rightCell = cell.rightPart(cutDim, point); stack.push({ node: right.root, cell: rightCell }); } } } return count; } // Returns an array with all points contained in rectangle r rangeSelect(r, cell = world, points = []) { if (!this.root) return points; // empty subtree this._rangeSelectHelper(this.root, r, cell, points); return points; } _rangeSelectHelper(node, r, cell, points) { if (node == null) { return; } const { point, left, right } = node; if (r.containsPoint(point)) { points.push(point); } if (r.isDisjointFrom(cell)) { return; } const { cutDim } = node; this._rangeSelectHelper(left.root, r, cell.leftPart(cutDim, point), points); this._rangeSelectHelper(right.root, r, cell.rightPart(cutDim, point), 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) { return bestDist; // Empty subtree, return current best distance } let currentNode = this.root; let stack = []; while (currentNode) { const { point, cutDim, left, right } = currentNode; visited.push(cell); const currentDist = pointDistance(point, q); if (currentDist < bestDist) { bestDist = currentDist; } if (q[cutDim] <= point[cutDim]) { if (left.root) { currentNode = left.root; cell = left.getBoundingBox(cell); } else { currentNode = right.root; cell = right.getBoundingBox(cell); } } else { if (right.root) { currentNode = right.root; cell = right.getBoundingBox(cell); } else { currentNode = left.root; cell = left.getBoundingBox(cell); } } } return bestDist; } }4b:T77a,/** * Represents a multidimensional rectangle **/ class Rectangle { // Constructor from two points constructor(a, b) { if (Math.min(a.length, b.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); } }4c:T75d,/** * 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`
\n## Implementation","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"k = 2","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"/**\n * Represents a node for a k-dimensional k-d tree\n **/\nclass KDNode {\n constructor(point, cutDim, left, right, size = 1) {\n Object.assign(this, { point, cutDim, left, right, size });\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"//\n// Returns dimension to cut given a node's level\n//\nfunction levelToCutDim (level) {\n return level % k\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"$4a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":204,"value":"//\n// Returns true if points a and b have the same coordinates\n//\nfunction pointEquals(a, b) {\n for (let i = 0; i < k; i++) if (a[i] != b[i]) return false;\n return true;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":260,"value":"//\n// Returns the Euclidian distance between points a and b\n//\nfunction pointDistance(a, b) {\n let sum = 0;\n for (let i = 0; i < k; i++) sum += (a[i] - b[i]) ** 2;\n return Math.sqrt(sum);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"$4b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":18,"value":"// \n// Known range for each coordinate of a point in a k-d tree. \n// (replace values with -Infinity, Infinity, if not known)\n//\nrange = ({ min: 0, max: 100 })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"//\n// Returns a random point in the allowed range for the k-d tree\n//\nfunction randomPoint() {\n let p = [];\n for (let i = 0; i < k; i++)\n p[i] = Math.round(range.min + Math.random() * (range.max - range.min));\n return p;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"//\n// A rectangle with the bounds for the representable world\n//\nworld = {\n let low = [],\n high = [];\n for (let i = 0; i < k; i++) {\n low[i] = range.min;\n high[i] = range.max;\n }\n return new Rectangle(low, high);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":95,"value":"
\n## Drawing code","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":147,"value":"d3.scaleLinear().domain([range.min, range.max]).range([10, 380])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"$4c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"graphViz = function (kdtree) {\n let result = `digraph{`;\n let count = 0;\n let traverse = (tree) => {\n if (tree.root) {\n if (tree.root.left.root) {\n result += `< ${tree.toString()} > -> < ${tree.root.left.toString()} >;\\n`;\n traverse(tree.root.left);\n } else {\n result += \"null\" + ++count + '[shape = none, label=\"\"];\\n';\n result += `< ${tree.toString()} > -> ${\n \"null\" + count\n } [arrowhead=\"tee\"];\\n`;\n }\n if (tree.root.right.root) {\n result += `< ${tree.toString()} > -> < ${tree.root.right.toString()} >;\\n`;\n traverse(tree.root.right);\n } else {\n result += \"null\" + ++count + '[shape = none, label=\"\"];\\n';\n result += `< ${tree.toString()} > -> ${\n \"null\" + count\n } [arrowhead=\"tee\"];\\n`;\n }\n }\n };\n traverse(kdtree);\n return result + \"}\";\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4d","stdlib":"1"}} 24:null