All examples By author By category About

armollica

K-D Tree Nearest Neighbor

k-d tree nearest neighbor search (1-NN). The red dot is the nearest neighbor. Orange dots are scanned and not selected.

Compare to nearest neighbor search using quadtrees from this block. The k-d tree technique seems to scan more points, although the process of limiting the search set is different so this isn't really a direct measure of which is more efficient.

Here's a more up-to-date version of this block that works for k nearest neighbors.