Комментарии 7
Все бы хорошо, но у иерархической системы квадратных сеток есть сильный недостаток - поскольку кодируются пары широты и долготы, то появляются различия в площади на разных широтах. Прям уух какие различия. В итоге uber, напрмер, создал свой spartial index H3. Их идея более жизнеспособна, и позволяет более точно кодировать координаты. Поиск по неточным координатам тоже возможен, правда, для случая z-curve есть ограничения. Я делал доклад по H3, несколько лет назад, удивлен, что кто то все еще использует S2.
Тут немного другая тематика -- построение фрактала и его применение. Мало разбить пространство (поверхность сферы в данном случае) на кусочки итеративно. Важен также порядок обхода. Обходы (в том числе многомерных) кубов влияют на кластеризации и близость хэшей близких точек. И принято использовать Z-curve или Hilbert curve. Для H3 вместо S2 тесты пока не проводились, но для квадратных решёток преимущества существенные, гексагональный случай можно попробовать погонять тоже. Был бы благодарен за ссылки в этом направлении.
Квадраты очень плохо натягиваются на глобус. Поэтому определение «рядом» приходится менять для каждого города (да и внутри крупных городов тоже плавает)
А можно глупый вопрос? Как реализуется поиск вблизи границ секторов, когда, насколько я понимаю, у двух даже очень близких точек будут разные хеши? В пределе - тот самый Гринвич, несколько метров на запад или на восток, и мы уже в западном/восточном полушарии с разными битами в старшем разряде?
Безусловно, близкие точки с далёкими хэшами будут в любом случае. Чтобы близость хэшей была равносильна близости точек, надо, чтобы пространства точек и хэшей были топологически эквивалентны (гомеоморфны). Но хэши — это отрезок, а точки — сфера. Они негомеоморфны, что ни делай. Но остаётся вопрос, насколько далеко в среднем получается до непрерывности. Если математически, то "бесконечно далеко" — её нет (например, выкидыванием точки отрезок можно разбить на две компоненты связности, а сферу — нет). Но если считать расстояния в количествах старших битов, в метрике Левенштейна или в чём-то ещё, от отсутствие непрерывности может влечь разные степени неприятностей или отсутствия желаемого профита. Добиться непрерывности нельзя, а вот что-то конструировать для улучшения качества геосервисов можно, уменьшая влияние отсутствия непрерывности.
Как математика улучшает геосервисы и помогает быстрее сориентироваться