Серверная кластеризация гео-объектов на карте на основе 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 бит преобразуются в символ, используя таблицу символов:

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,
g^min, g^max — минимальная и максимальная длина Geohash префикса,
z^min, z^max — минимальная и максимальная степень приближения.

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

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

В примере я использую следующие значения: g^min = 1, g^max = 12, z^min = 0, z^max = 17:

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

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