Geohash - Geohash

Geohash é um sistema de geocódigo de domínio público inventado em 2008 por Gustavo Niemeyer e (trabalho semelhante em 1966) GM Morton, que codifica uma localização geográfica em uma curta sequência de letras e dígitos. É uma estrutura hierárquica de dados espaciais que subdivide o espaço em baldes de formato de grade , que é uma das muitas aplicações do que é conhecido como curva de ordem Z e , geralmente , curvas de preenchimento de espaço .

Geohashes oferecem propriedades como precisão arbitrária e a possibilidade de remover gradualmente caracteres do final do código para reduzir seu tamanho (e gradualmente perder a precisão). O geohashing garante que quanto mais longo for um prefixo compartilhado entre dois geohashes, mais próximos espacialmente eles ficarão. O inverso disso não é garantido, pois dois pontos podem estar muito próximos, mas ter um prefixo curto ou nenhum prefixo compartilhado.

História

A parte central do algoritmo Geohash e a primeira iniciativa de solução semelhante foi documentada em um relatório de GM Morton em 1966, "Uma base de dados geodésica orientada por computador e uma nova técnica em sequenciamento de arquivos". O trabalho de Morton foi usado para implementações eficientes da curva de ordem Z , como nesta moderna (2014) versão Geohash-inteiro , baseada na intercalação direta de inteiros de 64 bits . Mas sua proposta de geocódigo não era legível e não era popular.

Aparentemente, no final dos anos 2000, G. Niemeyer ainda não conhecia a obra de Morton e a reinventou, acrescentando o uso da representação base32 . Em fevereiro de 2008, juntamente com o anúncio do sistema, lançou o site http://geohash.org, que permite aos usuários converter coordenadas geográficas em URLs curtos que identificam posições de maneira única na Terra , para que seja mais conveniente referenciá-las em e - mails , fóruns e sites .

Muitas variações foram desenvolvidas, incluindo o link curto do OpenStreetMap (usando base64 em vez de base32) em 2009, o Geohash de 64 bits em 2014, o exótico Hilbert-Geohash em 2016 e outros.

Usos típicos e principais

Para obter o Geohash, o usuário fornece um endereço a ser geocodificado , ou coordenadas de latitude e longitude , em uma única caixa de entrada (os formatos mais usados ​​para pares de latitude e longitude são aceitos) e realiza a solicitação.

Além de mostrar a latitude e longitude correspondentes a determinado Geohash, os usuários que navegam para um Geohash em geohash.org também recebem um mapa embutido e podem baixar um arquivo GPX ou transferir o waypoint diretamente para determinados receptores GPS . Links também são fornecidos para sites externos que podem fornecer mais detalhes sobre o local especificado.

Por exemplo, o par de coordenadas 57.64911,10.40744(perto da ponta da península da Jutlândia, Dinamarca ) produz um hash ligeiramente mais curto de u4pruydqqvj.

Os principais usos dos geohashes são:

• Como um identificador único.
• Para representar dados pontuais, por exemplo, em bancos de dados.

Geohashes também foram propostos para serem usados ​​para geotagging .

Quando usada em um banco de dados, a estrutura de dados geohashed tem duas vantagens. Em primeiro lugar, os dados indexados por geohash terão todos os pontos de uma dada área retangular em fatias contíguas (o número de fatias depende da precisão necessária e da presença de "linhas de falha" do geohash). Isso é especialmente útil em sistemas de banco de dados onde as consultas em um único índice são muito mais fáceis ou mais rápidas do que as consultas com vários índices. Em segundo lugar, essa estrutura de índice pode ser usada para uma pesquisa de proximidade rápida e suja: os pontos mais próximos geralmente estão entre os geohashes mais próximos.

Descrição técnica

Uma descrição formal para vistas computacionais e matemáticas.

Representação textual

Para traduções exatas de latitude e longitude, Geohash é um índice espacial de base 4 , porque transforma as coordenadas espaciais contínuas de latitude e longitude em uma grade discreta hierárquica, usando uma quatro partições recorrentes do espaço. Para ser um código compacto ele usa a base 32 e representa seus valores pelo seguinte alfabeto, que é a "representação textual padrão".

O "alfabeto Geohash" (32ghs) usa todos os dígitos 0-9 e quase todas as letras minúsculas, exceto "a", "i", "l" e "o".

Por exemplo, usando a tabela acima e a constante , o Geohash pode ser convertido em uma representação decimal por notação posicional comum : ${\ displaystyle B = 32}$ezs42

[ ezs42] _{32 ghs} =${\ displaystyle [(e \ vezes B ^ {4}) + (z \ vezes B ^ {3}) + (s \ vezes B ^ {2}) + (4 \ vezes B ^ {1}) + (2 \ times B ^ {0})] _ {32ghs}}$

= ${\ displaystyle [e] _ {32ghs} \ times B ^ {4} + [z] _ {32ghs} \ times B ^ {3} + [s] _ {32ghs} \ times B ^ {2} + [4 ] _ {32ghs} \ times B ^ {1} + [2] _ {32ghs} \ times B ^ {0}}$

