module BTree.ts #

type BTreeNode #

export type BTreeNode = {
    depth: number;
    dataPoint: Point;
    screenPoint: NumericPoint;
    screenValue: number;
    originalIndex: number;
};

a node in the BTree k

• depth number How many branches down the tree is this leaf? 0 == tree root
• dataPoint Point value of this node in data-space
• screenPoint NumericPoint value of this node in screen-space
• screenValue number single axis value of screenPoint
• originalIndex number original position of this point in the source data

type BTree #

export type BTree = {
  node: BTreeNode;
  left: BTree | null;
  right: BTree | null;
};

A 1-dimensional binary tree, used to index data and screenspace points for fast querying

• node BTreeNode
• left BTree
• right BTree

type BTreeSearchResult #

export type BTreeSearchResult = {
  node: BTreeNode;
  screenDistanceSq: number;
};

A search result from a BTree, returns the tree node that is closest as well as the squared distance in screen-space

• node BTreeNode
• screenDistanceSq number

interface BTreeSorter #

export interface BTreeSorter {
  (a: BTreeNode, b: BTreeNode): number; 
}

Generic interface for sorting nodes in the BTree

• undefined undefined

function buildBTree #

(nodes: BTreeNode[], depth?: number, nodeSorter?: BTreeSorter) =>
BTree

Constructs a new BTree given an array of unsorted nodes. This function is recursive.

Parameters #

• nodes BTreeNode

  usually you'd map datapoints to this structure

• depth number

  current recursive depth to build. leave this at 0 unless you're doing something "interesting"

• nodeSorter BTreeSorter

  see sorter docs, a function for ranking nodes

Returns BTree #

function searchBTree #

(queryValue: number, index: BTree, maxDistance?: number, depth?:
number, bestMatch?: BTreeSearchResult) => BTreeSearchResult

Parameters #

• queryValue number
• index BTree
• maxDistance number
• depth number
• bestMatch BTreeSearchResult

Returns BTreeSearchResult #