Instantly share code, notes, and snippets.

Last active August 14, 2024 02:55
Show Gist options
• Save patricksurry/6478178 to your computer and use it in GitHub Desktop.

This 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?

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

### llb4ll commented Jan 29, 2014

This extension is great!
I was originally looking for an efficient way to implement a k-nearest-neighbor search. I've implemented a simple version of it here: http://bl.ocks.org/llb4ll/8709363 (https://gist.github.com/llb4ll/8709363).

### clankill3r commented Dec 30, 2017

@llb4ll

A small and easy way to improve your code.
You have this:

``````function euclidDistance(ax, ay, bx, by){
return Math.sqrt(Math.pow(ax-bx, 2) + Math.pow(ay-by, 2));
}
``````

`sqrt` is an expensive operation.

You could make another function named `euclidDistanceSq`:

``````function euclidDistanceSq(ax, ay, bx, by){
return Math.pow(ax-bx, 2) + Math.pow(ay-by, 2);
}
``````

And use that instead, keep in mind you might have to square other distances as well!
If it doesn't work you forgot to square some value!