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.

Question:

- What do smart people do in this situation?
- 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%

SQL:

```
select TOP 1 id
from
(
select
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.