Выполнение запроса геохэша в диапазоне памяти

Похоже, это должно быть возможно. Вам нужна точность 0,1 градуса. Конечно, сколько это в метрах, зависит от того, где вы находитесь на планете и говорим ли мы о долготе или широте. Но это можно посчитать. Основываясь на этом, вы можете выяснить, каким должен быть минимальный префикс вашего геша, чтобы его прямоугольная форма покрывала это. Более длинные хэши с тем же префиксом содержатся в прямоугольнике, который описывает меньший префикс.

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

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

Вы можете проверить мою библиотеку https://github.com/jillesvangurp/geogeometry. Он имеет алгоритмы и функции для всего вышеперечисленного. Вы можете делать круги, ограничивающие рамки или многоугольники и покрывать их геохэшами заданной максимальной длины. Вы можете вычислить подходящее значение для этой максимальной длины с помощью другой функции.

Он основан на Java, но он должен легко переноситься на Python или что-то еще, что вы хотите, учитывая, как я его структурировал. В основном это просто циклы и простая математика с использованием двойников.

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

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

In [33]: def geohash(lat, lng):
    ...:     "Approximate geohash algorithm."
    ...:     # Step 1: Convert to fixed-point.
    ...:     # I'm going to support six decimal places.
    ...:     lat = int(lat * 1e6)
    ...:     lng = int(lng * 1e6)
    ...:     # Step 2: Convert integers to 32-bit binary.
    ...:     lat = format(lat, '032b')
    ...:     lng = format(lng, '032b')
    ...:     # Step 3: Interleave bits from lat and lng.
    ...:     bits = [bit for pair in zip(lat, lng) for bit in pair]
    ...:     # Step 4: Convert bits to 64-bit integer.
    ...:     return int(''.join(bits), 2)
    ...: 
    ...: 

In [34]: lat, lng = 37.7749, 122.4194  # San Francisco, CA

In [35]: geohash(lat, lng)
Out[35]: 8215849339476576

Если вы немного измените широту и долготу, то число не сильно изменится. Вы можете создать ограничивающую рамку, добавляя и вычитая как широту, так и долготу:

In [38]: sf = geohash(lat, lng)

In [39]: lower_bounds = geohash(lat-0.001, lng-0.001)

In [40]: upper_bounds = geohash(lat+0.001, lng+0.001)

In [41]: lower_bounds < sf < upper_bounds
Out[41]: True

Теперь с нижней и верхней границами вы можете использовать SortedList.irange найти все точки вблизи заданной широты и долготы за время O(log(n)).