31:T4d3,When working with Observable Plot, providing interaction in response to pointer position is possible with the [Pointer transform](https://observablehq.com/plot/interactions/pointer). This works well for many use-cases, but has one limitation: the values under the pointer are not explicitly exposed in the API. Sometimes we may want access to these data values, for example when _brushing_ between views, or applying some data-based query via pointer interaction. We can address this by providing a [custom mark class](https://observablehq.com/@jwolondon/hello-custom-marks-with-plot) that transforms the location under the mouse pointer into 'data space' coordinates and exposes those data values. It works because marks use a custom `render()` function that is parameterised by (among others) the dimensions of the Plot area and the scaling functions to move between screen space and data space. Here is a custom mark that will behave exactly as the [Dot mark](https://observablehq.com/plot/marks/dot) but with the addition of any custom SVG to be added as an additional layer in response to pointer movements. The custom drawing is done in its own SVG layer so doesn't require redrawing the normal Dot marks when the mouse moves.32:T5bd,class DotOverlay extends Plot.Dot { constructor(data, options = {}) { super(data, options); this.onPointerMove = options.onPointerMove; } render(indices, scales, channels, dims, cxt) { // Render the standard Dot marks const g = super.render(indices, scales, channels, dims, cxt); // Add a new SVG overlay that is customisable with the onPointerMove callback function const overlayGroup = htl.svg``; g.appendChild(overlayGroup); const move = (event) => { overlayGroup.replaceChildren(); const [sx, sy] = d3.pointer(event, g); if ( sx < dims.marginLeft || sx > dims.width - dims.marginRight || sy < dims.marginTop || sy > dims.height - dims.marginBottom ) { return; // Pointer isn't in the data space } const [dataX, dataY] = [scales.x?.invert?.(sx), scales.y?.invert?.(sy)]; if (dataX != null && dataY != null && this.onPointerMove) { // Do the drawing provided by the onPointerMove callback const overlay = this.onPointerMove({ dataX, dataY, scales, channels, dims, cxt }); if (overlay instanceof SVGElement) { overlayGroup.appendChild(overlay); } } }; cxt.ownerSVGElement.addEventListener("pointermove", move); return g; // Return the combined Dot marks and overlay for display } }33:T8e1,class BoundedMaxHeap { #heap = []; #capacity; constructor(capacity = Infinity) { this.#capacity = capacity; this.#heap = []; // Array of [priority, value] tuples } size() { return this.#heap.length; } peek() { if (this.isEmpty()) { throw new Error("Attempting to peek at value in an empty BoundedMaxHeap"); } return this.#heap[0][1]; } peekPriority() { if (this.isEmpty()) { throw new Error( "Attempting to peek at priority in an empty BoundedMaxHeap" ); } return this.#heap[0][0]; } dequeue() { if (this.isEmpty()) { throw new Error("Cannot dequeue from an empty BoundedMaxHeap"); } const max = this.#heap[0]; const last = this.#heap.pop(); if (!this.isEmpty()) { this.#heap[0] = last; this.#siftDown(0); } return max[1]; } insert(x, priority = 0) { if (this.#heap.length < this.#capacity) { this.#heap.push([priority, x]); this.#siftUp(this.#heap.length - 1); } else if (priority < this.#heap[0][0]) { this.#heap[0] = [priority, x]; this.#siftDown(0); } return this; } toArray() { return this.#heap.map(([_, x]) => x); } toSortedArray() { return [...this.#heap].sort((a, b) => a[0] - b[0]).map(([_, x]) => x); } isEmpty() { return this.#heap.length === 0; } clear() { this.#heap = []; return this; } // ---------------------- Private helper methods #siftUp(i) { while (i > 0) { const parent = (i - 1) >> 1; if (this.#heap[i][0] <= this.#heap[parent][0]) { break; } [this.#heap[i], this.#heap[parent]] = [this.#heap[parent], this.#heap[i]]; i = parent; } } #siftDown(i) { const n = this.#heap.length; while (true) { const [left, right] = [2 * i + 1, 2 * i + 2]; let largest = i; if (left < n && this.#heap[left][0] > this.#heap[largest][0]) { largest = left; } if (right < n && this.#heap[right][0] > this.#heap[largest][0]) { largest = right; } if (largest === i) { break; } [this.#heap[i], this.#heap[largest]] = [ this.#heap[largest], this.#heap[i] ]; i = largest; } } }34:T1beb,class KdTree2D { constructor() { this.root = null; } // Add a point object that contains x and y fields. insert(obj) { const insertRec = (node, depth = 0) => { if (!node) { return new KdTree2DNode(obj, depth % 2); } const cmp = node.axis === 0 ? obj.x - node.pt.x : obj.y - node.pt.y; if (cmp < 0) { node.setLeft(insertRec(node.left, depth + 1)); } else if (cmp > 0 || obj.x !== node.pt.x || obj.y !== node.pt.y) { node.setRight(insertRec(node.right, depth + 1)); } return node; }; this.root = insertRec(this.root); return this; } find(x, y) { let node = this.root; let depth = 0; while (node) { if (node.pt.x === x && node.pt.y === y) { return node; } node = (depth % 2 === 0 ? x < node.pt.x : y < node.pt.y) ? node.left : node.right; depth++; } return null; } clear() { this.root = null; return this; } *dfsPreOrder(node = this.root) { if (!node) { return; } yield node.pt; yield* this.dfsPreOrder(node.left); yield* this.dfsPreOrder(node.right); } *bfs() { if (!this.root) { return; } const queue = [this.root]; let head = 0; while (head < queue.length) { const node = queue[head++]; yield node.pt; if (node.left) { queue.push(node.left); } if (node.right) { queue.push(node.right); } } } *spatialMedian() { const points = [...this.dfsPreOrder()]; yield* this.#recursiveMedian(points); } *rangeQuery(xMin, yMin, xMax, yMax, node = this.root) { if (!node) { return; } if (KdTree2D.#inBox(node.pt, xMin, yMin, xMax, yMax)) { yield node.pt; } const { x, y } = node.pt; if (node.axis === 0) { if (xMin <= x) { yield* this.rangeQuery(xMin, yMin, xMax, yMax, node.left); } if (xMax >= x) { yield* this.rangeQuery(xMin, yMin, xMax, yMax, node.right); } } else { if (yMin <= y) { yield* this.rangeQuery(xMin, yMin, xMax, yMax, node.left); } if (yMax >= y) { yield* this.rangeQuery(xMin, yMin, xMax, yMax, node.right); } } } *pointsWithinRadius(x, y, r) { const r2 = r * r; function* visit(node) { if (!node) { return; } const d = KdTree2D.#distSq({ x, y }, node.pt); if (d <= r2) { yield node.pt; } const delta = node.axis === 0 ? x - node.pt.x : y - node.pt.y; if (delta < 0) { yield* visit(node.left); if (delta ** 2 <= r2) { yield* visit(node.right); } } else { yield* visit(node.right); if (delta ** 2 <= r2) { yield* visit(node.left); } } } yield* visit(this.root); } nearestNeighbour(x, y) { let best = null; let bestDistSq = Infinity; const search = (node) => { if (!node) { return; } const d = KdTree2D.#distSq({ x, y }, node.pt); if (d < bestDistSq) { best = node; bestDistSq = d; } const delta = node.axis === 0 ? x - node.pt.x : y - node.pt.y; const primary = delta < 0 ? node.left : node.right; const secondary = delta < 0 ? node.right : node.left; search(primary); if (delta ** 2 < bestDistSq) { search(secondary); } }; search(this.root); return best?.pt ?? null; } kNearestNeighbours(x, y, k) { if (k <= 0 || !this.root) { return []; } const target = { x, y }; const heap = new BoundedMaxHeap(k); const search = (node) => { if (!node) { return; } const distSq = KdTree2D.#distSq(target, node.pt); heap.insert(node.pt, distSq); const axis = node.axis; const delta = axis === 0 ? x - node.pt.x : y - node.pt.y; const primary = delta < 0 ? node.left : node.right; const secondary = delta < 0 ? node.right : node.left; search(primary); if (heap.size() < k || delta ** 2 < heap.peekPriority()) { search(secondary); } }; search(this.root); return heap.toArray(); // Return values ordered closest to most distant| } rebalance() { const points = this.toArray("pre"); this.root = this.#buildBalanced(points); return this; } toArray(traversal = "bfs") { switch (traversal) { case "pre": return [...this.dfsPreOrder()]; case "bfs": return [...this.bfs()]; case "median": return [...this.spatialMedian()]; default: throw new Error(`KdTree2D: Unsupported traversal type: ${traversal}`); } } toDot(options = {}) { const { rankDir = "TB", scale = 1, compact = true, fillClr = () => "white", labelClr = () => "black" } = options; const lines = [ "digraph {", ` rankdir="${rankDir}";`, compact ? ` node [margin="0.05,0" width=0 height=0];` : "", ` edge [arrowsize=${compact ? 0.6 : 1.0}];` ]; const idMap = new Map(); let idCounter = 0; const visit = (node) => { if (!node) { return; } const id = `n${idCounter++}`; idMap.set(node, id); lines.push( ` ${id} [label="(${node.pt.x},${ node.pt.y })" style=filled fillcolor=${fillClr(node)} fontcolor=${labelClr( node )}];` ); if (node.left) { visit(node.left); lines.push(` ${id} -> ${idMap.get(node.left)};`); } if (node.right) { visit(node.right); lines.push(` ${id} -> ${idMap.get(node.right)};`); } }; visit(this.root); lines.push("}"); const dotSpec = dot`${lines.join("\n")}`; return scale === 1 ? dotSpec : md`

${dotSpec}

`; } // ----------------------------- Private helper methods static #distSq(a, b) { return (a.x - b.x) ** 2 + (a.y - b.y) ** 2; } static #inBox(pt, xMin, yMin, xMax, yMax) { return pt.x >= xMin && pt.x <= xMax && pt.y >= yMin && pt.y <= yMax; } *#recursiveMedian(points, depth = 0) { if (points.length === 0) { return; } const sorted = [...points].sort((a, b) => depth % 2 === 0 ? a.x - b.x || a.y - b.y : a.y - b.y || a.x - b.x ); const mid = Math.floor(sorted.length / 2); yield sorted[mid]; yield* this.#recursiveMedian(sorted.slice(0, mid), depth + 1); yield* this.#recursiveMedian(sorted.slice(mid + 1), depth + 1); } #buildBalanced(points, depth = 0) { if (points.length === 0) { return null; } const axis = depth % 2; const coord = axis === 0 ? "x" : "y"; const sorted = [...points].sort((a, b) => a[coord] - b[coord]); const mid = Math.floor(sorted.length / 2); const node = new KdTree2DNode(sorted[mid], axis); node.setLeft(this.#buildBalanced(sorted.slice(0, mid), depth + 1)); node.setRight(this.#buildBalanced(sorted.slice(mid + 1), depth + 1)); return node; } }35:[] 2f:{"title":"Extending mark interaction with Plot","cells":[{"id":0,"value":"# Extending mark interaction with Plot","pinned":false,"hidden":false,"mode":"md"},{"id":18,"value":"$31","pinned":false,"hidden":false,"mode":"md"},{"id":52,"value":"$32","pinned":true,"hidden":false,"mode":"ojs"},{"id":91,"value":"To use the `DotOverlay` class, provide a function that generates some SVG in response to the `[dataX,dataY]` coordinates. The `scales` element can be used to convert the data values back to screen coordinates for rendering.\n\nHere's a simple example that draws a dynamic ellipse under the mouse pointer representing penguin beak shape:","pinned":false,"hidden":false,"mode":"md"},{"id":30,"value":"Plot.plot({\n marks: [\n new DotOverlay(penguins, {\n x: \"culmen_length_mm\",\n y: \"culmen_depth_mm\",\n onPointerMove: ({ dataX, dataY, scales }) =>\n htl.svg``\n })\n ]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":95,"value":"The example above transforms the pointer's `[dataX,dataY]` values straight back to screen coordinates, so this is probably an over-engineered solution for this use-case. Where the approach becomes much more valuable is when we do more sophisticated work with the data values.\n\nHere is an example that does rapid spatial query of a large point set (50,000 points) using a [k-d tree](https://en.wikipedia.org/wiki/K-d_tree) to highlight a subset of points close to the pointer position.","pinned":false,"hidden":false,"mode":"md"},{"id":115,"value":"pointCoords = {\n const gauss = d3.randomNormal();\n const uniform = d3.randomInt(10000);\n return d3.range(0, 50000).map((d) => ({\n x: gauss() + 3,\n y: gauss() + 3\n }));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"kd = pointCoords.reduce((kd, pt) => kd.insert(pt), new KdTree2D()).rebalance()","pinned":false,"hidden":false,"mode":"ojs"},{"id":154,"value":"function drawSelected({ dataX, dataY, scales }) {\n const selPts = qType.startsWith(\"within\")\n ? kd.pointsWithinRadius(dataX, dataY, 0.25)\n : qType.startsWith(\"nearest\")\n ? kd.kNearestNeighbours(dataX, dataY, 500)\n : kd.rangeQuery(dataX - 0.25, dataY - 0.25, dataX + 0.25, dataY + 0.25);\n\n // Group all circles together\n return htl.svg`\n ${selPts.map(\n (pt) =>\n htl.svg``\n )}\n `;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":142,"value":"viewof qType = Inputs.radio(\n [\"within 0.25\", \"square range\", \"nearest 500 points\"],\n {\n label: \"Spatial query\",\n value: \"nearest 500 points\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":132,"value":"Plot.plot({\n style: \"cursor: crosshair\",\n width: 900,\n aspectRatio: 1,\n x: { ticks: 8, grid: true },\n y: { ticks: 8, grid: true },\n marks: [\n new DotOverlay(pointCoords, {\n x: \"x\",\n y: \"y\",\n fill: \"steelblue\",\n opacity: 0.4,\n r: 1,\n onPointerMove: drawSelected\n })\n ]\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":167,"value":"_**Thanks to @fil (Philippe Riviere) for some helpful suggestions (screen-data transformations and callback pattern).**_","pinned":false,"hidden":false,"mode":"md"},{"id":5,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md"},{"id":126,"value":"_Spatial indexing data structures:_","pinned":false,"hidden":false,"mode":"md"},{"id":123,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":128,"value":"class KdTree2DNode {\n #pt; // Point object with x and y properties\n #axis; // 0 = x-axis, 1 = y-axis\n #left = null;\n #right = null;\n #parent = null;\n\n constructor(pt, axis = 0) {\n this.#pt = pt;\n this.#axis = axis;\n }\n\n get pt() {\n return this.#pt;\n }\n\n get axis() {\n return this.#axis;\n }\n\n get left() {\n return this.#left;\n }\n\n get right() {\n return this.#right;\n }\n\n get parent() {\n return this.#parent;\n }\n\n setLeft(node) {\n this.#left = node;\n if (node) {\n node.#parent = this;\n }\n return this;\n }\n\n setRight(node) {\n this.#right = node;\n if (node) {\n node.#parent = this;\n }\n return this;\n }\n\n isLeaf() {\n return this.#left === null && this.#right === null;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":120,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"import { loadFonts, setPageStyle } from \"@jwolondon/teaching-utilities\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"_Page style:_","pinned":false,"hidden":false,"mode":"md"},{"id":12,"value":"loadFonts()","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"setPageStyle()","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W35","stdlib":"1","titling":"auto"}