Geohash - что это и где он может пригодиться.
Давно хотел написать пост про Geohash. Несколько лет у меня лежат скрины к нему, но всё руки не доходили.
Не буду особо расписывать про него, это будет больше формата заметки пост.
Geohash - алгоритм для преобразования 2 координат вида 37.571309, 55.767190 (долгота, широта) в 1 строку. Как он работает - можно прочитать в Википедии. Также в инете полно библиотек на разных языках для преобразования координат в Geohash-формат и обратно.
А использовали мы в работе Geohash для того, чтобы показывать на карте заведения рядом. Допустим, у нас есть ресторан, известны его координаты. Задача - отобразить заведения, которые находятся рядом.
Что мы делали: преобразовывали координаты ресторана в геохэш, получали строку вида «ucftqbne6vww».
Соответственно, мы для каждого ресторана имели и координаты, и geohash. А соль вся в том, что у тех ресторанов, которые находятся рядом, геохэш частично совпадает. Например:
ucftqbne6vww
ucftqbne6vat
Чем точнее координаты (чем больше знаков после запятой), тем длиннее geohash. Чем большее количество символов для совпадения нам нужно, тем ближе от исходной точки мы ищем. Отсекая от конца геохэша символы, мы получаем некая прямоугольную площадь. Чем больше символов мы отсекаем, тем больше эта площадь. Прелесть в том, что если мы сравниваем 2 геохэша и есть совпадение нужного нам количества символов (нужная точность) - это значит, что оба ресторана попадают в эту прямоугольную площадь. Соответственно, можно считать, что они находятся рядом.
На скрине выше мы задали меньше точность (меньше символов для geohash) - получили такую площадь, что она даже в не влезает в экран.
А тут мы увеличили точность. Больше символов в Geohash - больше точность, меньше площадь/разброс.
В итоге у нас на AllCafe (ну, когда-то он был наш) результаты выборки ближайших заведений на карте выглядели так:
Вроде бы, это решение работает и по сей день. Поскольку у нас CouchDB - то там с помощью Map/Reduce 1 раз для всех ресторанов считался Geohash. Имея эту выборку, мы уже искали ближайшие заведения по заданной точности.
Очевидный минус такого решения - убираешь 1 символ - меняется шаг поиска. То есть задать произвольный размер площади для поиска нельзя. И шаги эти могут быть гигантскими.
Позже, для мобильной версии, мы уже стали использовать Bounding Box, чтобы показывать на телефонах только те заведения, которые входят в область карты, отображаемой сейчас на экране, без подгрузки лишних меток, которые могут не влезать на экран, а память жрать. Так что, варианты есть :)
Ну всё, минус один висяк :) Несколько лет не мог написать эту заметку, даже скрины - со времён, когда я ещё Ubuntu пользовался.
Кстати, для побаловаться есть сайт - http://geohash.org - вбиваешь координаты - он тебе выдаёт Geohash + ссылку. То есть ещё один вариант его использования - дать http-ссылку на конкретные координаты. Если интересно - побалуйтесь.