Algorithm to find all points on a 2D grid some dis

Question

I have some point on a 2D grid (x, y) and I need to find all points that are n distance away from that point. The way I'm measuring distance is by using the distance formula between the two points. Anyone know how to do this?

Edit: Just for reference, what I'm trying to do is to write some AI path finding that will maintain some distance away from a target in a system that uses grid based locations. Currently I'm using A* path finding, but I'm not sure if that matters or makes a difference since I'm kind of new to this stuff.

Answer 1

This problem is known as range query. The brute force solution is just as you described: computed the distance of all points from the reference point and return those whose distance is less than the desired range value.

The brute force algorithm is O(N^2). There are, however, more efficient algorithms that employ spatial indexes to reduce algorithm complexity and the number of distance calculations. For example, you can use a R-Tree to index your points.

Answer 2

Java implementation:

public static Set<Point> findNearbyPoints(Set<Point> pts, Point centerPt, double radius) {
    Set<Point> nearbyPtsSet = new HashSet<Point>();
    double innerBound = radius * (Math.sqrt(2.0) / 2.0);
    double radiusSq = radius * radius;
    for (Point pt : pts) {
        double xDist = Math.abs(centerPt.x - pt.x);
        double yDist = Math.abs(centerPt.y - pt.y);
        if (xDist > radius || yDist > radius)
            continue;
        if (xDist > innerBound || yDist > innerBound)
            continue;
        if (distSq(centerPt, pt) < radiusSq)
            nearbyPtsSet.add(pt);
    }
    return nearbyPtsSet;
}

Answer 3

Its called nearest neighbor search. More at http://en.wikipedia.org/wiki/Nearest_neighbor_search

There are open libraries for that. I have used one written for C and recommend it: http://www.cs.umd.edu/~mount/ANN/. ANN stands for Approximate Nearest Neighbor, however, you can turn the approximation off and find the exact nearest neighbors.

Answer 4

This wouldn't use the distance formula, but if you're looking for points exactly n distance away, perhaps you could use sin/cos?

In pseudocode:

for degrees in range(360):
    x = cos(degrees) * n
    y = sin(degrees) * n
    print x, y

That would print every point n away in 360 degree increments.

Answer 5

Here's what I would do:

1. First filter out all points that are further than D on either x or y. These are certainly outside the circle of radius D. This is a much simpler computation, and it can quickly eliminate a lot of work. This is a outer bounding-box optimization.

2. You can also use an inner bounding-box optimization. If the points are closer than D * sqrt(2)/2 on either x or y, then they're certainly within the circle of radius D. This is also cheaper than calculating the distance formula.

3. Then you have a smaller number of candidate points that may be within the circle of radius D. For these, use the distance formula. Remember that if D = sqrt(Δx²+Δy²), then D² = Δx²+Δy².
   So you can skip the cost of calculating square root.

---

So in pseudocode, you could do the following:

for each point
begin
    if test 1 indicates the point is outside the outer bounding box, 
    then skip this point

    if test 2 indicates the point is inside the inner bounding box, 
    then keep this point

    if test 3 indicates the point is inside the radius of the circle, 
    then keep this point
end