Old school D3 from simpler times
Fixed-Radius Near Neighbors
Fixed-radius near neighbors
search from a set of 2D points. Uses a quadtree to accelerate the search. If
a quadtree square is entirely outside the specified radius then none of the
square's contained points is in the radius. This lets you significantly narrow
down the set of points that need to be scanned. Orange dots are scanned points
found to be outside the radius. Red dots are scanned points found to be inside
To test the efficiency of this method I did 100 searches on a set of 1 million
random points layed out like above. Each search was done at a random point
with a radius of 25. On average the brute force search method took 460
milliseconds to identify all points in the radius. Doing the exact same
searches with the quadtree method took only 1.44 milliseconds on average.
This method is based on this example
that uses a similar method for identifying points within a rectangle.