Введение

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

А что у нас тут? Mapbox GL JS может обрабатывать загрузку массивного набора данных GeoJSON объемом 106 МБ с областями почтового индекса США с более чем 33 000 объектов, сформированных более чем 5 миллионами точек, непосредственно в браузере без поддержки сервера.

Вы можете в это поверить, братья? Всего за несколько секунд загрузки вы можете легко и плавно просмотреть весь набор данных. Но как это работает? Давайте копнем глубже.

Нарезка векторных плиток

Мы не можем ожидать полного рендеринга такого огромного объема данных со скоростью 60 кадров в секунду, но, к счастью, нам это и не нужно. При более низких уровнях масштабирования фигуры не должны быть такими подробными, а при более высоких уровнях масштабирования большая часть данных находится за пределами экрана.

Лучший способ оптимизировать данные для всех уровней масштабирования и экранов — разбить их на векторные фрагменты. Традиционно это делается на сервере с помощью таких инструментов, как Mapnik и PostGIS. Но можем ли мы создавать эти векторные тайлы на лету, прямо в браузере?

Что ж, брэдрен, специально для этой цели я написал новую JavaScript-библиотеку под названием geojson-vt. И позвольте мне сказать вам, что это быстро и эффективно, и его использование выходит далеко за рамки браузера. Он поддерживает рендеринг GeoJSON в Mapbox GL JS, был портирован на C++14 для поддержки рендеринга точек и полилиний на мобильных устройствах с помощью Mapbox Mobile и даже работает на сервере с Node.js. Мы экспериментируем с его использованием в нашем конвейере обработки данных на стороне сервера, мон.

Как работает GeoJSON-VT

Предварительная обработка

Генерация плиток включает в себя множество вычислительно затратных шагов:

  • проецирование географических координат в экранные координаты
  • оптимизация деталей полилиний и полигонов для каждого уровня масштабирования
  • фильтрация объектов, которые слишком малы для определенного масштаба
  • обрезка данных до экстентов плитки

GeoJSON-VT выполняет эти шаги по порядку: проецирует весь набор данных и вычисляет упрощение перед созданием листов. Таким образом, создание множества плиток с различными уровнями масштабирования может выполняться быстро и без дублирования работы.

Первым шагом предварительной обработки является проецирование всех координат в диапазон [0..1, 0..1] с помощью проекции Web Mercator. Позже мы можем получить координаты тайлового экрана простым умножением плюс округление:

screen_x = [tile_size × (2^увеличение x – tile_x)]
screen_y = [tile_size × (2^увеличение y – tile_y)]

Следующим шагом является вычисление данных упрощения, которые впоследствии используются для уменьшения детализации каждой плитки. Он использует модифицированный алгоритм упрощения Рамера-Дугласа-Пекера, который рекурсивно находит наиболее значимые точки ломаной и отбрасывает ненужные детали.

Это тот же метод, который используется в Leaflet и simplify-js, но вместо того, чтобы сразу упростить данные, GeoJSON-VT помечает каждую вершину значением важности, чтобы ее можно было быстро включить или исключить на уровне масштабирования.

Поскольку расстояния в пикселях линейно масштабируются с увеличением 2^, мы можем запустить упрощение данных один раз и использовать одни и те же значения для оптимизации деталей на каждом уровне масштабирования, практически мгновенно отфильтровывая ненужные вершины.

Затем мы вычисляем площадь каждого полигонального кольца и длину каждой полилинии. Площади и длины масштабируются с уровнем масштабирования так же, как и расстояния, что позволяет нам отфильтровывать геометрию, которая слишком мала для отображения на любом конкретном уровне масштабирования, используя эти предварительно рассчитанные значения в линейном времени.

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

Нарезка данных на плитки

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

Чтобы сделать это быстро, GeoJSON-VT использует подход сверху вниз, разделяй и властвуй к отсечению:

  1. Разрежьте верхнюю плитку z0 на четыре плитки z1.
  2. Разрежьте каждую плитку z1 на четыре плитки z2.
  3. Повторить рекурсивно.

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

Вот как обычно работает наиболее распространенный алгоритм отсечения прямоугольников Сазерленда-Ходжемана:

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

Обратите внимание, что разрез тайла составляет не ровно четверть родительского тайла, потому что каждый тайл должен иметь небольшой буфер, выходящий за пределы того, что мы отображаем на карте, чтобы решить проблемы с рендерингом (например, Mapbox Studio Classic буферизует каждый тайл 512 пикселей на 8 пикселей в каждом направлении по умолчанию).

Давайте примерно посчитаем, сколько времени потребуется, чтобы отсечь 4 плитки относительно количества данных в родительской плитке:

4 × (n + 1/2 n + 1/4 n + 1/4 n) = 8n

Мы можем вырезать 4 плитки из родительской плитки более разумным способом. Для этого я сделал простую модификацию алгоритма отсечения полуплоскости, заставив его обрезать фигуры между двумя параллельными осями за один раз: вырезая полосу. Таким образом, мы можем сначала разрезать две половины с двумя вертикальными полосами, а затем вырезать 2 плитки из каждой половины с двумя горизонтальными полосами:

Давайте посмотрим, как это соотносится с предыдущим подходом:

n + n + 4 × 1/2 n = 4n

Таким образом, теперь у нас примерно в 2 раза быстрее отсечение каждого тайла.

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

Нарезка на лету

