Страницы

Поиск по вопросам

суббота, 6 июля 2019 г.

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

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

Комментариев нет:

Отправить комментарий