Parametric finding the nearest point in a given direction

There is an array of points with random coordinates.
Choose any of them.
Task: find the closest point to it in the given direction.
For example, if we are talking about a flat map, and we need to find the nearest point in the east, we filter the angle between northeast and southeast and look for a point in it, stupidly comparing distances. For three-dimensional space it is even worse. Especially if you try to introduce a ranking system: if there are two points, one of them is exactly east, but X further, and the other is east-northeast at an angle a, but a little closer, then the one for which a certain ratio is observed will be chosen X and a.


  1. What do smart people do in this situation?
  2. Is this a task for a database(MYSQL) or PHP?

You don’t need to write any code, I’ll manage somehow. We need an algorithm or a magic pendel.

Answer 1, authority 100%


select TOP 1 id
      my_range_fn( dir_x, dir_y, dir_z, x0, y0, z0, x, y, z ) as range
    from Points p
where range < 0
order by range desc

Ranking function example (JS):

//2D   JS
// - 2,  - 4,  - 6,  - 0
//     +- 45   
function my_range_fn( dir, x0, y0, x, y ){
  var dy = y - y0,
      dx = x - x0,
      rast = Math.sqrt( dx * dx + dy * dy ),
      my_dir = Math.PI * ( ( dy > 0 ) ? 1 : 0 ) - Math.acos( dx / rast ),
      my_dir = ( my_dir < 0 ) ? Math.PI * 2 + my_dir : my_dir,
      dir = Math.PI * dir / 4;
      delta = Math.abs( my_dir - dir );
  return ( ( delta < Math.PI/4 ) ? -1 : 1 ) * rast - 2 *delta;

Coefficient used. 2 by the difference between the desired direction and the received
Roughly means that with (x0, y0) = (0, 0)and direction Server will select (0,5)instead of (2,4)

Answer 2

You can also use MySQL. If we consider a variant of a flat grid of coordinates with a reference point in the center, then the northeast is the upper right square. That is, restrictions in the query for x > 0 and < 0, taking into account the reference point. Distance calculation using the Pythagorean theorem. Descending sort by distance. Limit 1 for withdrawal. The output is the nearest point in the given square.

Answer 3

First, let’s choose a coordinate system centered at the first point
The peculiarity of the problem is the presence of restrictions on the angle (|fi|<45), which suggests thoughts about the polar coordinate system and equations of the form r=R(cos(fi)-cos(pi/4)).

At the same time, the parameter of the equation suggests itself as an optimality criterion
R = r/(cos(fi)-sqrt(2)/2) = r^2/(x-r*sqrt(2)/2)
with the dimension of distance. And then the main thing remains – to correctly take into account the restrictions.