Using a QuadTree to get all points within a bounding circle

Question

I have a set of 100 to 200 points (x,y). I have to check which ones fall within a particular distance of the others. The particular distance is fixed for the entire program, say 50. Say point 1 falls within the range of points 5,7,25,90,96,105...etc. Similarly point 2 falls within range of 23,45, etc... Storing objects for locating by x,y coordinates

Here QuadTree is suggested, but it can be used to get all the points within a bounding rectangle. But how to get all points within a bounding circle? there is a method which returns a point closest to a lat/long within a maximum distance, but how to get all the points within the distance? http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int)

one way maybe to remove each point from the tree as I get it, then query for the closest point again, until i get null. is that the only way?

Answer 1

Suppose that you have a circle centered at (x, y) with radius r and want to find all points in a quadtree that are in the circle. One idea is as follows:

1. Construct the bounding box inscribing the circle. This is the smallest rectangle containing the circle, which has upper-left corner (x - r, y - r) and lower-right corner (x + r, y + r). Any point in the circle must also be in the square, but not the other way around.

2. Query the quadtree for the set of points lying in that rectangle. Let these points be P.

3. For each point in P which is known to be in the rectangle, see if it is also in the circle. You can do this by checking whether the distance from that point to (x, y) is no greater than r. In other words, given a point (x₀, y₀), you would compute (x - x₀)² + (y - y₀)², and if this value is less than or equal to r², then the point is contained in the circle.

Although this may seem inefficient, it's actually quite fast. The ratio of the area of the square to the area of the circle is 4 / π ≈ 1.27. In other words, assuming that your points are distributed somewhat evenly, you'll only find about 27% more points than you need to.