Чтобы обслуживать векторные листы на лету без заметной задержки, в идеале мы должны генерировать все векторные листы до максимального масштаба в кэш, а затем просто мгновенно обслуживать листы по запросу. Это может быть хорошо для небольших наборов данных, но для чего-то большего процедура нарезки плитки в конечном итоге исчерпает память. Только на 15-м уровне масштабирования потенциально может быть ⁴¹⁵ = ~1 миллиард плиток — это слишком много, особенно для браузера.

Таким образом, мы не можем нарезать плитки до максимального масштаба при начальной загрузке данных, но мы можем нарезать их до точки, когда последующая нарезка по требованию занимает так мало времени, что задержка загрузки становится незаметной. GeoJSON-VT решает эту проблему несколькими способами:

  1. Первоначально тайлы генерируются с определенным уровнем масштабирования, оставляя все остальное для нарезки по требованию.
  2. При нарезке плиток мы отслеживаем количество точек, объединенных в каждой плитке. Первоначальная нарезка останавливается, когда плитка опускается ниже определенного порога
    (по умолчанию 100 000 точек). Если тайл содержит несколько геометрий, то его дочерние элементы могут быть сгенерированы быстро по мере необходимости.
  3. При детализации до определенного тайла GeoJSON-VT нарезает только один тайл на 4 дочерних тайла на каждый масштаб в диапазоне масштабирования, кэшируя все нарезанные тайлы. Таким образом, переход к соседним плиткам выполняется очень быстро, потому что родительская плитка гораздо меньшего размера будет кэширована из предыдущей детализации плитки.

Я обнаружил, что начальные значения срезов по умолчанию (z5 и 100 000 точек) являются оптимальным выбором для большинства выборочных наборов данных, на которых я тестировал алгоритм — первоначальная обработка выполняется относительно быстро, а последующая детализация происходит почти мгновенно.

Нам также необходимо минимизировать объем памяти, используемый на каждом шаге алгоритма. Это достигается несколькими вещами:

  1. Исходная геометрия сохраняется только в тайлах с самым большим масштабом и удаляется после того, как тайл будет разрезан на 4 тайла следующего уровня масштабирования,
    сохраняя только упрощенные данные. Таким образом, объем памяти, необходимый для хранения всех данных листов, не растет экспоненциально при более глубоком срезе.
  2. Вся рекурсия устраняется с помощью итерационных алгоритмов. И упрощение, и нарезка плитки (рекурсивная по своей природе) реализованы с использованием простой очереди массивов, обрабатываемой в цикле. Это позволяет избежать ситуации, когда геометрия, которая вам больше не нужна, накапливается в стеках вызовов: она правильно очищается от мусора.
  3. Преобразование спроецированных (0..1, 0..1) координат в экранные координаты всегда происходит по запросу, потому что построение новых массивов занимает много памяти, если это делается для всех плиток, как только они нарезаются.
  4. Сплошные квадраты, заполненные до экстента плитки (плитки, полностью находящиеся внутри полигона), никогда не разрезаются дальше, потому что все ее дочерние элементы идентичны родительскому независимо от уровня масштабирования.

Отладка и профилирование производительности

Для отладки и оптимизации библиотеки я написал простую страницу отладки, где вы можете перетащить файл GeoJSON на базовую карту, где он обрабатывается GeoJSON-VT:

API-интерфейс библиотеки также имеет параметр debug с двумя уровнями ведения журнала, выполняя различные уровни времени производительности и ведя журнал во время тайлинга, когда это указано.
GIF-файл выше демонстрирует уровень 1, а уровень 2 выводит отладочную информацию для каждой отдельной плитки. Это очень помогло решить все узкие места и проблемы с отслеживанием.

Рендеринг без рывков в Mapbox GL JS

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

Браузеры обычно запускают код JavaScript в том же потоке, который обрабатывает все обновления пользовательского интерфейса и взаимодействие с пользователем. Если JavaScript занят выполнением тяжелых вычислений,
страница зависнет и не примет никакого пользовательского ввода.

Чтобы избежать задержек и зависаний при загрузке и обработке данных, Mapbox GL JS использует Web Workers, современную функцию браузера, которая позволяет выполнять ресурсоемкий код в фоновом режиме, не прерывая основной поток.

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

Чтобы избежать этого узкого места, мы воспользуемся еще одной функцией HTML5 — Переносимые объекты. Это позволяет передавать данные между потоками мгновенно с нулевой копией, если вы передаете данные в виде типизированных массивов. Это позволяет нам обеспечить бесперебойную работу без зависаний, несмотря на то, что в фоновом режиме происходит много тяжелой работы ЦП.

Использование библиотеки

Если вы используете инструменты на основе Mapbox GL (либо GL JS, либо Mapbox Mobile), вы уже используете GeoJSON-VT внутри.

Вы можете использовать его вручную и для других приложений — вся сложность обработки скрыта за очень простым API:

var tileIndex = geojsonvt(data);
...
var tile = tileIndex.getTile(z, x, y);

Полученная плитка представляет собой простой JSON-эквивалент Векторной плитки и может быть легко визуализирована.

Попробуй это! Нам любопытно посмотреть, какие другие творческие способы использования библиотеки вы можете придумать. Я также рекомендую вам проверить репозиторий geojson-vt
и прочитать код — он был тщательно написан, чтобы быть максимально простым и понятным.