Есть массив точек со случайными координатами. Выбираем любую из них. Задача: найти ближайшую к ней точку в заданном направлении. Например, если речь идет о плоской карте, и надо найти ближайшую точку на востоке, мы фильтруем угол между северовостоком и юговостоком и ищем точку в нем, тупо сравнивая расстояния. Для трехмерного пространства все еще хуже. Особенно, если попытаться ввести систему ранжирования: если есть две точки, одна из них точно на восток, но на X дальше, а другая - на восток-северовосток под углом a, но чуть ближе, то будет выбрана та, для которой соблюдается определенное отношение X и a. Вопрос: как поступают умные люди в данной ситуации? это задача для базы(MYSQL) или PHP? Код писать не надо: как-нибудь справлюсь. Нужен алгоритм или волшебный пендель.
Ответ
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)
Комментариев нет:
Отправить комментарий