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

Решение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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