Nearest neighbor search in D3

Question

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

Out of curiosity and nothing else, what are you using a JS K-D Tree for? — Sajjan Sarkar, Oct 04 '12 at 13:31
Cool! Would it be possible to share your code (unless of course it is proprietary or private),I think I could learn a lot from it. — Sajjan Sarkar, Oct 05 '12 at 19:30
@SajjanSarkar added link to the content of my question, enjoy! — Jacob Marble, Oct 07 '12 at 07:10

score 6 · Accepted Answer · answered Sep 07 '13 at 22:50

6

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

answered Sep 07 '13 at 22:50

patricksurry

5,508
2
27
38

Is nearest neighbour search is possible with latitude and longitude on leaflet.js maps? – gkuhu Nov 02 '18 at 23:07

Nearest neighbor search in D3

1 Answers1