29:null 2a:["$","title",null,{"children":"Spatial Data Structures | Jo Wood | Observable"}] 2f:T17b7,

KdTree

A k‑d tree for efficient spatial indexing and querying of objects. Coordinates are drawn from an explicit ordered list of object‑keys (coordKeys), each of which must refer to a numeric property on every point.

`constructor(points?: Array<object>, coordKeys?: Array<string>)`

Creates a k‑d tree in k = coordKeys.length dimensions (default: a 2d tree with elements ['x','y']). If an array of point‑objects is provided, a balanced tree is built. Each object must have a numeric property for every key in coordKeys, in the same order. If coordKeys is null, the numeric properties of the first point are used. If it is omitted, ["x", "y"] is used.

`root: KdTreeNode | null`

The root node, or null if the tree is empty.

`axisKeys: string[]`

The ordered coordinate keys used for successive splitting axes.

`k: number`

The number of indexed dimensions.

`insert(pt: object): KdTree`

Inserts a point‑object into the tree. The object must contain numeric values for each coordinate key defined at construction. If many insertions are made without balancing, performance may degrade. Returns the tree to support chaining.

`rebalance(): KdTree`

Rebuilds into a balanced tree for improved query performance. Useful after bulk inserts or highly structured data. Returns the tree to support chaining.

`find(queryPt: object): KdTreeNode | null`

Returns the node whose stored point exactly matches queryPt, or null if none. The query object must provide a numeric value for every configured coordinate key; additional properties are ignored.

`clear(): KdTree`

Clears the tree, removing all stored points.

`*[Symbol.iterator](): Iterable<object>`

Returns an iterator over all items in the tree in spatial-median order. This provides a convenient way of iterating over all points. For example,
for (const pt of kdTree)
or
[...kdTree].

`*dfsPreOrder(): Iterable<object>`

Generator yielding all stored point‑objects in depth‑first pre‑order.

`*bfs(): Iterable<object>`

Generator yielding all stored point‑objects in breadth‑first order.

`*spatialMedian(): Iterable<object>`

Generator yielding points in recursive median‑split order for spatial locality.

`*rangeQuery(minPt: object, maxPt: object): Iterable<object>`

Yields all points within the axis‑aligned bounding box defined by minPt and maxPt, each of which must supply the same coordinate keys as defined at construction.

`*pointsWithinRadius(queryPt: object, r: number): Iterable<object>`

Yields all points within Euclidean distance r of queryPt.

`nearestNeighbour(queryPt: object, excludeSelf?: boolean): object | null`

Returns the stored point nearest to queryPt, or null if the tree is empty. If excludeSelf is true, points whose configured coordinates exactly match the query point are excluded.

`kNearestNeighbours(queryPt: object, k: number, options?: {sorted?: boolean}): Array<object>`

Returns up to k stored points nearest to queryPt. By default, selected points are returned in unspecified heap order, avoiding a sorting step. If sorted:true, they are returned in increasing distance from the query point.

`toArray(traversal?: "pre" | "bfs" | "median"): Array<object>`

Returns an array of all stored points in the specified traversal order (default "bfs").

`toDot(options?: object): Element`

Generates a GraphViz dot representation of the tree. Options:

rankDir: layout direction (e.g. "LR","TB"; default"TB")
scale: rendering scale (default 1)
compact: use compact node spacing (default true)
label: function to render each node’s label (default shows all enumerable properties of the stored point)
fillClr: function to pick node fill colour (default ()⇒"white")
labelClr: function to pick text colour (default ()⇒"black")

Returns an HTML or SVG element containing the visualization.

30:T712,

KdTreeNode

A node in a k-dimensional k-d tree. Stores a point object, the axis it splits on, and links to child and parent nodes.

`constructor(pt: object, axis: number)`

Creates a new tree node for the given point and axis index (0 ≤ axis < k).

`pt: object`

The point object stored in this node (read-only).

`axis: number`

The axis index used for splitting at this node (read-only).

`left: KdTreeNode | null`

The left child node (read-only). Set using setLeft().

`right: KdTreeNode | null`

The right child node (read-only). Set using setRight().

`parent: KdTreeNode | null`

The parent node, or null if this node is the root (read-only).

`setLeft(node: KdTreeNode | null): KdTreeNode`

Sets the left child node and updates its parent reference.

`setRight(node: KdTreeNode | null): KdTreeNode`

Sets the right child node and updates its parent reference.

`isLeaf(): boolean`

Returns true if this node has no children.

31:T1eec,

PointQuadtree

A point quadtree for indexing 2D points of the form { x: number, y: number }. Supports optional auto-resizing via re-rooting so insertions outside the current root bounds can be accommodated efficiently.

`constructor(options?: object)`

Creates a PointQuadtree with the following options:

boundary: initial root bounds { x, y, halfWidth, halfHeight }. If omitted, the initial boundary is inferred from the first inserted point.
capacity: max items per leaf before subdivision (default 4)
autoResize: grow root to fit out-of-bounds inserts (default true)
strict: when autoResize:false, throw on out-of-bounds insert (default false)
maxDepth: max subdivision depth (default Infinity)
square: keep root expansions square (use max of half-width/height) (default true)

