Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Nearest neighbor search in D3

I have implemented a 2-dimensional k-d tree in Javascript (check it out on GitHub), and I am using it for nearest-neighbor searches alongside D3.

I learned that there is a quadtree implementation in D3, but also discovered that the API documentation is sparse and Google searches are not fruitful. I would rather use a well-traveled library than my own reinvented wheel when possible.

How do you perform a nearest neighbor search using D3's quadtree? By nearest neighbor, I mean:

  • Populate the quadtree with 2-dimensional points
  • Search for the quadtree-contained point closest to a new point that does not necessarily exist in the quadtree
like image 402
Jacob Marble Avatar asked Sep 25 '12 04:09

Jacob Marble


Video Answer


1 Answers

The brushing demo doesn't actually find the nearest neighbor, but rather finds quadtree points contained in a given rectangle. (Try brushing an empty rectangle and it doesn't necessarily visit its nearest neighbors.)

I forked an example that efficiently finds the nearest neighbor in the quadtree to an arbitrary point - see http://bl.ocks.org/patricksurry/6478178

like image 72
patricksurry Avatar answered Sep 30 '22 16:09

patricksurry