Выборка ближайших точек?

Question

[Explode]

Есть MySQL база данных со следующей таблицей:


CREATE TABLE IF NOT EXISTS `my_table` (

`id` int(11) unsigned NOT NULL AUTO_INCREMENT,

`name` text NOT NULL,

`longitude` double NOT NULL,

`latitude` double NOT NULL,

PRIMARY KEY (`id`)

) ENGINE=MyISAM DEFAULT CHARSET=utf8;


Необходимо составить запрос на выборку всех записей, которые находятся (по координатам longitude и latitude) в радиусе N метров от точки A (координаты которой известны).


P.S. До этого координаты хранил с помощью типа POINT, но после долгих поисков в интернете понял, что в MySQL очень урезаны возможности работы с этим типом, в отличие, к примеру, от PostgreSQL (PostGIS). Собственно по этому и пришлось перейти на хранение значений долготы и широты в разных полях.

Answer 1

[Ramzeska]

Используйте функции spatial движка mysql. dev.mysql.com/doc/refman/5.1/en/spatial-extensions.html
Там есть и специальные индексы и оптимизированный поиск по ним. Вам достаточно lat,lng поля превратить в одно поле типа GeoPoint и создать на нем spatial индекс. А далее дело техники сделать выборку в пределах квадрата по индексу и через having отрезать до окружности. Лучше поступать именно так, потому что там используется специальный для этого индекс. Не знаю что там у вас урезано, но мы проверяли быстродействие при поиске по двум полям и по point полю, так последний показал в разы большую производительность.

Comments

[Explode]

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

[Explode]

При создании индекса
ALTER TABLE `my_table` ADD SPATIAL INDEX ( `coordinates` ) ;
выдает ошибку
Cannot get geometry object from data you send to the GEOMETRY field

[Explode]

А все, с индексом разобрался — некоторые записи в таблице имели «пустые» поля coordinates.
Теперь бы разобраться с запросом. Выборка в пределах квадрата, как я понимаю, делается так, верно?
SELECT * FROM `my_table` WHERE MBRWithin(`coordinates`, GeomFromText('Polygon((50.456736 30.510540, 50.455690 30.510540, 50.455690 30.513295, 50.456736 30.513295))')) = 1;
А как теперь все это обрезать до окружности? И здесь же нужно знать координаты углов квадрата, а у нас известны только координаты точки, в радиусе которой необходимо произвести поиск, ну и собственно сам радиус.

[Ramzeska]

Выборка в пределах квадрата у вас не верная, полигон нужно замкнуть на первую точку иначе не заработает функция.
Дело в том, что расстояние разное в разных частях света, но я честно говоря уже не помню как это считается, но можно сделать иначе. Допустим есть координаты человека $q=array(55,44); Тогда что бы узнать длину одного градуса долготы на его широте, проверяем функцией расстояние:

$kmInDeg  = LatLngDist($q,array($q[0],$q[1]+1));

Теперь количество градусов в 1 км:

$degInKm = 1 / $kmInDeg;

Ну и для получения сторон квадрата:

$r = 3; // radius = 3km
$rdeg = $r * $degInKm;
$sq[0] = array($p[0]-$rdeg,$p[1]+$rdeg); // левый верхний
$sq[1] = array($p[0]+$rdeg,$p[1]+$rdeg); // правый верхний
$sq[2] = array($p[0]+$rdeg,$p[1]-$rdeg); // правый нижний
$sq[3] = array($p[0]-$rdeg,$p[1]-$rdeg); // левый нижний
$sq[4] = $sq[0]; // замыкаем полигон

[Ramzeska]

Ну и что бы срезать до окружности дописываете в HAVING обычную теорему пифагора, только уже учитывая нужное количество градусов:

SELECT * FROM `my_table`
WHERE MBRWithin(`coordinates`, GeomFromText('Polygon(($sq[0][0] $sq[0][1], $sq[1][0] $sq[1][1],$sq[2][0] $sq[2][1], $sq[3][0] $sq[3][1], $sq[4][0] $sq[4][1]))'))
HAVING X(coordinates)*X(coordinates) + Y(coordinates)*Y(coordinates) <= $rdeg*$rdeg

[Ramzeska]

Хотя вот, более точная функция для определения расстояния:

$lat = $q[0]; $lng = $q[1]; $r = 3; // km
SELECT ...
HAVING ( 6371 * acos( cos( radians('.floatval($lat).') ) * cos( radians( X(p.coord) ) ) * cos( radians( Y(coord) ) - radians('.floatval($lng).') ) + sin( radians('.floatval($lat).') ) * sin( radians( X(p.coord) ) ) ) ) < $r

[Explode]

