Реализация иерархического поиска с помощью H3
Гексагональный иерархический пространственный индекс от Uber
Для задач исследований больших наборов пространственных данных важную роль играют сеточные системы (grid systems), которые разбивают поверхность земли на идентифицированные ячейки разного масштаба. Каждая ячейка обладает определенными характеристиками, что позволяет анализировать ее отдельно или в сравнении с другими.
Uber разработал собственную такую систему H3, обладающую рядом преимуществ над существующими до этого. Он использует ее для задач динамического ценообразования, диспетчеризации, визуализации и др. исследований.
Технические подробности
Изначально поверхность земли представлена в виде сферического икосаэдра – многогранника с 20 гранями. Каждая грань – треугольник. На каждый треугольник проецируются многоугольники, центрируясь по центру грани. В результате получается разбиение 0-го масштаба. Образуется 122 многоугольника. Из них 110 шестиугольников и 12 пятиугольников. Из-за превалирования шестиугольников схема получила название гексагональной
Иерархическое представление
Каждый гексагон 0-го масштаба разбивается на7 дочерних гексагонов. Пятиугольник на 5 дочерних 5 угольников. Каждый дочерний многоугольник разбивается на более мелкие. H3 всего состоит из 16 масштабов.
Каждый дочерний многоугольник может однозначно идентифицироваться относительно родительского по следующей схеме. Идентификатор по сути представляет целое число от 0 до 6.
Перечисляя номера ячеек относительно родительской, двигаясь от большего масштаба к меньшему, и получается иерархический индекс. Пример:
Бинарное представление индекса
Индекс представляет собой число ulong.
Идея – если индексировать в более детальном масштабе, можно вести поиск по более грубому масштабу – т.е. по родительским гексагонам Для этого убираем ведущие биты со служебной информацией. И делаем обычный числовой индекс в БД.
В результаты в выборку попадут все шестиугольника у которых бинарный префикс будет равен зеленой части. Они будут являться потомками поискового шестиугольника.
Подобный алгоритм работает при индексации S2 в монге
Объединение соседних ячеек
Соседние ячейки будут иметь соседние интервалы. При построении поискового запроса эти интервалы можно объединять. Количество обходов индекса в БД при этом будет уменьшаться
Пример https://observablehq.com/d/07557cde0d417062
.Net H3.Net. биндинг к библиотеке на C.