I have a 2D flat plane with points. Each point is stored in a database and has it's own x,y cordinates. Example: 2D plane is a 800px * 800px square.

   $points[0]['x'] = 100;
   $points[0]['y'] = 100;
   $points[1]['x'] = 120;
   $points[1]['y'] = 230;
   $points[2]['x'] = 240;
   $points[2]['y'] = 680;
   //More points here
   $points[52]['x'] = 700;
   $points[52]['y'] = 140;

I already have generated the distance of all points using Euclidean distance formula, but as points increases, so the number of calculations that must be done.

So I want at first to limit the number of calculations by searching "neighbor" points only. I can't find or to be more precise, I don't know how to search correctly my question.

What is the algorithm that I must use in order to search within a radius?

A picture with my problem https://i.stack.imgur.com/LONUi.png

Black point is the point from which I want to find the distance on red points within the radius. I am using PHP for this specific problem.

P.S. No coordinates, latitude/longitude.

CodePudding user response：

Lets say your radius is r. You can start by placing a square around your center whose side is length 2r. In other words, disregard points which are > ** /- r** on both axis.

You will be left with all the points within a circle of radius r centered around your point and some other points that are outside that circle but inside the square above. Then, you must iterate through every point and calculate euclidean distance to find which point is definitely inside the cirle.