Come work in Estonia – the most advanced digital society. Many Ukrainians already know that Estonia is affordable – become one of them and check out the jobs available!
×Закрыть

Серверная кластеризация гео-объектов на карте на основе Geohash

Когда слишком много гео-объектов (точек, маркеров, меток) расположены рядом на карте, они сливаются в одно большое, едва различимое пятно. При большом количестве гео-объектов координаты и другие данные занимают много памяти, а для отображения карты потребляется много ресурсов устройства, что может привести к частому зависанию приложения.

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

Кластеризация может значительно увеличить производительность при отображении большого числа гео-объектов.

Много JavaScript библиотек для интерактивных карт предоставляют возможность кластеризации гео-объектов на стороне клиента. При кластеризации на стороне клиента с сервера получаются отдельные точки, которые затем обрабатываются в браузере или мобильном приложении для объединения в кластер. Это делает размер ответа сервера огромным, занимая время и память на стороне клиента. Ели используется кластеризация на стороне сервера, размер ответа сервера значительно меньше — данные о нескольких кластерах вместо тысяч отдельных точек. Это быстрее и потребляет намного меньше памяти на стороне клиента.

Рассмотрим как реализовать серверную кластеризацию гео-объектов на карте на основе системы геокодирования Geohash.

Что такое Geohash

Geohash — это алфавитно-цифровая строка, представляющая географические координаты, широту и долготу. Данная система геокодирования разработана Gustavo Niemeyer, создателем geohash.org.

Например, точка с широтой 50.450101 и долготой 30.523401 представлена Geohash строкой u8vxn84mnu3q. Короткий URL geohash.org/u8vxn84mnu3q может использоваться для определения местоположения.

Количество символов в Geohash напрямую связано с точностью координат. Если убрать символы с конца Geohash строки, чтоб уменьшить ее длину, некоторая точность координат будет потеряна. Например, Geohash u8vxn84mnu расшифровывается в координаты 50.45010 и 30.5234, а Geohash u8vxn8 - в 50.45 и 30.5.

Точке на расстоянии 50 км, такой как 50.348751 и 30.90151, соответствует Geohash u8vyrjty9r7y. Как видите, Geohash строки имеют общий префикс u8v.

Это позволяет нам с легкостью искать объекты, расположенные поблизости. Например, используя SQL:

SELECT * FROM GEO_POINT WHERE GEOHASH LIKE 'u8v%'

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

Принцип работы алгоритма

Как работает алгоритм геокодирования Geohash? Сначала весь мир делится пополам вертикально. Левой половине присваивается бинарное значение 0, а правой — значение 1. Если точка, координаты которой кодируются, попадает в правую половину, мы добавляем 1 к бинарному значению Geohash:

Далее, алгоритм геокодирования Geohash делит карту горизонтально на 2 половины и присваивает бинарное значение 1 верхней половине, а нижней — 0. Точка, координаты которой мы кодируем в Geohash, расположена в верхней половине, поэтому мы добавляем 1 к бинарному значению Geohash. На данном этапе бинарное значение Geohash нашей точки — 11:

Мы продолжаем делить ячейки на половины вертикально и горизонтально, каждый раз добавляя к бинарному значению Geohash 0 или 1. Каждый раз, когда мы добавляем бит к бинарному значению Geohash, точность повышается:



Бинарное значение Geohash необходимо перевести в строку, кодированную в Base 32. Каждые 5 бит преобразуются в символ, используя таблицу символов:

Десятичная система012345678910111213141516
Base 320123456789bcdefgh
Десятичная система171819202122232425262728293031
Base 32jkmnpqrstuvwxyz

Geohash разбивает карту мира на ячейки, каждая из которых представляет один кластер. Длина префикса Geohash строки напрямую связана со степенью приближения (zoom). Для лучшей визуализации, среднее арифметическое значение всех координат в ячейке будет местом размещения иконки кластера — вместо размещения иконки в центре ячейки. Предположим, географические координаты хранятся в таблице GEO_POINT:

CREATE TABLE GEO_POINT (
  GEO_POINT_ID SERIAL PRIMARY KEY,
  LATITUDE_DEG FLOAT8 NOT NULL,
  LONGITUDE_DEG FLOAT8 NOT NULL,
  GEOHASH VARCHAR(12) NOT NULL,
  COUNTRY_CODE VARCHAR(2)
);

