Quadtree - nearest neighbor
Clicking on the diagram places a yellow query point and a quadtree nearest-neighbor search identifies its closest orange base point, highlighted red. The d3.geom.quadtree recursively visits green rectangles, with color saturation indicating depth, while untested base points remain gray. Only orange points are measured for Euclidean distance, and the code uses d3.svg and SVG circles and rectangles to render the animated search process.
AI-generated descriptionThis example adapts mbostock's quadtree brushing demo to find the nearest neighbor (shown red) of a new point (shown yellow). Choose a new point to classify by clicking on the diagram. (An alternative approach for nearest neighbors of the mouse position is D3's Voronoi polygons, but the idea here would extend to rapidly classifying many new points against a base collection of points.)
We use a data-dependent order of recursion through the quadtree in order to quickly find a nearby point and then exclude many large rectangles without testing actual points. Green rectangles are visited, with saturation indicating depth in the quadtree. Only the orange points from the base collection are tested for Euclidean distance, other rectangles are excluded with a simple margin test.
I found it helpful to add extent and depth data to the quadtree nodes, maybe a useful general extension?
forked from <a href='http://bl.ocks.org/patricksurry/'>patricksurry</a>'s block: <a href='http://bl.ocks.org/patricksurry/6478178'>D3JS quadtree nearest neighbor algorithm</a>