PHP+MySQL: поиск по координатам

Ничего долгого, если у вас место по сути не ограничено. Создайте кэш для каждого объекта и не нужно каждый раз делать поиск.

А что кэшировать? distance-то от объекта до произвольной координаты изменяется..

Если действительно будет - тогда думать..

Если не критичны незначительные ошибки при сортировке, можно другой, менее ресурсоёмкой метрикой пользоваться.. (к примеру, |x1-x2|+|y1-y2|)

В свое время сталкивался с похожей задачей когда нужно было выводить обьекты недвижимости на Яндекс картах.

Определяли местоположение объекта

Зная точку вокруг которой нужно искать очень легко в пхп построчить верхний и нижний угол

дальше на основе этих данных строился SQL запрос

Запрос очень простой БАЗА была MySQL записей ~ 1M, но в выборке участвовали максимум 100 тыщ. Естественно latitude, longitude добавили в индекс, так как это числа то запрос довольно быстро отрабатывал и не создавал нагрузку.(тупо в лоб, без красивостей - но оно работало!!!!)

Самый геморрой начался когда выбиралась область а в ней от 5 до 30 тысяч объектов . А на карту одновременно мы выводили не более 500 объектов. Вариант когда тупо стоит LIMIT 0,500; отмели сразу. Задача стояла выводить рендомно каждый раз объекты для это области т.е чтобы не было такого что показываются одни и те же 500 последних. Пробовали order by RAND() LIMIT 0,500 -- запрос начал жрать кучу ресурсов и тормозить.

В итоге сделали костыльное решение во все записи добавили 10 новых полей RAND1, RAND….RAND10. Все эти поля заполнялись при вставке записи в базу каждое поле получало свое рендомное значение от 1 до 1000. А когда в пхп строился запрос на выборку то случайным образом выбиралось 1 поле из 10 по которому будут сортироваться этот раз записи. Решение конечно довольно колхозное – но стабильно работало. И когда единицей поиска был целый город разные люди при заходах получали разные наборы выборок.

Использую комбинированный вариант.

1) Выделение максимальных/минимальных координат на нужном расстоянии от заданной точки и фильтр всех точек, которые попадают в эту область.

2) Среди них уже расчет точного расстояния до начальной точки и сортировка по этому значению.

Проблем с производительностью замечено не было. У меня в этот прямоугольник обычно может попадать до 2к точек пока. Работающий пример

Для первого этапа граничные значения расчитываются вот так:

 $R = 6371;  // earth's radius, km

// first-cut bounding box (in degrees)

$max_latitude = $latitude + rad2deg($max_distance/$R);

$min_latitude = $latitude - rad2deg($max_distance/$R);

// compensate for degrees longitude getting smaller with increasing latitude

$max_longitude = $longitude + rad2deg($max_distance/$R/cos(deg2rad($latitude)));

$min_longitude = $longitude - rad2deg($max_distance/$R/cos(deg2rad($latitude)));

Дальше эти значения просто в WHERE добавляются в запрос. С использованием ORM у меня так, но думаю, смысл понятен:

$this->where('address.latitude', '>', $min_latitude)

	->where('address.latitude', '<', $max_latitude)

	->where('address.longitude', '>', $min_longitude)

	->where('address.longitude', '<', $max_longitude);

Использую встроенную процедуру для определения расстояния на втором этапе. По результату и делаю сортировку.

CREATE DEFINER=`root`@`%` FUNCTION `GetDistance`(`lat1` VARCHAR(120), `lon1` VARCHAR(120), `lat2` VARCHAR(120), `lon2` VARCHAR(120))

	RETURNS varchar(120) CHARSET latin1

	LANGUAGE SQL

	NOT DETERMINISTIC

	CONTAINS SQL

	SQL SECURITY DEFINER

	COMMENT ''

BEGIN

	DECLARE distance DECIMAL(12,8);

        select ((ACOS(SIN(lat1 * PI() / 180) * SIN(lat2 * PI() / 180) + COS(lat1 * PI() / 180) * COS(lat2 * PI() / 180) * COS((lon1 - lon2) * PI() / 180)) * 180 / PI()) * 60 * 1.1515 * 1.609344) into distance;

	RETURN distance;



END

Пример расчета расстояния от точки А с координатами lat1, lon1 до точки B c координатами lat2 : GetDistance(lat1,lon1,lat2,lon2);

Если что-то не понятно описал, обращайтесь, расскажу.