25:["$","title",null,{"children":"Point k-d trees with queries (incomplete) | Data Structures Course | 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:T10bd,/** * 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; } let p = this.root; if (p.cutDim === i) { if (p.left.root) { return p.left.findMin(i); } else { return p.point; } } else { let leftMin = p.left.findMin(i) let rightMin = p.right.findMin(i) let q = (!leftMin || p.point[i] <= leftMin[i])? p.point:leftMin; let t = (!rightMin || q[i] <= rightMin[i])? q:rightMin; return t; } } // 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)) { if (right.root != null) { this.root.point = right.findMin(cutDim); right.delete(this.root.point); } else if (left.root != null) { this.root.point = left.findMin(cutDim); left.delete(this.root.point); right.root = left.root; left.root = null; } else { this.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; if (r.containsRectangle(cell)) return this.root.size; let count = 0; if (r.containsPoint(this.root.point)) count++; 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 let { point, cutDim, left, right } = this.root; if (r.isDisjointFrom(cell)){ return points; } else { if (r.containsPoint(point)){ points.push(point); } points = left.rangeSelect(r, cell.leftPart(cutDim, point), points); points = right.rangeSelect(r, cell.rightPart(cutDim, 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); // WRONG! Do something here! let leftCell = cell.leftPart(cutDim, point); let rightCell = cell.rightPart(cutDim, point); if (q[cutDim] < point[cutDim]){ bestDist = left.nearestNeighbor(q, leftCell, bestDist, visited); if (rightCell.distanceToPoint(q) < bestDist) { bestDist = right.nearestNeighbor(q, rightCell, bestDist, visited); } }else { bestDist = right.nearestNeighbor(q, rightCell, bestDist, visited); if (leftCell.distanceToPoint(q) < bestDist) { bestDist = left.nearestNeighbor(q, leftCell, bestDist, visited); } } } return bestDist; } }4b:T77a,/** * 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); } }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