Параметрическое нахождение ближайшей точки в заданном направлении

#алгоритм #php #mysql

                    
Есть массив точек со случайными координатами.
Выбираем любую из них.
Задача: найти ближайшую к ней точку в заданном направлении.
Например, если речь идет о плоской карте, и надо найти ближайшую точку на востоке,
мы фильтруем угол между северовостоком и юговостоком и ищем точку в нем, тупо сравнивая
расстояния. Для трехмерного пространства все еще хуже. Особенно, если попытаться ввести
систему ранжирования: если есть две точки, одна из них точно на восток, но на X дальше,
а другая - на восток-северовосток под углом a, но чуть ближе, то будет выбрана та,
для которой соблюдается определенное отношение X и a.

Вопрос: 


как поступают умные люди в данной ситуации?

это задача для базы(MYSQL) или PHP?


Код писать не надо: как-нибудь справлюсь. Нужен алгоритм или волшебный пендель.    

Ответы

Ответ 1

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

Пример ранжирующей функции ( 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;
}

Используется коэф. 2 на разность желаемого направления и полученного
Примерно означает что при (x0, y0) = (0, 0) и направлении Сервер, выберет (0,5) вместо
(2,4)


Ответ 2

Можно и с помощью MySQL. Если рассматривать вариант плоской сетки координат с точкой
отсчета в центре, то северо-восток - это верхний правый квадрат. То-есть ограничения
в запросе по х > 0 и у < 0 с учетом точки отсчета. Расчет расстояния по теореме Пифагора.
Убывающая сортировка по расстоянию. Лимит 1 на вывод. На выходе ближайшая точка в заданном
квадрате.


Ответ 3

Для начала выберем систему координат с центром в первой точке
Особенность задачи - в наличии ограничений на угол (|fi|<45), что наталкивает на
мысли о полярной системе координат и уравнениях вида r=R(cos(fi)-cos(pi/4)).

При этом в качестве критерия оптимальности напрашивается параметр уравнения
R = r/(cos(fi)-sqrt(2)/2) = r^2/(x-r*sqrt(2)/2)
с размерностью расстояния. И тогда останется главное - правильно учесть ограничения.