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

Question

Прежде всего я хотел бы сказать, что я не заинтересован в использовании Redis или любой другой пространственной БД. Я пытаюсь сделать очень упрощенный запрос в диапазоне геохэш-памяти в памяти, и я использую следующее программное обеспечение для вычисления пакета C geohash-geohash-int, и у меня есть оболочка Cython для вызова этих API в Python 3.6. Я использую SortedList для хранения геохешей, и моя цель - сделать простой запрос диапазона геохешей в памяти.

#GeoHash is a Cython wrapper of external C geohash library (link provided)
from geo import GeoHash
from sortedcontainers import SortedList
import numpy as np

import time
minLat = 27.401436
maxLat = 62.54858
minLo = -180.0
maxLo = 179.95000000000002
latGrid = np.arange(minLat,maxLat,0.05)
lonGrid = np.arange(minLo,maxLo,0.05)
geoHash = GeoHash()

print(latGrid.shape,lonGrid.shape)
gridLon,gridLat = np.meshgrid(lonGrid,latGrid)
grid_points = np.c_[gridLon.ravel(),gridLat.ravel()]

sl = SortedList()
geohash1 = {}
t0 = time.time()
for grid_point in grid_points:
   lon = grid_point[0]
   lat = grid_point[1]
   geohash = geoHash.encode(lon,lat,26)
   bitsOriginal = geohash["bits"]
   sl.add(bitsOriginal)
   neighbors = geoHash.get_neighbors(geohash)
   for k,v in neighbors.items():
        bits1 = v["bits"]
        sl.add(bits1)
t1 = time.time()
print(t1-t0)
lonTest = 172.76843
latTest = 61.560745
geohashTest = geoHash.encode(lonTest,latTest,26)
bitsTest =    geohashTest["bits"]

Что я хочу сделать, это следующее

it = sl.irange(bitsTest-window,bitsTest+window)

Мой вопрос, как мне о расчете окна? Я хочу, чтобы окно было в пределах 0,1 градуса или любого другого окна, которое я укажу. Я понятия не имею, как рассчитать окно. Весь пакет geohash очень быстрый, и меня интересуют только приблизительные совпадения для моего запроса. Я считаю, что моя контрольная точка должна находиться в пределах "диапазона" входного набора данных, для которого я рассчитал геохеш, но я не знаю, как получить диапазон геохешей для моей точки запроса. Может кто-нибудь помочь?

ОБНОВЛЕНИЕ Предложенный ответ в порядке, но имеет сложность O( N). Если существует сложность порядка O(log N), которая была бы приемлемой.

Answer 1

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

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

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

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

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

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

Answer 2

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

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)).