…И почему я решил сменить на что-то другое

Покемон GO! сразу после запуска стала глобальным феноменом, наложив наших любимых монстров на карту и позволив нам взаимодействовать с ними. Со временем были добавлены новые функции, такие как Рейды, и, в конечном итоге, специальные рейды под названием EX Raids. Учитывая редкость покемонов из этих рейдов, многие пользователи пытались предсказать механизм генерации EX-рейдов.

Появились некоторые теории о том, как количество спортзалов в одной ячейке S2 уровня 14 имело какое-то отношение к EX Raids. Это был первый раз, когда я услышал о S2 Cell (и, вероятно, это было верно для большинства игроков в покемонов на тот момент).

Ячейка S2 представляет собой четырехугольник, ограниченный четырьмя геодезическими. Самые большие получаются путем проецирования шести граней куба на целевую сферу. Каждая ячейка рекурсивно имеет 4 дочерних элемента, до 30-го, представляющего собой «листовые ячейки» размером около 1 см в квадрате.

Проблема

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

Решение?

Во-первых, я попытался использовать пакет кластеризации по умолчанию, доступный для Google Maps, но из-за того, что все выборки данных также выполнялись в фоновом режиме, производительность была ниже ожидаемой. Также почти не было возможности настройки под нужды приложения. Поэтому я вспомнил, чему научился у S2 Cells, и решил протестировать и посмотреть, как поведет себя карта.

Разделение одного и того же региона с использованием ячеек уровня 16 привело меня к следующему:

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

Есть несколько доступных пакетов npm, переносящих репозиторий S2 Geometry Library из Google в JavaScript, поэтому я решил использовать s2-geometry и перебрать Data Points для группировки по ячейкам и отображения на карте.

И результаты были очень многообещающими, с невероятной производительностью до 1000 Data Points в той же области. В течение месяца вопросы, связанные с картой, считались решенными.

Затем, однажды во время тестов, мы заметили, что некоторые точки данных «исчезают» с карты в зависимости от уровня масштабирования.

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

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

Итак, как я это исправил?

Во-первых, я потратил как минимум 3-4 часа, пытаясь представить лучшую форму. Или если бы использование нескольких разных форм помогло бы.

Но проблема кластеризации должна использовать алгоритм кластеризации. Я начал искать что-то, что могло бы помочь, и нашел K-Means.

Алгоритм KMeans группирует данные, пытаясь разделить выборки на N групп с одинаковой дисперсией, сводя к минимуму критерий, известный как инерция или сумма квадратов внутри кластера. Этот алгоритм требует указания количества кластеров. Он хорошо масштабируется для большого количества образцов и используется в широком диапазоне областей применения во многих различных областях.

Алгоритм k-средних делит набор из N выборок X на K непересекающихся кластеров C, каждый из которых описывается средним значением µj отсчетов в кластере. Средние обычно называют кластерными «центроидами»; обратите внимание, что они, вообще говоря, не являются точками из X, хотя и живут в одном и том же пространстве.

Источник: Scikit-learn

Мне не удалось найти пакет npm, который соответствовал бы моим требованиям, но были тысячи примеров, реализующих его с нуля на разных языках. Так что нужно было просто переписать алгоритм на TypeScript и изменить его, чтобы использовать координаты Data Points в качестве параметра. Я придумал это:

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

Заключение

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