Клуб API Карт

Быстрый поиск в БД ближайших меток

dima-besh
24 ноября 2011, 10:11

Здравствуйте!

Почему-то нигде не смог найти обсуждение этого, как мне кажется, первоочередного вопроса.

Пусть в БД хранится, скажем, 1000 меток. Как быстро выбрать ближайшие, чтобы отобразить их на том участке карты который смотрит пользователь?

 

Единственное что нашел: считать расстояние между центром карты и каждой(!) хранящейся точкой:

SELECT address, name, lat, lng, ( 6371 * acos( cos( radians('%s') ) * cos( radians( lat ) ) 
* cos( radians( lng ) - radians('%s') ) + sin( radians('%s') ) * sin( radians( lat ) ) ) ) AS distance
FROM markers HAVING distance < '%s' ORDER BY distance LIMIT 0, 20

Или надо капать в сторону кластеризации? Как правильно?

 

5 комментариев
Подписаться на комментарии к посту

Существуют специальные SPATIAL расширения баз данных, например, PostGIS для PostgreSQL. Попробуйте посмотреть в эту сторону.

 

Королев Михаил
24 ноября 2011, 16:12

Если не нужна большая точность а именно выбрать top 10..20..100 ближайших - имхо можно вообще не считать расстояния а использовать простую разницу координат, полагая что она пропорциональна расстоянию. единственное что придётся предусмотреть - переход через 0.

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

Во первых в Posgress, MySQL и даже в Oracle есть тип данных spatial.

В общем случае это некая метафизический формат данных которых хранит сущьности определенные в 2д пространстве.

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

Если у вас 1000 точек и есть интерес к красивому и правильному програмингу - поиск в помощь.

Если точек или больше, или меньше, или вас немного не устраивает что spatial во всех базах ЖУТКО тормозит :)

То давайте работать по старинке.

вариант 1. Записываем в базу lat и lng

Выбор из базы - SELECT ... WHERE lat between y1 and y2 and lng between x1 and x2

Где эти x1-y2 есть bounds видимого куска карты.

И надо будет не забыть повесить двойной индекс на эти два поля.

Работает изумительно для относительно больших обьемов данных( десятки тысяч записей )

Минус - обновление с сервера при каждом драге карты.

Тут можно решить либо через расширение тех bounds что отдаются на сервер, а потом не делать обновления пока не вышли из зоны "расширения".

Либо, лучше, как-то фиксировать зоны запросов. Чтобы всегда запрашивались дискретные куски. Примерно так как на карте тайлы.

Об остальном можно пояндексить интернеты, например хабрахабр.

Что то запрос не срабатывает подозреваю нужно конвертировать даные?

 

SELECT* frommap_cord WHERE cord_lat between 76.718215942382and 77.27096557617 and cord_lon between 43.339123639687 and 43.18330624940;