block by armollica 64ffc3bd8fc76c5657719a842e39c4e3

K-D Tree Nearest Neighbor

Full Screen

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.

index.html

kd-tree.js