Введение
В последнее время возникла необходимость подсчитать все магазины в радиусе 5 километров от координат клиента и отсортировать их по пешеходной дистанции.
Самый прямой метод — обойти все магазины в городе, но этот метод явно не желателен, потому что временная сложность слишком высока, когда количество магазинов огромно, а пешее расстояние нужно вычислять и сортировать.
Мне вдруг пришло в голову, что я столкнулся с проблемой при создании изображений: даны три тысячи последовательных кадров в видео, но они не по порядку, я скажу вам первый кадр и отсортирую три тысячи кадров. Также не рекомендуется проходить через все пиксели изображения.В то время решением было использовать перцепционное хеширование для вычисления отпечатков пальцев всех изображений, а затем использовать расстояние Минши для вычисления изображения, наиболее близкого к первому изображению, в качестве второго изображения. , а затем рассчитайте расстояние до второго изображения. Самое последнее — это третье и так далее.
Кроме того, должны быть методы хеширования для преобразования географического местоположения в какую-либо кодировку, и кодирование может использоваться для географических вычислений. этоGeoHash.
2. Соответствующие знания
Прежде чем вводить текст, давайте вместе рассмотрим географию неполной средней школы:
Запад нулевого меридиана — это западная долгота, и он делится на двенадцать районов, каждый из которых составляет 15 градусов, а всего 180 градусов; восток — это восточная долгота, и он также делится на двенадцать районов, с всего 180 градусов.
К северу от экватора — северная широта, всего 90 градусов, к югу от экватора — южная широта, тоже 90 градусов.
Тогда в компьютере координаты выражаются как:
Западная долгота отрицательна, а восточная долгота положительна, поэтому долгота принимает значение
[-180, 180].Северная широта положительна, а южная широта отрицательна, поэтому широта принимает значение
[-90, 90].
Мы знаем, что длина экватора составляет около 40 000 километров, поэтому каждый градус долготы равен примерно 111 километрам. Земля на самом деле неправильная сфера, но для простоты предположим, что каждый градус широты примерно равен 222 километрам.
3. Знакомство с GeoHash
1. Рассчитать двоичный код
Сначала вычислите двоичный код над долготой[-180, 180]Начните с широты, начиная с[-90, 90]В начале интервал каждый раз делится на две части, и если входная координата меньше среднего значения, кодируется как0, следующий интервал занимает левую половину интервала, если она больше, код1, следующий интервал занимает правую половину интервала. И так далее, чем длиннее код, тем ближе к значению координаты и тем точнее.
к118°04′04, 24°26′46Например, сначала вычислите кодировку долготы:
| Длина кода | интервал | медиана | кодирование | иллюстрировать | Точность (км) |
|---|---|---|---|---|---|
| 1 | [-180, 180] | 0 | 1 | 118°04′04 больше 0°, поэтому закодируйте 1 и выберите правильный интервал | 19980 |
| 2 | [0, 180] | 90 | 1 | 118°04′04 больше 90° | 9990 |
| 3 | [90, 180] | 135 | 0 | 118°04′04 меньше 135°, поэтому код 0, взять левый интервал | 4995 |
| 4 | [90, 135] | 112.5 | 1 | 2497.5 | |
| 5 | [112.5, 135] | 123.75 | 0 | 1248.75 | |
| 6 | [112.5, 123.75] | 118.125 | 0 | 624.375 | |
| 7 | [112.5, 118.125] | 115.3125 | 1 | 312.188 | |
| 8 | [115.3125, 118.125] | 116.71875 | 1 | 156.094 | |
| 9 | [116.71875, 118.125] | 117.421875 | 1 | 78.047 | |
| 10 | [117.421875, 118.125] | 117.7734375 | 1 | 39.024 | |
| N | ... | ... | . | ... |
Точно так же необходимо закодировать вычисление широты:
| Длина кода | интервал | медиана | кодирование | иллюстрировать | Точность (км) |
|---|---|---|---|---|---|
| 1 | [-90, 90] | 0 | 1 | 24°26′46 больше 0°, поэтому закодируйте 1 и выберите правильный интервал | 19980 |
| 2 | [0, 90] | 45 | 0 | 24°26′46 меньше 45°, поэтому код 0, взять левый интервал | 9990 |
| 3 | [0, 45] | 22.5 | 1 | 4995 | |
| 4 | [22.5, 45] | 33.75 | 0 | 2497.5 | |
| 5 | [22.5, 33.75] | 28.125 | 0 | 1248.75 | |
| 6 | [22.5, 28.125] | 25.3125 | 0 | 624.375 | |
| 7 | [22.5, 25.3125] | 23.906 | 1 | 312.188 | |
| 8 | [23.906, 25.3125] | 24.609 | 0 | 156.094 | |
| 9 | [23.906, 24.609] | 24.2575 | 1 | 78.047 | |
| 10 | [24.2575, 24.609] | 24.433 | 0 | 39.024 | |
| N | ... | ... | . | ... |
Подводя итог, предполагая, что мы берем только десятизначный код, код, полученный из долготы, равен1101001111, закодированный в широте как1010001010.
Переплетение двух кодов, таких как деформация и уток сетки:
11100110000011101110Объединив данные о точности из двух вышеприведенных таблиц, мы знаем, что код на самом деле представляет собой прямоугольный блок длиной и шириной 39,024 километра.
2. Преобразование кодировки base32
Двоичное кодирование на самом деле можно использовать как геокодирование, но:
- Неудобно находить соседние блоки. Для расчета смежных блоков перед расчетом его необходимо разобрать на два кода долготы и широты. После использования кодировки base32 для ускорения вычислений можно использовать метод поиска по таблице.
- Длина двоичного кода слишком велика, что не способствует поиску.
Поэтому GeoHash использует кодировку base32 и base36, поскольку большинство из них используют кодировку base32, поэтому в этой статье рассматривается только кодировка base32.
| Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B | C | D | E | F | G |
| Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base 32 | H | J | K | M | N | P | Q | R | S | T | U | V | W | X | Y | Z |
В кодировке base32 всего 32 кода, поэтому требуется 5 бит, а11100110000011101110Преобразовать в кодировку base32:
WS7F.
В-четвертых, вычислить соседние блоки
1. Общий закон
Входными данными общего метода является двоичный код, поэтому, в отличие от метода поиска по таблице, который имеет ограничение на количество цифр, он подходит для всех ситуаций, а процесс прост.
Во-первых, двоичный код, чередующийся по широте и долготе, делится на долготу и широту.Если входное положение север, добавьте одну широту, если это юг, вычтите одну широту, если это запад, вычтите одну долготу, если это восток. , добавьте одну долготу плюс один. Следует отметить, что исходные значащие цифры должны сохраняться после сложения и вычитания (например, 11 + 01 = 00, сохраняются две значащие цифры). Наконец, результаты вычислений рекомбинируются для получения двоичного кода искомой позиции.
Процесс показан на следующем рисунке в качестве примера и здесь повторяться не будет:
2. Метод справочной таблицы
Вычисление метода поиска по таблице происходит намного быстрее, чем при обычном методе, и нет необходимости разбивать входной код на широту и долготу для сложения и вычитания, но следует отметить, что вход представляет собой кодировку base32, поэтому он применим только к двоичному коду, кратному 5.GeoHash.
Большинство статей в Интернете рассказывают только о том, как использовать метод справочной таблицы для вычисления соседних блоков, так как же получить эту справочную таблицу? Как после получения кодировки вычислить соседние блоки? Большинство статей в Интернете рассказывают только о том, как использовать метод справочной таблицы для расчета соседних блоков, но как получить эту справочную таблицу?
Согласно вышеизложенному, мы знаем, что код состоит из 5 двоичных битов и чередуется по широте и долготе. Следовательно, если код состоит из нечетного числа битов, т.е.经 纬 经 纬 经Режим чередования; если он четный, то纬 经 纬 经 纬переплетение.
Затем, сWНапример, двоичный файл11100, если он состоит из нечетного числа цифр, он будет в таблице как右 上 右 下 左, если это четная цифра, то она есть в таблице上 右 下 左 下,следовательноWРасположение в таблице поиска следующее:
WS7FНапример, теперь запрашиваем соседний блок этой позиции, берем последний битF, как видно из таблицы четных битов,Fнаходится рядом сE, G, D, 9, C, и за пределы вправо5, 4, 1. следовательно5, 4, 1В трех соседних блоках тоже нужно смотреть на предпоследнюю цифру7. Как видно из таблицы нечетных чисел,7Справа от р.K.
Следовательно, соответствующие биты окружающих смежных блоков получаютсяWS7E, WS7G, WS7D, WS79, WS7C, WSK5, WSK4, WSK1, отношение позиций следующее:
V. Резюме
В основном вводятся теоретически:
- Метод GeoHash для кодирования точек географического положения: получение двоичного кода в соответствии с «рекурсивной дихотомией» и преобразование двоичного кода в кодировку Base32.
- Быстрый метод вычисления соседних блоков GeoHash: возьмите последний битовый код, найдите соответствующий код соседнего блока в соответствии с таблицей четных битов, если определенное направление выходит за пределы, ищите предыдущий битовый код и найдите соответствующее направление. код по таблице чет/нечет.
Реализация алгоритма:[Примечания о перемещении блоков] Использование GeoHash для кодирования географического местоположения — реализация
6. Расширение
-
GeoHash можно использовать не только для кодирования точек местоположения, но и для кодирования лиц, что полезно для обработки расчета различных комбинаций точек и лиц. Например, определить, находится ли точка в пределах забора доставки магазина.
-
GeoHash на самом делеКривая ПеаноПрименение, как показано ниже:
Есть также много кривых, заполняющих пространство, например, те, которые обычно считаются хорошими без серьезных мутаций.кривая Гильберта.