Pull to refresh

Кластеризация на клиенте или как показать 10000 точек на карте

Reading time 7 min
Views 30K
Существует несколько типов проектов,
для которых вывод геоинформации является
необходимым: сайты по недвижимости, каталоги компаний,
каталоги достопримечательностей, доски объявлений и другие.
Для этих сайтов я решил разработать плагин к goolge API 3 и Яндекс API 2.

Основные требования:
  1. Возможность подключения без глубокой подготовки данных на сервере, а именно, используя только уже имеющиеся географические координаты объектов.
  2. Простой протокол подготовки и передачи данных.
  3. Быстрый клиентский кластеризатор с ДВУМЯ типами меток: кластер и группа. Кластер — несколько объектов, расположенных рядом. При клике кластер “раскрывается”, то есть увеличивает зум пока объекты будут на расстоянии, большем чем расстояние кластеризации. Группа — несколько объектов в одной точке (на минимальном расстоянии). При клике на группу на любом зуме выводится список объектов в группе.
  4. Отображение до 10000 точек с использованием кластеризатора.
  5. Отображение в ie7, на мобильных устройствах (iPad первого поколения).
  6. Шаблонизация на клиенте двух инфоокон — группового кластера и самого объекта.
  7. Использование спрайта для меток.
  8. Возможность использования неограниченного количества типов меток (иконок) для разных типов объектов.
  9. Возможность использования нескольких размеров иконки для разного диапазона зума.

В статье я опишу несколько подходов, которые были использованы для реализации этого плагина.

Замер времени работы функций проводился на нескольких устройствах. Для удобства я буду писать через дробь 2 из них — Google Chrome 19.0 @ AMD Athlon 64 X2 Dual Core 5600+ 2.8 GHz ОЗУ 2Gb Windows-7 32bit как среднячок и Safari@Apple iPad 16GB 1.0 GHz iOS 5.1.1 как самый медленный и капризный.

Серверная часть


Серверная часть состоит из двух запросов:

1. Запрос на данные карты.

В этот запрос передается ссылка с параметрами для выборки меток. Например, ?city=1&rooms=1,2. То есть выбираем только город id=1 c 1 и 2-х комнатными квартирами (пример для сайта по недвижимости).
В ответ отдается скрипт с json-параметрами карты (типа карты, центр и зум карты, параметры иконок, расстояние кластеризации, спрайт и т.д.) и json с данными обо всех точках. Данные точки содержат: id объекта, геокоординаты, тип иконки и строку всплывающей подсказки. На 10000 точек в несжатом состоянии размер ответа — 1,2Мб, но при сжатии gzip — всего 350 кб.
Часто повторяющиеся запросы хорошо кэшируются nginx’ом.

2. Запрос об объекте.

При клике на одиночный маркер всплывает инфоокно с данными об объекте. Ajax-запрос содержит id объекта. В ответ отдается json. Названия полей json должно совпадать с тэгами в шаблоне инфоокна, последние подменяются полученным содержанием.

Клиентская часть


Парсинг данных о точках

Полученные данные обрабатываются следующим образом:
1. Вычисляются глобальные пиксельные координаты на нулевом зуме для каждой точки.
2. Исходя из глобальных координат вычисляется id тайла на 14-ом зуме, и точки помещаются в массив с соответствующим id тайла. В дальнейшем, на любом зуме можно легко вычислить Id необходимых тайлов и выбрать все точки для них. Скорость выборки точек — для 10,000 точек не более 100/350мс.

Время парсинга 10000 точек — 100/650 мс

Кластеризатор

Мною были опробованы несколько кластеризаторов, в том числе и нативный Clusterer от Яндекс API 2. Ни один меня не устроил по нескольким причинам. Во-первых, во всех есть только кластер, нет группы. После клика на кластер, зум увеличится до максимального, но список не появится. Надо опять кликать, чтобы получить список. Именно так устроен Clusterer от яндекса. В MarkerClusterer forGoogle Maps v3 также нет подобного типа маркера.
Во-вторых, кластеры обсчитываются по grid, что, хотя и быстро, но кластеры при большом количестве меток располагаются “по сетке”, и выглядит это некрасиво.
В результате был написан собственный кластеризатор Clusterize. В нем способ кластеризации асинхронно-гибридный: при запросе данных для тайла происходит следующее:
— тайл разбивается на 4 подтайла (сетка) и каждый подтайл кластеризуется по distance, но сам кластер располагается не в середине ячейки, а в центре области «схлопнутых» точек.
— полученные точки и кластеры собираются обратно в тайл, и снова кластеризуются. На этом этапе точек уже немного.
— полученные точки “прореживаются” с учетом граничащих тайлов (если они уже были кластеризованы). То есть если в граничащем тайле на границе есть кластер или маркер, перекрывающий маркер на нашем тайте, то эти маркеры объединяются в кластер. Этим мы добиваемся отсутствия “слипания” маркеров на границах тайлов.
Скорость кластеризации получилась довольно высокой: из 10,000 получаем 580 точек за 60/500мс. Вполне приемлемо.

Иконки маркеров

Для вывода иконок я использую спрайт. Количество типов иконок не ограничено. В примерах используется 7 типов иконок для одиночных маркеров + иконки кластера и группы. Каждый тип иконки в примере 2 двух вариантах — крупный для зума более 14 и мелкий для менее 14. Так как расстояние кластеризации — 17 пикселей, то для мелких масштабов мелкие иконки смотрятся симпатичнее.



Шаблоны инфоокон

По клику на маркер происходит:
1. Если маркер является кластером — кластер зумится до “раскрытия”.


