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

    Существует несколько типов проектов,
    для которых вывод геоинформации является
    необходимым: сайты по недвижимости, каталоги компаний,
    каталоги достопримечательностей, доски объявлений и другие.
    Для этих сайтов я решил разработать плагин к 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. Думаю, в ближайшее время и ее удасться побороть.
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 22

      0
      Ух пригодилась бы такая штука. Я напоролся в свое время, когда пытался сделать фильтр по категориям точек — галками отмечаем, какие показывать, какие нет. При использовании гугловского кластеризатора точки пропадали, а кластеры — нет. Причем даже принудительно прятаться они отказывались( А как у вас реализуется такой функционал? Насколько я понимаю, надо перерисовывать тайлы?
      З.Ы. Вы это на каких условиях выложили — чтобы люди пользовались или только посмотреть?
        0
        Я не фильтрую данные на клиенте. Смысл этого плагина в том, чтобы предоставить возможность просмотра результатовпоиска на карте. Скажем, на сайте недвижимости юзер выбирает параметры поиска в форме, и ему предоставляется возможность посмотреть результаты в виде списка или на карте.

        З.Ы. люди могут пользоваться подходом к разработке своих сервисов. готовый плагин мне слишком сложно будет задокументировать и поддерживать.
          0
          Спасибо за труд. Использовал в своём проекте, нашел ошибку.
          Если на карте нужно отобразить одни иконки, а потом набор других, то старые не стирались.

          В citymap.js в строках:

          var ctx = canvas.getContext("2d"); ctx.rect(0,0, canvas.width, canvas.height); ctx.clearRect(0,0, canvas.width, canvas.height);

          нужно ctx вынести в глобальную переменную и получать контекст только 1 раз.

          if(typeof ctx != 'undefined') { ctx.clearRect(0,0, canvas.width, canvas.height); } else { ctx = canvas.getContext("2d"); } ctx.rect(0,0, canvas.width, canvas.height);
            0
            Это вы наверное автору хотели написать? Если да, то ошиблись веткой.
          +1
          Интересный доклад на смежную тему был на Future Insights, спикер из Facebook рассказывал о визуализации большого кол-ва данных на картах. Вот видео, пароль habrahabr
            0
            Спасибо за ссылку. Честно говоря, смешно, когда они называют huge amount of data какие-то 1500 точек. Мой алгоритм кластеризации попроще, но сам метод позволяет показывать больше данных.
            Хотя, у нас разные задачи.
              0
              Тут больше о качестве визуализации, чем о кол-ве, спикер в этом докладе разные примеры и приводил с чем пришлось столкнуться. Как он сам ответил: 1200 разных меток на карте — это максимум что они видели у пользователей.
          • UFO just landed and posted this here
            • UFO just landed and posted this here
                0
                это жестко. при каждом движении карты делать запрос к серверу (причем запрос невозможно кэшировать), да еще и мучать mysql запросом с file sort ))
                Просто у нас с Вами разные задачи. Я делаю плагин для высоконагруженных приложений с большим количетвом данных.
                • UFO just landed and posted this here
                    0
                    10к точек — это 350Кб. На iPad при размере карты в экран помещается 15 тайлов с подложкой (это только при начальной загрузке). каждый тайл — 30кб в среднем — уже 600кБ. Тем более, что это — только начало. Каждое движение карты — это загрузка тайлов. За один сеанс работы с картой вы загрузите никак не меньше 2Мб. Так что 350Кб — это семечки.
                      0
                      упс… что-то с математикой после полуночи)) конечно, 450кБ
                        0
                        Это всё да, но решение «сразу грузим все точки на клиент» немасштабируемое.
                        Ладно, 10К — терпимо. А что делать, когда станет 100К? Миллион?
                0
                При сдвигании карты, (зум не трогаю) магическим образом отображаются точки ) joxi.ru/ZIcIp3eQ это первое состояние, а вот немного сдвинув карту joxi.ru/Z1rdlS1n
                0
                Может я что-то не так делаю, но ни один пример с maps.1cs.su/ не выводит ни одной точки, только карты.
                  0
                  Город Москва только.
                  0
                  Странно, никак не могу понять почему fullCanvas быстрее чем обычный тайловый — он же при движении карты тупить должен нехило так.
                  И тебе значит нужно чтобы при плавном зуме маркеры сохраняли свои размеры?
                    0
                    как оказалось, рендеринг — очень быстрая штука. а все остальное — уже в кэше.
                    более того, я еще не сделал частичную перерисовку канваса — сейчас он при движении перерисовывается весь.
                    При плавном зуме канвас просто пропорционально уменьшается/увеличивается.
                    Сохранять размер маркера при плавной масштабировании?.. Теоретически, это надо делать в движке. Сначала просчитывать и прорисовывать переходы, а потом их показывать юзеру. Надстройкой над АПИ этого не сделать.
                    Хотя, я попробую)
                    0
                    Уважаемый автор, а вы бы могли написать для какого проекта все это делается?
                      0
                      Это исследование делалось для russia.auto.ru, но проект так и не был закончен.

                    Only users with full accounts can post comments. Log in, please.