Finding all points in certain radius of another point

Question

I am making a simple game and stumbled upon this problem. Assume several points in 2D space. What I want is to make points close to each other interact in some way.

Let me throw a picture here for better understanding of the problem:

Now, the problem isn't about computing the distance. I know how to do that.

At first I had around 10 points and I could simply check every combination, but as you can already assume, this is extremely inefficient with increasing number of points. What if I had a million of points in total, but all of them would be very distant to each other?

I'm trying to find a suitable data structure or a way to look at this problem, so every point can only mind their surrounding and not whole space. Are there any known algorithms for this? I don't exactly know how to name this problem so I can google exactly what I want.

If you don't know of such known algorighm, all ideas are very welcome.

Answer 1

You're still going to have to iterate through every point, but there are two optimizations you can perform:

1) You can eliminate obvious points by checking if x1 < radius and if y1 < radius (like Brent already mentioned in another answer).

2) Instead of calculating the distance, you can calculate the square of the distance and compare it to the square of the allowed radius. This saves you from performing expensive square root calculations.

This is probably the best performance you're gonna get.