K-D Tree (C++)

Intro:

This code sample covers a generalized K-D Tree class I implemented for use in two audio plugins at Red Timbre Audio, both of which need efficient search of a spatial database of nodes.

Code Overview:

The K-D Tree implementation is general purpose using templatization, such that it can support any data type, provided that type can be interpreted spatially using the [] operator or with a custom functor class (KdNode line 30 and KdNodeDefaultGetAxis line 23).

The class builds the spatial tree when constructed (line 159) and does not support adding / removing elements after creation, as this was not necessary for my purposes.

The class supports nearest neighbor search (line 202) and nearest K search (line 259).

Both search functions support a randomness threshold distance within which distances are considered equal and broken with a random tiebreaker.

To improve this class, I would work to further generalize it, adding support for adding / removing nodes after creation and range search.

Code: