alexraven
@alexraven
веб-разработчик, специализация - wordpress

Как бы вы решили задачу по поиску в заданном радиусе?

В общем, задача слегка нетривиальная. Сайт на Вордпрессе. Пользователь указывает свой адрес, из которого мы получаем координаты Latitude, Longitude при помощи Geocoding API. На иллюстрации пользователь указан под индексом 0, зеленый маркер. Есть сервисы (например, стрижка газонов, выгул собак, чистка бассейнов, уборка и т.д), назовем их Services. И есть некие организации, предоставляющие эти сервисы. Причем одна организация может предоставлять одновременно несколько сервисов (например, стрижку газонов и выгул собак, а другая - чистку бассейнов и уборку). Назовем их Hubs.

А дальше мы ищем все Hubs, которые могут обслужить эти координаты. Services и Hubs у нас в базе данных как custom posts. У Hubs есть post meta с latitude, longitude. Задача в принципе, не сложная. Но она осложняется тем, что каждый Hub имеет собственный радиус, который он может обслужить. Например, 10, 20, 50 километров и так далее. Для каждого Hub может быть уникальным, как и его координаты. На иллюстрации радиус обслуживания показан цветными кругами.

Здесь видно, что пользователь 0 попадает в зону обслуживания Hub 1 и 2. Hub 3 находится примерно на таком же расстоянии от 0, как и 2. Но его радиус обслуживания меньше, поэтому его мы отфильтровываем из результатов. А дальше из Hubs, которые обслуживают данный адрес, мы выбираем ближайший к пользователю. В результате получается, что нам лучше всего подходит Hub 1, поскольку пользователь находится в его зоне обслуживания и он явно ближе, чем 2.

0cd711c47ed0445fbd9eac1c1551d0bb.png

В дальнейшем (пока не реализовано) алгоритм планируется апгрейдить. Например, радиус обслуживания сервиса 10 км, но они поедут и на 20 км, но за двойную цену.

Алгоритм работает. Вопрос в следующем. Можно ли как-то его упростить и сократить число итераций? Ведь если Hubs будут десятки тысяч, то итерации по всем из базы данных будут занимать время и нагружать сервер, даже с учетом кэширования. Кроме того, функция вызывается ajax'ом после того, как пользователь отметит очередной интересующий его сервис, то есть много раз для каждого пользователя.

function get_closest_hub($service_id, $latitude, $longitude)
{
    // получим все сервисы, которые есть в базе данных
    // поскольку хаб может предоставлять более одного сервиса, мы кэшируем все сервисы в $this->hubs, чтобы уменьшить количество запросов к базе данных. в теории это может вызвать переполнение памяти, то есть это костыль =)
    if (!is_array($this->hubs))
    {
        $hubs = get_posts([ 'post_type' => 'hubs', 'post_status' => 'publish', 'posts_per_page' => -1 ]);
        $this->hubs = $hubs;
    }
    else
    {
        $hubs = $this->hubs;
    }
    $selected = [];
    // возьмем все доступные хабы
    foreach ($hubs as $hub)
    {
        // координаты хаба у нас хитро закодированы в массиве
        $address = get_post_meta($hub->ID, 'hub_coords', true);
        $distance = $this->distance($address['lat'], $address['lng'], $latitude, $longitude);
        // а данные о предоставляемых сервисах - как сериализованный массив в post_content
        $data = unserialize($hub->post_content);
        $good = false;
        $radius = floatval(get_post_meta($hub->ID, 'hub_radius', true));
        $in_range = ($distance <= $radius);
        // если пользователь находится в зоне обслуживания и у хаба определен хоть один сервис
        if ($in_range && is_array($data))
        {
            foreach ($data['active'] as $key=>$value)
            {
                // данный хаб предоставляет сервис $service_id и пользователь находится в радиусе его обслуживания
                if ($key == $service_id && $value == '1')
                {
                    $good = true;
                }
            }
        }
        // если хаб предоставляет хотя бы один из выбранных пользователем сервисов
        if ($good)
        {
            // хаб нам подходит, сохраняем его в массиве
            $hub->distance = $distance;
            $selected[] = $hub;
        }
    }
    if (is_array($selected) && count($selected)>0)
    {
        // сортируем по расстоянию, от меньшего к большему
        usort($selected, [$this, 'distance_cmp']);
        reset($selected);
        // и выбираем первый, то есть ближайший
        $hub = current($selected);
        // получаем множитель цены, для каждого хаба он может быть свой, например: 1.25
        $hub->km_rate = floatval(get_post_meta($hub->ID, 'hub_rate', true));
        if ($hub->km_rate == 0)
        {
            // теоретически он никогда не должен быть равен нулю, но мало ли что...
            $hub->km_rate = 1;
        }
        return $hub;
    }
    // ни одного хаба не найдено
    return false;
}
// сравнение расстояний в двух объектах
function distance_cmp($a, $b)
{
    if ($a->distance == $b->distance)
    {
        return 0;
    }
    return ($a->distance < $b->distance) ? -1 : 1;
}
// Haversine formula
function distance($latitudeFrom, $longitudeFrom, $latitudeTo, $longitudeTo, $earthRadius = 6371)
{
    $latFrom = deg2rad($latitudeFrom);
    $lonFrom = deg2rad($longitudeFrom);
    $latTo = deg2rad($latitudeTo);
    $lonTo = deg2rad($longitudeTo);
    $latDelta = $latTo - $latFrom;
    $lonDelta = $lonTo - $lonFrom;
    $angle = 2 * asin(sqrt(pow(sin($latDelta / 2), 2) + cos($latFrom) * cos($latTo) * pow(sin($lonDelta / 2), 2)));
    return $angle * $earthRadius;
}


P. S. Я понимаю, что код получился совсем не оптимальным, но когда дедлайн был 2 недели назад и ты не спишь уже 30 часов, то по-другому не получается...
  • Вопрос задан
  • 401 просмотр
Пригласить эксперта
Ответы на вопрос 4
Rastishka
@Rastishka
Я бы сделал как то так:

Для ускорения выборки сначала ищем в БД по bounding box (тупо вхождение точки точки в квадрат каждого хаба).

Потом по найденным хабам вычисляем более точное расстояние. Если у вас масштаб - города (а не страны/континенты), можно не заморачиваться с "правильной" формулой, а использовать тупо расстояние между точками (школьная геометрия 5й класс). Но это спорная оптимизация.

Для сложных случаев, когда удаленность менее важна чем совпадение спектра услуг, я бы ввел коэфициенты-множители, считал релевантность для каждой точки, и выводил от самых релевантных к менее релевантным.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Задача: найти минимальное расстояние между координатами точки 0 и центром любого из хабов, где радиус больше или равен этому расстоянию.

Хранимая процедура (внутри БД):
входные параметры: M,N,inRange
задача процедуры: вывести начиная с M-го результата N-записей, с сортировкой по возрастанию расстояний хабов от точки 0, где радиусы хабов больше или равны (inRange=true) расстоянию между центром хаба и точкой 0.

Эту же процедуру можно потом использовать для тех хабов, которые не достаю до точки 0 своей областью действия просто установив параметр inRange в false.

Порядок действий:
-------------
1. Вначале, нужно отсортировать все хабы по расстояниям относительно точки 0.
2. Затем убрать те, где радиус стал меньше расстояния до точки 0 - т.е, недостающие зоной обслуживания. (сохраним индекс "отсечения хвоста" на случай, если не найдём)
3. Из оставшихся начиная сверху (самый ближний хаб к точке 0) - сделать поиск по любым критериям.

4. Если таких не окажется и недостающие по радиусу зоны (ПОСЛЕ индекса п.2) смогут расширить свой радиус за доп. деньги - то расширяем с учётом удалённости и доплаты, считая уже 2 параметра: присутствие точки 0 в зоне радиуса и стоимость доплаты. Останавливаемся когда будет достигнута нужная минимальная цена или пока не закончатся хабы (чтобы найти САМУЮ минимальную цену).
Ответ написан
freeExec
@freeExec
Участник OpenStreetMap
Воспользоваться геопространственной БД. Где запрос будет целиком в БД типа:
Отобрать все хабы с нужными типом и находящиеся в максимальном радиусе (те самые 50км, или реально найти MAX от всех хабов) от пользователя, причём используя индекс БД. Построить от найденных хабов буфер - их заданный радиус и отобрать те, в которые попал пользователь.
Т.е. два вложенные SELECT-a, а не портянка кода на php.
Ответ написан
alexraven
@alexraven Автор вопроса
веб-разработчик, специализация - wordpress
Оно как бы логично, есть только одна проблема. Проект на MySQL и я никогда не получу от клиента добро на переделку. Он попросту не согласится выделить на это деньги.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы