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?

Argile

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.

Ashcroft

Good idea, got it. I will hardly have about 10 points within the bounding rectangle. So your method seems reasonable. Is using quadtree the fastest way of querying all the points within a bounding circle? – Argile

There are a variety of spatial data structures like quadtrees, including kd-trees and R trees. If you're specifically interested in "give me everything in this circle," a quadtree is definitely a good choice. If you want to ask questions like "give me the five closest points to some particular point in space," then a kd-tree is an excellent option. For what you've described, though, the quadtree should be perfect. – Ashcroft

Ok. I'm dealing with just circles. – Argile

I think the enclosing rectangle would have corners at +/- r*sqrt(2). And I am also wondering whether there is a more straightforward way of doing this - it definitely does not scale for geodesic lat/lon and for more points whereas bitmasks would do a much better job. Just can not find how to apply one. – Brecher

@Ashcroft Could you please explain second clause? How can I find points which are in rectangle? – Touchandgo