3e:null 3f:["$","title",null,{"children":"Point k-d trees with queries | Claudio Esperança | Observable"}] 45:T1287,{ 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) { console.log(query.visited.length); 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; }46:T1505,/** * 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; } } } // Finds the point with minimum i'th coordinate findMax(i) { if (this.root) { let { point, cutDim, left, right } = this.root; if (cutDim == i) { if (right.root) return right.findMax(i); return point; } else { if (left.root) { let q = left.findMax(i); if (q[i] > point[i]) point = q; } if (right.root) { let q = right.findMax(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.findMax(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; } }47: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); } }48: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":"$46","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":"$47","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":"$48","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":"$W49","stdlib":"1"}} 44:"$43:body"