= ${\ displaystyle [13] _ {10} \ times B ^ {4} + [31] _ {10} \ times B ^ {3} + [24] _ {10} \ times B ^ {2} + [4 ] _ {10} \ vezes B ^ {1} + [2] _ {10} \ vezes B ^ {0}}$

= =${\ displaystyle 13 \ times 1048576 + 31 \ times 32768 + 24 \ times 1024 + 4 \ vezes 32 + 2 \ vezes 1}$${\ displaystyle 13631488 + 1015808 + 24576 + 128 + 2 = 14672002}$

Representação geométrica

A geometria do Geohash tem uma representação espacial mista:

• Geohashes com 2, 4, 6, ... e dígitos (dígitos pares ) são representados por uma curva de ordem Z em uma "grade regular" onde o par decodificado (latitude, longitude) tem incerteza uniforme, válido como Geo URI .
• Geohashes com 1, 3, 5, ... d dígitos (dígitos ímpares) são representados por "curva de ordem И". A latitude e a longitude do par decodificado têm incertezas diferentes (a longitude está truncada).

A curva da grade de 32 células foi obtida mesclando 2 por 2 células do "próximo nível" (grade de 64 células ilustrada aqui) para obter uma representação geométrica do "Geohash de dígitos ímpares".

É possível construir a "curva de ordem И" a partir da ordem Z mesclando células vizinhas e indexando a grade retangular resultante pela função j = floor ( i ÷ 2). A ilustração ao lado mostra como obter a grade de 32 células retangulares a partir da grade de 64 células quadradas.

A propriedade mais importante do Geohash para os humanos é que ele preserva a hierarquia espacial nos prefixos do código .
Por exemplo, na ilustração de "grade de 1 dígito Geohash" de 32 retângulos, acima, a região espacial do código e(retângulo de círculo azul acinzentado na posição 4,3) é preservada com o prefixo ena "grade de 2 dígitos" de 1024 retângulos (escala aparecendo eme círculos verdes acinzentados a azuis na grade).

Algoritmo e exemplo

Usando o hash ezs42como exemplo, aqui está como ele é decodificado em uma latitude e longitude decimal. O primeiro passo é decodificá-lo da " base 32ghs " textual , conforme mostrado acima, para obter a representação binária:

${\ displaystyle [e] _ {32ghs} = [13] _ {10} = [01101] _ {2}}$

${\ displaystyle [z] _ {32ghs} = [31] _ {10} = [11111] _ {2}}$

${\ displaystyle [s] _ {32ghs} = [24] _ {10} = [11000] _ {2}}$

${\ displaystyle [4] _ {32ghs} = [4] _ {10} = [00100] _ {2}}$

${\ displaystyle [2] _ {32ghs} = [2] _ {10} = [00010] _ {2}}$.

Essa operação resulta nos bits 01101 11111 11000 00100 00010 . Começando a contar do lado esquerdo com o dígito 0 na primeira posição, os dígitos nas posições ímpares formam o código da longitude ( 0111110000000), enquanto os dígitos nas posições pares formam o código da latitude ( 101111001001).

Cada código binário é então usado em uma série de divisões, considerando um bit de cada vez, novamente da esquerda para a direita. Para o valor de latitude, o intervalo -90 a +90 é dividido por 2, produzindo dois intervalos: -90 a 0 e 0 a +90. Como o primeiro bit é 1, o intervalo mais alto é escolhido e se torna o intervalo atual. O procedimento é repetido para todos os bits do código. Finalmente, o valor da latitude é o centro do intervalo resultante. As longitudes são processadas de forma equivalente, lembrando que o intervalo inicial é de -180 a +180.

Por exemplo, no código de latitude 101111001001, o primeiro bit é 1, portanto sabemos que nossa latitude está em algum lugar entre 0 e 90. Sem mais bits, adivinharíamos que a latitude era 45, resultando em um erro de ± 45. Como mais bits estão disponíveis, podemos continuar com o próximo bit, e cada bit subsequente divide esse erro pela metade. Esta tabela mostra o efeito de cada bit. Em cada estágio, a metade relevante do intervalo é destacada em verde; um bit baixo seleciona a faixa inferior, um bit alto seleciona a faixa superior.

A coluna "valor médio" mostra a latitude, simplesmente o valor médio do intervalo. Cada bit subsequente torna esse valor mais preciso.

(Os números na tabela acima foram arredondados para 3 casas decimais para maior clareza)

O arredondamento final deve ser feito com cuidado de forma que

${\ displaystyle \ min \ leq \ mathrm {round} (valor) \ leq \ max}$

Portanto, embora o arredondamento de 42,605 para 42,61 ou 42,6 seja correto, o arredondamento para 43 não é.

Dígitos e precisão em km

Limitações quando usado para decidir a proximidade

Casos extremos

Geohashes podem ser usados ​​para encontrar pontos próximos uns dos outros com base em um prefixo comum. No entanto, locais de casos extremos próximos uns dos outros, mas em lados opostos do meridiano de 180 graus, resultarão em códigos Geohash sem prefixo comum (longitudes diferentes para locais físicos próximos). Os pontos próximos aos pólos Norte e Sul terão geohashes muito diferentes (longitudes diferentes para localizações físicas próximas).