CREATE INDEX I_GEO_POI_LAT_LON ON GEO_POINT (LATITUDE_DEG, LONGITUDE_DEG);
CREATE INDEX I_GEO_POI_GEOHASH ON GEO_POINT (GEOHASH);

Чтобы сформировать кластеры из видимых в текущей области просмотра (viewport) точек, может использоваться следующий SQL запрос:

SELECT AVG(GP.LATITUDE_DEG) AS LATITUDE_DEG,
          AVG(GP.LONGITUDE_DEG) AS LONGITUDE_DEG,
          COUNT(*) AS QUANTITY,
          SUBSTRING(GP.GEOHASH FROM 1 FOR :precision) AS GEOHASH_PREFIX,
          GP.COUNTRY_CODE AS COUNTRY_CODE
     FROM GEO_POINT GP
    WHERE GP.LATITUDE_DEG BETWEEN :south_west_lat AND :north_east_lat
      AND GP.LONGITUDE_DEG BETWEEN :south_west_lon AND :north_east_lon
 GROUP BY GEOHASH_PREFIX,
          COUNTRY_CODE

south_west_lat/south_west_lon — широта/долгота нижней левой вершины ограничительного прямоугольника области просмотра (viewport);

north_east_lat/north_east_lon — широта/долгота верхней правой вершины ограничительного прямоугольника области просмотра (viewport);

precision — так как количество символов в Geohash коде напрямую связано с размером кластера, значение данного параметра зависит от расстояния между нижней левой и верхней правой вершиной (диагональ ограничительного прямоугольника области просмотра).

Этот запрос вернет координаты размещения иконки кластера и количество объектов в каждом кластере. Гео-объекты группируются в кластеры по Geohash префиксу и стране. Гео-объекты, которые расположены рядом, но в разных странах, не будут объединены в один кластер, даже имея одинаковый Geohash префикс. Для этого колонка COUNTRY_CODE была добавлена в GROUP BY.

Определяем параметры

Когда мы приближаем (zoom in) и отдаляем (zoom out) карту, Geohash изменяется соответственно. Длина Geohash префикса зависит от степени приближения. Определим связь длинны Geohash префикса и степени приближения как функцию y=f(x). Это скорее экспоненциальная функция (y = ae^(bx)), а не линейная (y = kx + b):

И степень приближения, и длина Geohash префикса имеют минимальное и максимальное значение. Когда степень приближения минимальная, длина Geohash префикса тоже минимальная. То же самое и с максимальными значениями.

Решим систему уравнений, чтобы получить значения параметров a и b.

x — степень приближения (zoom),
y — длина префикса Geohash,
gmin, gmax — минимальная и максимальная длина Geohash префикса,
zmin, zmax — минимальная и максимальная степень приближения.





Когда значения параметров a и b известны, функция может быть записана. Так как длина Geohash префикса имеет нижний и верхний предел, функция y=f(x) будет выглядеть следующим образом:


Что получается в итоге

В примере я использую следующие значения: gmin = 1, gmax = 12, zmin = 0, zmax = 17:




Кластеризация подходит для любого проекта, отображающего на карте большое количество гео-объектов, которые сливаются в едва различимое пятно из-за большого количества. Серверная кластеризация на основе Geohash повышает производительность, значительно снижая размер ответа сервера, заменяя несколькими кластерами потенциально тысячи точек.


P.S. Интерактивный пример доступен тут, исходный код примера — тут.

24 комментария

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

Спасибо, очень полезная статья! Пришелся к празднику — горшок, а хвост — ко дню рождения! ©

Дякую, стаття корисна та інформативна. Але не вистачає кількісних характеристик (хто пам’ятає анекдот :-). Наприклад, починаючи з якої кількості об’єктів потрібно робити кластеризацію на сервері? З особистого досвіду: до 10 тис точок по Україні, і openlayers 3 справляється на ура.
І якби інтерактивний приклад містив два варіанти (серверний/клієнтський кластер, в ідеалі — якби ще й з можливістю вказувати кількість рандомно згенерованих об’єктів), то був би жирний плюс в карму.
Ну і якщо вже говорити про перспективу, то звичайним sql вже нікого не здивуєш. А от якби згадали в статті, що в редісі порівняно недавно з’явилися spatial data (geohash, доречі, там теж є), і якщо зробити серверну кластеризацію гео-об’єктів на редісі, то взагалі було б добре.

При x=1 нужно делать ексепшн, а так = Гугл уже укрупняет.