2. Если маркер — группа, выводится список объектов из этой группы:

3. Одиночный маркер подгружает данные и выводит инфоокно


Вывод маркеров.

Для вывода маркеров я использовал Google API 3 и Яндекс API 2.
Была написана модель, в которой я храню и обрабатываю данные, кластеризую тайлы и отрисовываю канвасы, а также несколько контроллеров, которые подгружают необходимый API и выводят маркеры.

Google API 3 — нативный контроллер

Контроллер использует нативные функции Google Api 3 и кластеризатор Clusterize.
Google API 3 быстро подгружается, по возможности использует canvas, поддерживает спрайты для меток.
Пример
Достоинства
Небольшое количество кода
Автоматическое переключение на CANVAS
Поддержка спрайта
Недостатки
Медленная и корявая прорисовка при смене зума
В ie на каждый маркер создаются 4 объекта, на зуме 10-12 в ie обрушивает DOM

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Google API 3 — canvas-контроллер

Контроллер использует canvas для рендеринга каждого тайла и кластеризатор Clusterize.
В этом контроллере тайлы рендерятся на канвасе асинхронно. Особых преимуществ по сравнению с нативными функциями не имеет, кроме небольшого выигрыша в скорости отрисовки.
Пример
Достоинства
Небольшое количество объектов DOM
Более высокая скорость рендеринга до 50% по сравнению с нативным контроллером
Поддержка спрайта
Недостатки
Мигание при смене зума
Не поддерживается в ie

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Google API 3 — fullcanvas-контроллер

Контроллер использует canvas для рендеринга всей видимой части карты.
Кластеризатор Clusterize.
Используется подложка canvas’а под размер видимой части карты и прорисовывается при каждом движении.
Пример
Достоинства
Самое малое количество объектов DOM
Самая высокая скорость рендеринга до 100% по сравнению с нативным контроллером
Поддержка спрайта
Поддержка FlashCanvas для ie 6>
Красивая анимация при смене зума
Недостатки
В ie работает только при масштабе страницы 100% (bug)

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Яндекс API 2 — нативный контроллер «из коробки»

Контроллер использует функции API 2 «из коробки».
Кластеризатор также нативный Clusterer.
В новом Яндекс API 2 кластеризатор уже встроен в апи в качестве модуля. Использование кластеризатора — 3 строки кода. Имеется настройка иконок кластеров и инфоокон со списком. В данном примере я этого не использовал, так так время обработки данных просто катастрофическое.
Пример (вывод может занять длительное время!)
Достоинства
Все функции — из коробки
Недостатки
Очень медленная начальная обработка и кластеризация
Огромное количество объектов DOM
Отсутствие типа кластера «точка»
Отсутствие поддержки спрайта.
Мигание при смене зума

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Яндекс API 2 — нативный контроллер

Контроллер использует функции API 2 для размещения GeoObject.
Используются программные шаблоны для меток и кластеризатор Clusterize.
Этот контроллер я переписывал несколько раз. ymaps.GeoObject на сегодняшний момент не поддерживает спрайты, а фабрика overlay.staticGraphics.Placemark — не поддерживает тени. В результате я сделал свой шаблон layout’a для маркеров, который состоит из 2 дивов — иконки и ее тени.
Пример
Достоинства
Достаточно высокая скорость подготовки карты
Поддержка спрайта через layout метки
Недостатки
Огромное количество объектов DOM
Медленно
Убивает ie

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Яндекс API 2 — canvas-контроллер

Контроллер использует canvas для рендеринга каждого тайла и кластеризатор Clusterize.
Использует тот же рендер, как и Google canvas. В отличие от Googe API, где канвасы плавно анимировались при смене зума, добиться этого от Яндекс API 2 мне не удалось, хотя уже сейчас я знаю, как это сделать (костылем).
Пример
Достоинства
Небольшое количество объектов DOM
Высокая скорость рендеринга
Поддержка спрайта
Сглаженные эффекты перемещения
Недостатки
«Каша» при смене зума
Не поддерживается в ie

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Яндекс API 2 — fullcanvas-контроллер

Контроллер использует canvas для рендеринга всей видимой части карты.
Рендеринг производится при каждом перемещении карты и смене зума.
Кластеризатор Clusterize.
В отличие от Google fullcanvas-контроллера, здесь канвас шире и выше области просмотра. Поэтому перемещение карты получается более плавным. Анимацию при смене зума пришлось написать самостоятельно.
Пример
Достоинства

Самое малое количество объектов DOM
Самая высокая скорость рендеринга
Поддержка спрайта
Поддержка FlashCanvas для ie 6>
Красивая анимация при смене зума
Недостатки
В ie работает только при масштабе страницы 100% (bug)

Скорость вывода карты 10 зума с 10,000 точками и кластеризацией


Действующие примеры Вы можете посмотреть здесь

Вывод.


Использование fullcanvas контроллеров наиболее эффективно. Для ie применим FlashCanvas, хотя пока и с ограничениями.
Более того, fullcanvas контроллер — это отличная возможность использования WebGL для анимации маркеров (например, 3d повороте за курсором), создания других эффектов анимации.
Шаблоны для инфоокон позволяют настраивать дизайн под любой проект, а также отображать любую информацию об объекте.
На сегодняшний день плагин написан на 95%. Осталось подобрать некоторые баги, а также оптимизировать рендеринг канваса в fullcanvas контроллерах.
Единственная пока нерешенная проблема — масштаб страницы для FlashCanvas в ie. Думаю, в ближайшее время и ее удасться побороть.
Tags:
Hubs:
+51
Comments 22
Comments Comments 22

Articles