Duas localizações próximas em cada lado do Equador (ou meridiano de Greenwich) não terão um prefixo comum longo, uma vez que pertencem a diferentes 'metades' do mundo. Simplificando, a latitude (ou longitude) binária de um local será 011111 ... e o outro 100000 ..., portanto, eles não terão um prefixo comum e a maioria dos bits será invertida. Isso também pode ser visto como uma consequência de confiar na curva de ordem Z (que poderia ser mais apropriadamente chamada de visita de ordem N neste caso) para ordenar os pontos, já que dois pontos próximos podem ser visitados em momentos muito diferentes. No entanto, dois pontos com um prefixo comum longo estarão próximos.

Para fazer uma pesquisa de proximidade, pode-se calcular o canto sudoeste (geohash baixo com latitude e longitude baixas) e canto nordeste (geohash alto com latitude e longitude altas) de uma caixa delimitadora e pesquisar geohashes entre os dois. Esta pesquisa recuperará todos os pontos na curva de ordem z entre os dois cantos, que podem ser muitos pontos. Este método também se divide nos 180 meridianos e nos pólos. Solr usa uma lista de filtros de prefixos, calculando os prefixos dos quadrados mais próximos perto do geohash [1] .

Não-linearidade

Como um geohash (nesta implementação) é baseado em coordenadas de longitude e latitude, a distância entre dois geohashes reflete a distância em coordenadas de latitude / longitude entre dois pontos, o que não se traduz em distância real, consulte a fórmula de Haversine .

Exemplo de não linearidade para sistema de latitude-longitude:

• No Equador (0 Graus), o comprimento de um grau de longitude é 111,320 km, enquanto um grau de latitude mede 110,574 km, um erro de 0,67%.
• Em 30 graus (latitudes médias), o erro é 110,852 / 96,486 = 14,89%
• A 60 graus (Alto Ártico) o erro é 111,412 / 55,800 = 99,67%, atingindo o infinito nos pólos.

Observe que essas limitações não são devido ao geohashing, e não devido às coordenadas de latitude-longitude, mas devido à dificuldade de mapear as coordenadas em uma esfera (não linear e com agrupamento de valores, semelhante ao módulo aritmético) para coordenadas bidimensionais e o dificuldade de explorar um espaço bidimensional uniformemente. O primeiro está relacionado ao sistema de coordenadas geográficas e projeção do mapa , e o outro à curva de Hilbert e curva de ordem z . Uma vez que um sistema de coordenadas é encontrado que representa pontos linearmente em distância e quebra nas bordas, e pode ser explorado uniformemente, a aplicação de geohashing a essas coordenadas não sofrerá com as limitações acima.

Embora seja possível aplicar geohashing a uma área com um sistema de coordenadas cartesiano , ele só se aplicaria à área onde o sistema de coordenadas se aplica.

Apesar desses problemas, existem soluções alternativas possíveis e o algoritmo foi usado com sucesso no Elasticsearch, MongoDB, HBase, Redis e Accumulo para implementar pesquisas de proximidade.

Sistemas de indexação semelhantes

É possível usar os mesmos códigos base32-Geohash em diferentes curvas de indexação. Para os ladrilhos quadriláteros, a curva de Hilbert é a melhor alternativa para a curva de Morton , usada por exemplo na geometria S2.
Códigos com número par de dígitos (2, 4, ...) são mapeados para grades regulares, mas códigos de número ímpar (1, 3, ...) devem ser mapeados para uma grade intermediária irregular, com células indexadas por curvas degeneradas .

Uma alternativa para armazenar Geohashes como strings em um banco de dados são os códigos de localização , que também são chamados de chaves espaciais e semelhantes a QuadTiles.

Em alguns sistemas de informações geográficas e bancos de dados espaciais de Big Data , uma indexação baseada na curva de Hilbert pode ser usada como uma alternativa para a curva de ordem Z , como na biblioteca de geometria S2 .

Em 2019, um front-end foi desenvolvido pela QA Locate no que eles chamaram de GeohashPhrase para usar frases para codificar Geohashes para facilitar a comunicação por meio do idioma inglês falado. Havia planos para tornar o GeohashPhrase de código aberto.

Licenciamento

O algoritmo Geohash foi colocado em domínio público por seu inventor em um anúncio público em 26 de fevereiro de 2008.

Enquanto algoritmos comparáveis ​​foram patenteados com sucesso e tiveram direitos autorais reivindicados, GeoHash é baseado em um algoritmo e abordagem totalmente diferentes.

Veja também

• Lista de sistemas geodésico-geocodificação
• Geohash-36 (não é uma variante Geohash)
• Grade (índice espacial)
• Sistema Localizador Maidenhead
• Sistema de referência de rede militar
• Número de Morton (teoria dos números)
• Código de área natural
• Esquema de numeração
• Código de localização aberto (plus code)
• curvas de preenchimento de espaço
• what3words
• Curva de ordem Z

Referências

links externos

• Website oficial
• elasticsearch: o guia definitivo - Geo
• Aproximações geohash para geometrias JTS
• The Geohash Playground