All examples By author By category About


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 the radius.

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.