Спасибо, то что надо! А можно как нибудь отсортировать результаты по расстоянию от точки q прямо в теле запроса?

[Ramzeska]

SELECT *, ( 6371 * acos( cos( radians('.floatval($lat).') ) * cos( radians( X(p.coord) ) ) * cos( radians( Y(coord) ) - radians('.floatval($lng).') ) + sin( radians('.floatval($lat).') ) * sin( radians( X(p.coord) ) ) ) ) as distance
FROM `my_table`
WHERE MBRWithin(`coordinates`, GeomFromText('Polygon(($sq[0][0] $sq[0][1], $sq[1][0] $sq[1][1],$sq[2][0] $sq[2][1], $sq[3][0] $sq[3][1], $sq[4][0] $sq[4][1]))'))
HAVING distance <= $rdeg*$rdeg
ORDER BY distance

[Explode]

Благодарю! Теперь вопрос полностью решен!

[NightGhost]

Спасибо! Сделал реализацию на своем сайте — работает отлично.
А реально тоже самое сделать в квадрате?

[Артем]

NightGhost, подскажи пожалуйста как!?

[Артем]

Explode, подскажи пожалуйста как!?

[Артем]

Ramzeska, подскажи пожалуйста, ругается на p.coord

Answer 2

[Ramzeska]

Ну а если вас интересует функция, переводящая две координаты в расстояние между ними, с радостью поделюсь кусочком:

<?php
    private function LatLngDist($p, $q) {
        $R = 6371; // Earth radius in km

        $dLat = (($q[0] - $p[0]) * pi() / 180);
        $dLon = (($q[1] - $p[1]) * pi() / 180);
        $a = sin($dLat / 2) * sin($dLat / 2) +
                cos($p[0] * pi() / 180) * cos($q[0] * pi() / 180) *
                sin($dLon / 2) * sin($dLon / 2);
        $c = 2 * atan2(sqrt($a), sqrt(1 - $a));

        return $R * $c;
    }

Answer 3

[Андрей Буров]

Если не учитывать то, что это координаты на поверхности геоида, а считать координатами на плоскости, то подойдет теорема Пифагора.

В прямоугольном треугольнике квадрат длины гипотенузы равен сумме квадратов длин катетов.

SQRT(POW(latitude-latitudeA,2)+POW(longitude-longitudeA,2))<N

Comments

[Explode]

но здесь же используются координаты, а сравнивать нужно с метрами

[Андрей Буров]

А что мешает перевести градусы в метры умножив на какой-то коэффицент?

PS: это всё годится только для небольших расстояний, где можно пренебречь формой планеты и считать её плоской.

[Explode]

Да, необходимо это как раз для небольших расстояний (максимум 50 метров).
А вот на счет перевода, что за коэффициент?

[Explode]

Извиняюсь, ступил. Это радиус Земли.

[Андрей Буров]

Широта от -90 до 90, долгота от -180 до 180
значит нужно умножить штроту на 2, длина экватора 40075 км.
получается коэффициент будет 40075/360 = 111.3194444 км. = 111319.4444 м.
а конечная формула
SQRT(POW(latitude*2-latitudeA*2,2)+POW(longitude-longitudeA,2))<N *111319.4444

вроде всё верно…

[Ramzeska]

Кстати, раз уж на то пошло, то не забывайте, что если впишите такую формулу в Where, то можете забыть про индексы

Answer 4

[tribesman]

Вывод точек с сортировкой - "сначала те, которые ближе к точке по адресу Москва, ул Народного Ополчения."
SELECT *,
(ABS(lon-37.48488200)+ABS(lat-55.78553900)) as crd
FROM `pvz`
#WHERE `ds_full_addr` LIKE '%Народного%'
ORDER BY `crd` ASC

Answer 5

[sl_bug]

zcentric.com/2010/03/11/calculate-distance-in-mysql-with-latitude-and-longitude/

Comments

[sl_bug]

в целом — вот

Answer 6

[m08pvv]

Если точек много и хранятся так, то можно попробовать разбить на квадраты и по координатам сначала получать квадрат и его соседей, а затем перебирать только их, ну и считать можно квадрат расстояния (корень всё-таки долго извлекать, а обойтись можно и без этого)

Answer 7

[Vampiro]

Я делал выборку квадрата со стороной в 2 радиуса запросом, а более точно для каждой точки считал расстояния в серверной части приложения. Так проще масштабировать и будут индексы задействованы.

Answer 8

[Gasoid]

мой подобный вопрос: habrahabr.ru/qa/23016/

По оптимизации поиска по вхождению точки в квадрат для Mysql
www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Answer 9

[GabrielViolet]

MySQL форум, надеюсь поможет