`insert(p: {x:number, y:number}): PointQuadtree`

Inserts a point. If autoResize is enabled and the point lies outside the current root boundary, the root is enlarged until the point fits. Returns this quadtree to support chaining.
Throws: RangeError if out-of-bounds when autoResize:false and strict:true.

`fitsRoot(p: {x:number, y:number}): boolean`

Returns true if the point fits within the current root boundary (or if the tree is empty). Useful when autoResize:false.

`clear(): PointQuadtree`

Clears the tree. Returns the tree to support chaining.

`capacity: number`

Read-only accessor for the leaf capacity configured at construction.

`maxDepth: number`

Read-only accessor for the maximum subdivision depth.

`bounds: {x:number, y:number, halfWidth:number, halfHeight:number} | null`

The current root boundary, or null if empty.

`*[Symbol.iterator](): Iterable<object>`

Iterates all stored points (leaf-first, subtree order). Examples:
for (const p of qt) or [...qt].

`*items(): Iterable<object>`

Generator yielding all stored points (same order as the default iterator).

`toArray(): Array<object>`

Returns an array of all stored points.

`*rangeQuery(range: object): Iterable<object>`

Generator that yields all items within the axis-aligned bounding box specified by range. The range object must define numeric x, y, halfWidth, and halfHeight properties. Items are yielded in an unspecified order.
To collect results into an array:
const results = [...qt.rangeQuery(range)];

`*cells(options?: object): Iterable<{ boundary: {x:number, y:number, halfWidth:number, halfHeight:number}, depth: number, isLeaf: boolean, size: number }>`

Generator that yields the quadtree's spatial cells (node boundaries) for visualization and analysis. Each yielded object includes the cell's boundary, its depth in the tree, whether it is a leaf (isLeaf), and the number of items stored at that node (size). Always includes the root boundary.

Options:

leavesOnly (boolean): yield only leaf cells (default: false)
includeInternal (boolean): include internal (non-leaf) cells (default: true)
order ("pre"|"bfs"): traversal order; DFS pre-order or breadth-first (default: "pre")

Returns: an iterator over cell descriptors.

`toDot(options?: object): Element`

Generates a GraphViz DOT visualization of the quadtree.
Can be used to illustrate relatively small quadtrees for illustrative purposes.
Options:

rankDir: layout direction (e.g. "TB", "LR"; default "TB")
scale: scale factor for rendering (default 1)
compact: compact node spacing (default true)
fillClr(node): fill colour for node boxes (default () ⇒ "white")
labelClr(node): text colour (default () ⇒ "black")
label(node): node label function (default shows region boundary and occupancy)
showItems: render items at leaves as dashed child boxes (default false)
itemLabel(item): label function for item boxes

`PointQuadtree.minL1DistancePointAABB(...)`

Returns the Manhattan (L1) distance from a point to an axis-aligned rectangle in min/max form ({minX, minY, maxX, maxY}). Returns 0 if the point lies inside. Useful for L1 ball (diamond) tests.

`PointQuadtree.halfToMinMax(...)`

Converts a centre/half-extent rectangle ({x, y, halfWidth, halfHeight}) to min/max form ({minX, minY, maxX, maxY}). Useful for splitting and distance tests.

`PointQuadtree.minMaxToHalf(...)`

Converts a min/max rectangle ({minX, minY, maxX, maxY}) to centre/half-extent form ({x, y, halfWidth, halfHeight}).

`PointQuadtree.splitBox(...)`

Splits a rectangle into up to four integer-aligned quadrants in fixed order: NW, NE, SW, SE. Uses integer-safe midpoints (mx = floor((minX+maxX)/2), my = floor((minY+maxY)/2)). Empty quadrants (where min > max) are omitted. This utility is intended for inclusive integer-coordinate boxes. It should not be used to divide continuous-coordinate extents.

`PointQuadtree.intersectsAABB(...)`

Returns true if two axis-aligned rectangles in centre/half form ({x, y, halfWidth, halfHeight}) intersect or touch; otherwise false.

32:T1e34,

RegionQuadtree

A region quadtree for 2D rectangular regions. Each item must have a bounds property of the form { x, y, halfWidth, halfHeight }. Items that straddle child boundaries are retained at their current internal node to avoid duplication.

`constructor(options?: object)`

Creates a RegionQuadtree. Recognised options:

boundary: initial root bounds { x, y, halfWidth, halfHeight } (default: inferred from first insert)
capacity: max items stored in a leaf before subdivision (default 4)
autoResize: grow root to fit out-of-bounds inserts (default true)
strict: when autoResize:false, throw on out-of-bounds insert (default false)
maxDepth: max subdivision depth (default Infinity)
square: keep root expansions square (default true)

`insert(item: { bounds: {x:number, y:number, halfWidth:number, halfHeight:number}, ... }): RegionQuadtree`

Inserts a rectangular region. If autoResize is enabled and out-of-bounds, the root is enlarged to fit. Regions that do not fit cleanly into a single child remain at the current node. Returns the tree (chainable).
Throws: RangeError if out-of-bounds with autoResize:false and strict:true.

`fitsRoot(item: {bounds: {...}}): boolean`

Returns true if the region fully lies within the current root boundary (or if the tree is empty).

`clear(): RegionQuadtree`

Clears the tree. Returns the tree to support chaining.

`capacity: number`

Read-only accessor for the leaf capacity configured at construction.

`maxDepth: number`

Read-only accessor for the maximum subdivision depth.

`bounds: {x:number, y:number, halfWidth:number, halfHeight:number} | null`

The current root boundary, or null if empty.

`*[Symbol.iterator](): Iterable<object>`

Iterates all stored items (leaf-first, subtree order).

`*items(): Iterable<object>`

Generator yielding all stored items.

`toArray(): Array<object>`

Returns an array of all stored items.

`*rangeQuery(range: object): Iterable<object>`

Yields regions whose complete bounding boxes are contained within the query range. Regions that only partially intersect the query range are not returned. The range object must define numeric x, y, halfWidth, and halfHeight properties. Items are yielded in an unspecified order.
To collect results into an array:
const results = [...qt.rangeQuery(range)];

`*cells(options?: object): Iterable<{ boundary: {x:number, y:number, halfWidth:number, halfHeight:number}, depth: number, isLeaf: boolean, size: number }>`

Options:

leavesOnly (boolean): yield only leaf cells (default: false)
includeInternal (boolean): include internal (non-leaf) cells (default: true)
order ("pre"|"bfs"): traversal order; DFS pre-order or breadth-first (default: "pre")

Returns: an iterator over cell descriptors.

`toDot(options?: object): Element`

Generates a GraphViz DOT visualization of the quadtree.
Can be used to illustrate relatively small quadtrees for illustrative purposes.
Options:

rankDir: layout direction (e.g. "TB", "LR"; default "TB")
scale: scale factor for rendering (default 1)
compact: compact node spacing (default true)
fillClr(node): fill colour for node boxes (default () ⇒ "white")
labelClr(node): text colour (default () ⇒ "black")
label(node): node label function (default shows region bounds and occupancy)
showItems: render items at leaves as dashed child boxes (default false)
itemLabel(item): label function for item boxes

`RegionQuadtree.minL1DistancePointAABB(...)`

Returns the Manhattan (L1) distance from a point to an axis-aligned rectangle in min/max form ({minX, minY, maxX, maxY}). Returns 0 if the point lies inside. Useful for L1 circle–rectangle tests.

`RegionQuadtree.halfToMinMax(...)`

Converts a centre/half-extent rectangle ({x, y, halfWidth, halfHeight}) to min/max form ({minX, minY, maxX, maxY}). Useful for splitting and distance tests.

`RegionQuadtree.minMaxToHalf(...)`

Converts a min/max rectangle ({minX, minY, maxX, maxY}) to centre/half-extent form ({x, y, halfWidth, halfHeight}).

`RegionQuadtree.splitBox(...)`

`RegionQuadtree.intersectsAABB(...)`

Returns true if two axis-aligned rectangles in centre/half form ({x, y, halfWidth, halfHeight}) intersect or touch; otherwise false.

33:T233c,

PointOctree

A point octree for indexing 3D points of the form { x: number, y: number, z: number }. Supports optional auto-resizing via re-rooting so insertions outside the current root bounds can be accommodated efficiently.

`constructor(options?: object)`

Creates a PointOctree with the following options:

boundary: initial root bounds { x, y, z, halfWidth, halfHeight, halfDepth } (default: inferred from first insert)
capacity: max items per leaf before subdivision (default 4)
autoResize: grow root to fit out-of-bounds inserts (default true)
strict: when autoResize:false, throw on out-of-bounds insert (default false)
maxDepth: max subdivision depth (default Infinity)
cube: keep root expansions cubic (use max of half-width/height/depth) (default true)

Throws: RangeError if capacity is not a positive integer, if maxDepth is neither a non-negative integer nor Infinity, or if the supplied boundary contains invalid or non-positive extents.

`insert(p: {x:number, y:number, z:number}): PointOctree`

Inserts a point. If autoResize is enabled and the point lies outside the current root boundary, the root is enlarged until the point fits. Returns this octree to support chaining.
Throws: RangeError if out-of-bounds when autoResize:false and strict:true.

`fitsRoot(p: {x:number, y:number, z:number}): boolean`

Returns true if the point fits within the current root boundary (or if the tree is empty). Useful when autoResize:false.

`clear(): PointOctree`

Clears the tree. Returns the tree to support chaining.

`capacity: number`

Read-only accessor for the leaf capacity configured at construction.

`maxDepth: number`

Read-only accessor for the maximum subdivision depth.

`bounds: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number} | null`

The current root boundary, or null if empty.

`*[Symbol.iterator](): Iterable<object>`

Iterates all stored points (leaf-first, subtree order). Examples:
for (const p of ot) or [...ot].

`*items(): Iterable<object>`

Generator yielding all stored points (same order as the default iterator).

`toArray(): Array<object>`

Returns an array of all stored points.

`*rangeQuery(range: object): Iterable<object>`

Generator that yields all items within the axis-aligned bounding box specified by range. The range object must define numeric x, y, z, halfWidth, halfHeight, and halfDepth properties. Items are yielded in an unspecified order.
To collect results into an array: const results = [...ot.rangeQuery(range)];

`*cells(options?: object): Iterable<{ boundary: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}, depth: number, isLeaf: boolean, size: number }>`

Generator that yields the octree’s spatial cells (node boundaries) for visualisation and analysis. Each yielded object includes the cell’s boundary, its depth in the tree, whether it is a leaf (isLeaf), and the number of items stored at that node (size).

Options:

leavesOnly (boolean): yield only leaf cells (default: false)
includeInternal (boolean): include internal (non-leaf) cells (default: true)
order ("pre"|"bfs"): traversal order; DFS pre-order or breadth-first (default: "pre")

Returns: an iterator over cell descriptors.

`toDot(options?: object): Element`

Generates a GraphViz DOT visualisation of the octree.
Options:

rankDir: layout direction (e.g. "TB", "LR"; default "TB")
scale: scale factor for rendering (default 1)
compact: compact node spacing (default true)
fillClr(node): fill colour for node boxes (default () ⇒ "white")
labelClr(node): text colour (default () ⇒ "black")
label(node): node label function (default shows region boundary and occupancy)
showItems: render items at leaves as dashed child boxes (default false)
itemLabel(item): label function for item boxes

`PointOctree.minL1DistancePointAABB3D(p: {x:number, y:number, z:number}, box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): number`

Returns the Manhattan (L1) distance from a point { x, y, z } to an axis-aligned box { minX, maxX, minY, maxY, minZ, maxZ }. If the point lies inside the box, the distance is 0. Useful for L1 ball (octahedron) vs. box intersection via minL1DistancePointAABB3D(p, box) <= radius.

`PointOctree.halfToMinMax(b: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}): {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}`

Converts a centre/half-extent box to min/max form. Handy when splitting nodes or when distance tests prefer min/max bounds.

`PointOctree.minMaxToHalf(box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}`

Converts a min/max box to centre/half-extent form. Useful for normalising bounds before feeding APIs expecting centre/half extents.

`PointOctree.splitBox(box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): Array<{minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}>`

Splits a box into up to eight integer-aligned octants (order implied by iteration). Uses an integer-safe split at mx = floor((minX+maxX)/2), my = floor((minY+maxY)/2), and mz = floor((minZ+maxZ)/2), producing ranges [min..m] and [m+1..max] per axis. Empty octants are omitted. It is intended for inclusive integer-coordinate boxes. It should not be used to divide continuous-coordinate extents.

`PountOctree.intersectsAABB3D(a: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}, r: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}): boolean`

Returns true if two axis-aligned boxes (given in centre/half form) intersect or touch; otherwise false. This is the standard AABB–AABB overlap test in 3D.

34:T232a,

RegionOctree

A region octree for 3D rectangular regions. Each item must have a bounds property of the form { x, y, z, halfWidth, halfHeight, halfDepth }. Items that straddle child boundaries are retained at their current internal node to avoid duplication.

`constructor(options?: object)`

Creates a RegionOctree. Recognised options:

boundary: initial root bounds { x, y, z, halfWidth, halfHeight, halfDepth } (default: inferred from first insert)
capacity: max items stored in a leaf before subdivision (default 4)
autoResize: grow root to fit out-of-bounds inserts (default true)
strict: when autoResize:false, throw on out-of-bounds insert (default false)
maxDepth: max subdivision depth (default Infinity)
cube: keep root expansions cubic (default true)

Throws: RangeError if capacity is not a positive integer, if maxDepth is neither a non-negative integer nor Infinity, or if the supplied boundary contains invalid or non-positive extents.

`insert(item: { bounds: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}, ... }): RegionOctree`

`fitsRoot(item: {bounds: {...}}): boolean`

Returns true if the region fully lies within the current root boundary (or if the tree is empty).

`clear(): RegionOctree`

Clears the tree. Returns the tree to support chaining.

`capacity: number`

Read-only accessor for the leaf capacity configured at construction.

`maxDepth: number`

Read-only accessor for the maximum subdivision depth.

`bounds: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number} | null`

The current root boundary, or null if empty.

`[iterator](): Iterable<object>`

Iterates all stored items (leaf-first, subtree order).

`*items(): Iterable<object>`

Generator yielding all stored items.

`toArray(): Array<object>`

Returns an array of all stored items.

`*rangeQuery(range: object): Iterable<object>`

Yields regions whose complete bounding boxes are contained within the query range. Regions that only partially intersect the query range are not returned. The range object must define numeric x, y, z, halfWidth, halfHeight, and halfDepth properties. Items are yielded in an unspecified order.
To collect results into an array: const results = [...ot.rangeQuery(range)];

`*cells(options?: object): Iterable<{ boundary: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}, depth: number, isLeaf: boolean, size: number }>`

Options:

leavesOnly (boolean): yield only leaf cells (default: false)
includeInternal (boolean): include internal (non-leaf) cells (default: true)
order ("pre"|"bfs"): traversal order; DFS pre-order or breadth-first (default: "pre")

Returns: an iterator over cell descriptors.

`toDot(options?: object): Element`

Generates a GraphViz DOT visualisation of the octree.
Options:

rankDir: layout direction (e.g. "TB", "LR"; default "TB")
scale: scale factor for rendering (default 1)
compact: compact node spacing (default true)
fillClr(node): fill colour for node boxes (default () ⇒ "white")
labelClr(node): text colour (default () ⇒ "black")
label(node): node label function (default shows region bounds and occupancy)
showItems: render items at leaves as dashed child boxes (default false)
itemLabel(item): label function for item boxes

`RegionOctree.minL1DistancePointAABB3D(p: {x:number, y:number, z:number}, box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): number`

Returns the Manhattan (L1) distance from a point { x, y, z } to an axis-aligned box { minX, maxX, minY, maxY, minZ, maxZ }. If the point lies inside the box, the distance is 0. Useful for “sphere” (L1 diamond) vs. box intersection via minL1DistancePointAABB3D(p, box) <= radius.

`RegionOctree.halfToMinMax(b: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}): {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}`

Converts a centre/half-extent box to min/max form. Handy when splitting nodes or when distance tests prefer min/max bounds.

`RegionOctree.minMaxToHalf(box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}`

Converts a min/max box to centre/half-extent form. Useful for normalising bounds before feeding APIs expecting centre/half extents.

`RegionOctree.splitBox(box: {minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}): Array<{minX:number, maxX:number, minY:number, maxY:number, minZ:number, maxZ:number}>`

`RegionOctree.intersectsAABB3D(a: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}, r: {x:number, y:number, z:number, halfWidth:number, halfHeight:number, halfDepth:number}): boolean`

Returns true if two axis-aligned boxes (given in centre/half form) intersect or touch; otherwise false. This is the standard AABB–AABB overlap test in 3D.

35:Tc03,function birdTraj(options = {}) { const { totalPoints = 400, ascendCount = 380, ascendRadius = 5, descendRadius = 2, ascendRot = 4, descendRot = 2, ascendHeight = 10, descendDrop = 10, driftRadius = 2, jitterAmt = 0.1, xyzScale = 50 } = options; const descendCount = totalPoints - ascendCount; const ascendStep = ascendHeight / ascendCount; const descendStep = descendDrop / descendCount; const driftSpeed = (2 * Math.PI) / totalPoints; const pts = []; let lastAngle = 0; // ——— Ascent ——— for (const i of Array.from({length: ascendCount}, (_, i) => i)) { const t = i; const driftAng = driftSpeed * i; const cx = driftRadius * Math.cos(driftAng); const cy = driftRadius * Math.sin(driftAng); const cyclePos = ((i / ascendCount) * ascendRot) % 1; const rPulse = 0.8 + 0.4 * Math.sin(2 * Math.PI * cyclePos); const r = ascendRadius * rPulse + (Math.random() - 0.5) * jitterAmt; const angle = 2 * Math.PI * ascendRot * (i / ascendCount) + (Math.random() - 0.5) * jitterAmt; const x = cx + r * Math.cos(angle); const y = cy + r * Math.sin(angle); const z = i * ascendStep + (Math.random() - 0.5) * jitterAmt; pts.push({x, y, z, t}); lastAngle = angle; } // Compute drift centre at top of climb const driftAngTop = driftSpeed * (ascendCount - 1); const driftCxTop = driftRadius * Math.cos(driftAngTop); const driftCyTop = driftRadius * Math.sin(driftAngTop); const lastPt = pts[pts.length - 1]; const r0 = descendRadius * 0.8; // Centre that makes the very first descent point land on lastPt const centreDesc0 = { x: lastPt.x - r0 * Math.cos(lastAngle), y: lastPt.y - r0 * Math.sin(lastAngle) }; const driftCentre0 = {x: driftCxTop, y: driftCyTop}; // ——— Descent ——— for (const j of Array.from({length: descendCount}, (_, j) => j)) { const t = ascendCount + j; const driftAngJ = driftSpeed * (ascendCount - 1 + j); const driftCxJ = driftRadius * Math.cos(driftAngJ); const driftCyJ = driftRadius * Math.sin(driftAngJ); const centreX = centreDesc0.x + (driftCxJ - driftCentre0.x); const centreY = centreDesc0.y + (driftCyJ - driftCentre0.y); // No randomness on j=0 to preserve continuity const jitterR = j === 0 ? 0 : (Math.random() - 0.5) * jitterAmt; const jitterA = j === 0 ? 0 : (Math.random() - 0.5) * jitterAmt; const jitterZ = j === 0 ? 0 : (Math.random() - 0.5) * jitterAmt; const cyclePos = ((j / descendCount) * descendRot) % 1; const rPulse = 0.8 + 0.4 * Math.sin(2 * Math.PI * cyclePos); const r = descendRadius * rPulse + jitterR; const angle = lastAngle + 2 * Math.PI * descendRot * (j / descendCount) + jitterA; const x = centreX + r * Math.cos(angle); const y = centreY + r * Math.sin(angle); const z = ascendHeight - j * descendStep + jitterZ; pts.push({x, y, z, t}); } return pts.map((d) => ({ x: d.x * xyzScale, y: d.y * xyzScale, z: d.z * xyzScale, t: d.t })); }36: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 } }37:[] 2d:{"id":"c42dda91086fa3f8","slug":"data-structures-spatial","title":"Spatial Data Structures","thumbnail":"57637a0088bad2bf747740831c2e449c8e1f84dcf19ce69fd6b3373fdb4a91a8","access_level":"public","create_time":"$D2025-07-23T06:50:31.733Z","update_time":"$D2026-09-22T14:08:07.089Z","view_time":null,"first_public_time":"$D2026-09-22T14:24:14.810Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":1106,"publish_version":1106,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"},{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":{"id":"cf3a41cde0560514","slug":"data-structures","title":"data structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"Spatial Data Structures","cells":[{"id":0,"value":"# Spatial Data Structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":808,"value":"Spatial data structures organise geometric objects so that queries such as range searches and nearest-neighbour searches can avoid examining every stored item. The structures below cover point and region data in two, three and higher dimensions.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"## 1. k-d tree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":251,"value":"A [k-d tree](https://en.wikipedia.org/wiki/K-d_tree) is a space-partitioning data structure designed for efficient spatial queries such as nearest neighbour calculations. This can work with any number of dimensions (`k`), but is commonly applied to 2D data on a plane and 3D data in a volume.\n\nConsider the 2D case.\n\nFor a given point set, first, the median point in the x-direction is selected. This becomes the root of the k-d tree. Then the median point in the y-direction is found from just the points to the left of the root point. This becomes the root's left child node. Similarly the median y-direction point to the right of the root becomes its right child node. This continues recursively for each node, alternating between horizontal and vertical partitioning until all points have been assigned.\n\nThe figure below shows an example for a small point set (similar to the example used in [this explanation of k-d trees](https://youtu.be/BK5x7IUTIyU)).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":217,"value":"

\n ${plotKdPoints(pts,myKd)}\n ${myKd.toDot({ scale: 1, label: (node) => node.pt.name })}\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":267,"value":"Nearest-neighbour queries traverse the tree by following the side of each splitting plane containing the query point. Other branches can be skipped when their splitting planes are farther away than the best result already found. In a balanced, low-dimensional k-d tree this often gives approximately ${tex`O(\\log n)`} query time, but the worst case remains ${tex`O(n)`}, particularly for unfavourable point distributions or higher-dimensional data.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":290,"value":"Here's an example that creates the k-d tree for the point set illustrated above:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":35,"value":"import {KdTree} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":59,"value":"const pts = [\n {name: \"a\", x: 54, y: 55},\n {name: \"b\", x: 41, y: 54},\n {name: \"c\", x: 19, y: 51},\n {name: \"d\", x: 69, y: 51},\n {name: \"e\", x: 33, y: 48},\n {name: \"f\", x: 58, y: 47},\n {name: \"g\", x: 70, y: 40},\n {name: \"h\", x: 20, y: 38},\n {name: \"i\", x: 45, y: 37},\n {name: \"j\", x: 34, y: 34},\n {name: \"k\", x: 53, y: 33},\n {name: \"l\", x: 69, y: 28},\n {name: \"m\", x: 18, y: 25},\n {name: \"n\", x: 59, y: 21},\n {name: \"o\", x: 25, y: 20}\n];\n\nconst myKd = new KdTree(pts);\ndisplay([...myKd]) // Display the point objects in spatial-median order)","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":294,"value":"The principal reason for using a k-d tree is for rapid querying of larger point sets. The example below uses one to find the nearest points to the pointer from a set of 20,000 points. For details of how the interaction is handled, see [Extending mark interaction with Plot](https://observablehq.com/@jwolondon/extending-mark-interaction-with-plot).","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":44,"value":"{\n const drawSelected = ({dataX, dataY, scales}) => {\n const selPts = qType.startsWith(\"within\")\n ? kd2.pointsWithinRadius({x: dataX, y: dataY}, 0.5)\n : qType.startsWith(\"nearest\")\n ? kd2.kNearestNeighbours({x: dataX, y: dataY}, 500)\n : kd2.rangeQuery(\n {x: dataX - 0.5, y: dataY - 0.5},\n {x: dataX + 0.5, y: dataY + 0.5}\n );\n\n // Group all circles together\n return htl.svg`\n ${selPts.map(\n (pt) =>\n htl.svg``\n )}\n `;\n };\n\n display(\n Plot.plot({\n style: \"cursor: crosshair\",\n aspectRatio: 1,\n x: {ticks: 4, grid: true},\n y: {ticks: 4, grid: true},\n marks: [\n new DotOverlay(pts2, {\n x: \"x\",\n y: \"y\",\n fill: \"steelblue\",\n opacity: 0.4,\n r: 1,\n onPointerMove: drawSelected\n })\n ]\n })\n );\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"const qType = view(\n Inputs.radio([\"within 0.5\", \"square range\", \"nearest 500 points\"], {\n label: \"Spatial query\",\n value: \"nearest 500 points\"\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":22,"value":"The tree can be used for storing three- or higher-dimensional data. Here for example is a simple 4D point set (x,y,z and time) representing the trajectory of a bird ascending and then rapidly descending:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":569,"value":"const points4d = birdTraj();\nconst mykd4 = new KdTree(points4d, [\"x\", \"y\", \"z\", \"t\"]);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":659,"value":"We can use the k-d tree to find the 10 nearest bird locations to a given position (0,0,z,t):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":590,"value":"const nearestTs = mykd4\n .kNearestNeighbours({ x: 0, y: 0, z: sel.z, t: sel.t }, 10)\n .map((d) => d.t)\ndisplay(nearestTs)","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":671,"value":"const zDomain = [\n Math.floor(d3.min(points4d, (d) => d.z)),\n Math.ceil(d3.max(points4d, (d) => d.z))\n];\nconst sel = view(\n Inputs.form({\n z: Inputs.range(zDomain, {\n label: \"elevation (z)\",\n step: 1,\n value: 0\n }),\n t: Inputs.range([0, points4d.length - 1], {\n label: \"time (t)\",\n step: 1,\n value: 10\n })\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":474,"value":"const scatter = plot3d(points4d, {\n w: 400,\n zoom: 0.8,\n radiusF: 0.01,\n upAxis: \"z\"\n});\ndisplay(scatter);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":309,"value":"$2f","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":311,"value":"$30","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":683,"value":"## 2. Point Quadtree","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":837,"value":"A [quadtree](https://en.wikipedia.org/wiki/Quadtree) divides space into quadrants. Each quadrant has a _capacity_ such that if a quadrant contains more than _capacity_ items, it is further divided into four smaller quadrants. These are in turn checked against the capacity subdividing as necessary. The result is a hierarchical subdivision of space with smaller units in areas of greatest concentration of items.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":855,"value":"A _point quadtree_ stores points in these quads. For example,","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":716,"value":"{\n const cells = [...pqt.cells()].map((d) => d.boundary);\n\n display(\n Plot.plot({\n width: 640,\n aspectRatio: 1,\n x: {ticks: d3.range(-16, 16.1, 4)},\n y: {ticks: d3.range(-16, 16.1, 4)},\n marks: [\n Plot.rect(cells, {\n x1: (d) => d.x - d.halfWidth,\n y1: (d) => d.y - d.halfHeight,\n x2: (d) => d.x + d.halfWidth,\n y2: (d) => d.y + d.halfHeight,\n stroke: \"firebrick\",\n strokeWidth: 0.2\n }),\n Plot.dot(qtPts, {fill: \"steelblue\", opacity: 0.9, r: 1})\n ]\n })\n );\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":747,"value":"const capacity = view(\n Inputs.range([1, qtPts.length], {\n label: \"Capacity\",\n step: 1,\n value: 10,\n transform: Math.log\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":845,"value":"A _range query_ visits only cells that intersect the query rectangle. Its cost depends on the spatial distribution, the cell capacity, the size of the query and the number of reported items. If ${tex`v`} cells are visited and ${tex`k`} items are returned, the cost is ${tex`O(v+k)`}. Localised queries over well-distributed data can therefore examine far fewer than ${tex`n`} items, although the worst case remains ${tex`O(n)`}.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":858,"value":"The points are represented as objects with at least `x` and `y` elements. Here's a simple example with the _capacity_ set to 1 (i.e. at most one point in an undivided quadrant):","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":720,"value":"import {PointQuadtree} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":860,"value":"const simpleQt = pts.reduce(\n (qt, point) => qt.insert(point),\n new PointQuadtree({\n capacity: 1,\n boundary: {x: 40, y: 35, halfWidth: 35, halfHeight: 35}\n })\n);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":922,"value":"

\n ${plotQtPoints(pts,simpleQt)}\n ${simpleQt.toDot({\n rankDir: \"LR\",\n fillClr: (d) => (d.isDivided || d.size < 1 ? \"white\" : \"lightblue\"),\n scale: 0.4\n})}\n\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":936,"value":"Performing a range query on the point quadtree to find the points that have `x ≥ 50` and `y ≥ 50`:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":938,"value":"[...simpleQt.rangeQuery(PointQuadtree.minMaxToHalf({minX: 50, minY: 50}))]","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":973,"value":"The benefit of fast range queries only becomes apparent with larger datasets:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":798,"value":"const pqt2 = pts2.reduce(\n (qt, point) => qt.insert(point),\n new PointQuadtree({\n boundary: {\n x: 3,\n y: 3,\n halfWidth: 5,\n halfHeight: 5\n }\n })\n);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":770,"value":"{\n const drawSelected = ({dataX, dataY, scales}) => {\n const selPts = [\n ...pqt2.rangeQuery({\n x: dataX,\n y: dataY,\n halfWidth: 0.5,\n halfHeight: 0.5\n })\n ];\n\n // Group all circles together\n return htl.svg`\n ${selPts.map(\n (pt) =>\n htl.svg``\n )}\n `;\n };\n\n display(\n Plot.plot({\n style: \"cursor: crosshair\",\n aspectRatio: 1,\n x: {ticks: 4, grid: true},\n y: {ticks: 4, grid: true},\n marks: [\n new DotOverlay(pts2, {\n x: \"x\",\n y: \"y\",\n fill: \"steelblue\",\n opacity: 0.4,\n r: 1,\n onPointerMove: drawSelected\n })\n ]\n })\n );\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":687,"value":"$31","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":813,"value":"## 3. Region Quadtree\n\nA region quadtree stores two-dimensional axis-aligned rectangles rather than points. A region is passed to a child only when its complete bounding box fits within that child’s cell. A region crossing a subdivision boundary remains at the current internal node, avoiding duplication between children.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":689,"value":"$32","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":816,"value":"## 4. Point Octree\n\nAn octree is the three-dimensional counterpart of a quadtree: each cell can be subdivided into eight octants. A point octree is useful for indexing points in a volume, with denser parts of the point distribution represented by progressively smaller cells.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":832,"value":"$33","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":819,"value":"## 5. Region Octree\n\nA region octree stores three-dimensional axis-aligned boxes. Regions that fit completely within one octant descend into that child; regions crossing one or more splitting planes remain at the current node. This avoids duplicating a region across multiple octants while still allowing unrelated branches to be excluded from range queries.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":835,"value":"$34","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":256,"value":"_Data and trees used for figures:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":100,"value":"function kdPartitionLines(tree, xMin, xMax, yMin, yMax) {\n const lines = [];\n\n const visit = (node, x1, x2, y1, y2, depth = 0) => {\n if (!node) {\n return;\n }\n const {x, y} = node.pt;\n\n if (node.axis === 0) {\n lines.push({x, y1, y2, axis: 0, depth});\n visit(node.left, x1, x, y1, y2, depth + 1);\n visit(node.right, x, x2, y1, y2, depth + 1);\n } else {\n lines.push({x1, x2, y: y, axis: 1, depth});\n visit(node.left, x1, x2, y1, y, depth + 1);\n visit(node.right, x1, x2, y, y2, depth + 1);\n }\n };\n\n visit(tree.root, xMin, xMax, yMin, yMax);\n return lines;\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"function plotKdPoints(pts, kd) {\n const kdLines = kdPartitionLines(kd, 10, 80, 10, 60);\n const lineWidth = [5, 3, 2, 0.5];\n\n return Plot.plot({\n width: 420,\n aspectRatio: 1,\n\n marks: [\n Plot.ruleX(\n kdLines.filter((l) => l.axis === 0),\n {\n x: \"x\",\n y1: \"y1\",\n y2: \"y2\",\n stroke: \"steelblue\",\n strokeWidth: (d) => lineWidth[d.depth],\n strokeDasharray: [7, 4],\n opacity: 0.9\n }\n ),\n Plot.ruleY(\n kdLines.filter((l) => l.axis === 1),\n {\n y: \"y\",\n x1: \"x1\",\n x2: \"x2\",\n stroke: \"steelblue\",\n strokeWidth: (d) => lineWidth[d.depth],\n strokeDasharray: [7, 4],\n opacity: 0.9\n }\n ),\n Plot.dot(pts, {x: \"x\", y: \"y\", fill: \"black\", r: 4}),\n Plot.text(pts, {x: \"x\", y: \"y\", text: \"name\", dx: 10, dy: -10})\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":955,"value":"function plotQtPoints(pts, qt) {\n const cells = [...qt.cells()].map((d) => d.boundary);\n return Plot.plot({\n width: 480,\n aspectRatio: 1,\n marks: [\n Plot.rect(cells, {\n x1: (d) => d.x - d.halfWidth,\n y1: (d) => d.y - d.halfHeight,\n x2: (d) => d.x + d.halfWidth,\n y2: (d) => d.y + d.halfHeight,\n stroke: \"steelblue\",\n strokeWidth: 0.2\n }),\n Plot.dot(pts, {x: \"x\", y: \"y\", fill: \"black\", r: 4}),\n Plot.text(pts, {x: \"x\", y: \"y\", text: \"name\", dx: 10, dy: -10})\n ]\n });\n}","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"const pts2 = (() => {\n const gauss = d3.randomNormal();\n const uniform = d3.randomInt(10000);\n const rInt = d3.randomInt(255);\n\n return d3.range(0, 20000).map((d) => ({\n x: gauss() + 3,\n y: gauss() + 3,\n clr: `rgb(${rInt()},${rInt()},${rInt()})`\n }));\n})();","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":25,"value":"const kd2 = new KdTree(pts2)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":529,"value":"$35","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":753,"value":"const qtPts = (() => {\n const rand = d3.randomNormal(0, 3.3);\n return Array.from({length: 5000}, (d) => [rand(), rand()]);\n})();","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":773,"value":"const pqt = qtPts.reduce(\n (qt, [x, y]) => qt.insert({x, y}),\n new PointQuadtree({\n boundary: {\n x: 0,\n y: 0,\n halfWidth: 16,\n halfHeight: 16\n },\n capacity\n })\n);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"$36","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":464,"value":"_For 3d plot:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":466,"value":"import {plot3d} from \"observable:@jwolondon/3d-scatterplot\";","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":645,"value":"scatter.update((d) => (nearestTs.includes(d.t) ? \"firebrick\" : \"white\"));\ndisplay(md`_Updates point colour in response to sliders_`);","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"_For API doc and page styling:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":974,"value":"import {defaultStyle} from \"observable:@jwolondon/utilities-cdt-2026\";","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"import {apiStyle} from \"observable:@jwolondon/data-structure-docs\";","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":975,"value":"defaultStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"apiStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"2","titling":"auto"}} 2e:"$2d:body"