Гугл, якраз на клієнті укрупняє)

Я гуманитарий, поэтому прокомментирую с точки зрения юзабилити:
1. Надо делать кластеры кликабельными, чтобы клик выставлял зум по самым удаленным точкам в кластере.
2. Нужно хорошее юзабилити и перфоманс-тестирование чтобы определить минимальную зону кластеризации. Иначе слишком часто кластер визуально на одном месте, а точки в нем по факту сильно разнесены. Это, например, моя боль в использовании ПриватКарты — там очень большая площадь кластеризации и жутко неудобно искать банкоматы на экране телефона

О, еще подумалось ко второму — минимальная площадь кастеризации должна зависеть от ширины экрана. На мобилках — поплотнее, на десктопах — пошире.

GeoHash работает на принципах KD-дерева/R-дерева или как-то иначе?

наскільки я розумію це просто адаптований до координат K-medians алгоритм. K-medians не дуже. Якщо буде для прикладу країна-анклав то кластер зовнішньої країни поглине точки внутрішньої. DBSCAN як на мене більш доречний до такої задачі
П.С Алгоритмів кластеризації багато, чого нема порівняня з найбільш популярними?

П.С. Гадаю, у автора немає порівнняння з тієї ж причини, з якої воно відсутнє у вашому коментарі ;)

Астрологи объявили месяц украинского хабра, кол-во интересных статей на доу увеличилось вдвое.

Все лучше, чем про гейпарады и про очередных властелинов сыра

Надеюсь они объявят и «год украинского хабра», так как последнее время уж очень много бреда пишут.

Неоптимальность — очень размытая характеристика. Неоптимален по какому критерию? Статья по ссылке делает акцент на том, что две точки расположенные рядом, но, например, по разные стороны от экватора будут иметь разный Geohash. Это не приведет к потере точек на карте, так как мы явно указываем координаты юго-западной и северо-восточной вершины ограничительного прямоугольника viewport-а при выборке точек для кластеризации. Просто, вместо одного кластера, будет 2. При этом, если точек в каждой из этих ячеек Geohash сетки больше 1, иконка кластера будет размещена по среднему арифметическогому их координат. Простыми словами, иконки кластеров не будут накладываться друг на друга и будут выглядеть эстетично.

чому ж не використати

DBSCAN
?

Статья о том, как реализовать кластеризацию гео-данных на стороне сервера используя Geohash. Я описал именно этот подход, так как, на мой взгляд, он является простым и элегантным. Я не знаю преимущества и недостатки DBSCAN алгоритма и сложность реализации кластеризации с использованием этого алгоритма, но с удовольствием почитаю, если кто-то опишет.

як на мене недолік в залежності від початкового розбиття в Geohash, як приклад випадок з екватором. також цікаво що буде у випадку анклавів чи спедифічних форм країн.

Указывая в своей статье применимость и ограничения выбранного метода (одного из многих), вы избежите вопросов об оптимальности.

Задачу серверной кластеризации гео-данных (расположенные рядом точки на карте должны объединяться в группы, чтоб не сливаться в одно большое пятно) индекс на основе Geohash решает в полном объеме, без ограничений и с хорошей скоростью, что можно увидеть на интерктивном примере, geohash-evgeniykhist.rhcloud.com. Говорить об оптимальности можно только определив критерий. Мне этот подход нравится своей простотой.

2D дерево, или мне показалось?

Красиво и элегантно. Респект.

А хіба не краще зберігати геодату в спеціалізованих сховищах, типу ElasticSearch чи Postgres+PostGIS, там крім геохешинга є ще купа вбудованих функцій (в т.ч. кластеризація).

PostgreSQL c PostGIS, наверное, лучше, но приложение может использовать другую БД, например. ElasticSearch, конечно, умеет работать с гео-данными, но это все равно в первую очередь сервер полнотекстового поиска. На мой взгляд, выбор системы или подхода для работы с гео-данными, зависит от многих факторов. Статья описывает еще один подход, помимо PostGIS и ElasticSearch.

Кластеризация объектов по алгоритму описанному в статье отсутсвует в самом свежем PostGIS 2.2.2. Там есть кластеризация, но другая — кластеризация индексов postgis.net/....html#database_clustering . Все равно алгоритм пришлось бы реализовывать в своем коде. А с остальным согласен: встроенные в PostGIS функции очень сильно облегчат и ускорят разработку фич связаных с геообъектами.

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