Geohash es un sistema de geocodificación de dominio público inventado en 2008 por Gustavo Niemeyer [1] y (trabajo similar en 1966) GM Morton, [2] que codifica una ubicación geográfica en una pequeña cadena de letras y dígitos. Es una estructura jerárquica de datos espaciales que subdivide el espacio en cubos de forma de cuadrícula , que es una de las muchas aplicaciones de lo que se conoce como curva de orden Z y , en general , curvas de relleno de espacio .
Los geohashes ofrecen propiedades como precisión arbitraria y la posibilidad de eliminar gradualmente caracteres del final del código para reducir su tamaño (y perder precisión gradualmente). Geohashing garantiza que cuanto más largo sea un prefijo compartido entre dos geohashes, más cercanos espacialmente estarán. No se garantiza lo contrario, ya que dos puntos pueden estar muy cerca pero tienen un prefijo corto o no compartido.
Historia
La parte central del algoritmo Geohash y la primera iniciativa para una solución similar se documentó en un informe de GM Morton en 1966, "Una base de datos geodésica orientada por computadora y una nueva técnica en secuenciación de archivos". [2] El trabajo de Morton se utilizó para implementaciones eficientes de la curva de orden Z , como en esta versión moderna de Geohash-integer (2014) , basada en el entrelazado directo de enteros de 64 bits . Pero su propuesta de geocodificación no era legible por humanos y no era popular.
Aparentemente, a finales de la década de 2000, G. Niemeyer todavía no conocía el trabajo de Morton y lo reinventó, agregando el uso de la representación en base32 . En febrero de 2008, junto con el anuncio del sistema, [1] Se puso en marcha la página web http://geohash.org
, que permite a los usuarios convertir coordenadas geográficas a corto URL que identifican de forma única posiciones en la Tierra , por lo que la referencia a ellos en los correos electrónicos , foros y sitios web es más conveniente.
Se han desarrollado muchas variaciones, incluido el enlace corto de OpenStreetMap [3] (usando base64 en lugar de base32) en 2009, el Geohash de 64 bits [4] en 2014, el exótico Hilbert-Geohash [5] [6] en 2016, y otros.
Usos típicos y principales
Para obtener el Geohash, el usuario proporciona una dirección a geocodificar , o coordenadas de latitud y longitud , en un solo cuadro de entrada (se aceptan los formatos más utilizados para pares de latitud y longitud) y realiza la solicitud.
Además de mostrar la latitud y la longitud correspondientes al Geohash dado, los usuarios que navegan a un Geohash en geohash.org también se les presenta un mapa incrustado y pueden descargar un archivo GPX o transferir el waypoint directamente a ciertos receptores GPS . También se proporcionan enlaces a sitios externos que pueden proporcionar más detalles sobre la ubicación especificada.
Por ejemplo, el par de coordenadas 57.64911,10.40744
(cerca de la punta de la península de Jutlandia, Dinamarca ) produce un hash de u4pruydqqvj
.
Los principales usos de Geohashes son:
- Como identificador único.
- Para representar datos puntuales, por ejemplo, en bases de datos.
También se ha propuesto el uso de geohashes para geoetiquetado .
Cuando se utiliza en una base de datos, la estructura de los datos geohashed tiene dos ventajas. Primero, los datos indexados por geohash tendrán todos los puntos para un área rectangular dada en cortes contiguos (el número de cortes depende de la precisión requerida y la presencia de "fallas" de geohash). Esto es especialmente útil en sistemas de bases de datos donde las consultas en un solo índice son mucho más fáciles o más rápidas que las consultas de múltiples índices. En segundo lugar, esta estructura de índice se puede utilizar para una búsqueda de proximidad rápida y sucia: los puntos más cercanos se encuentran a menudo entre los geohashes más cercanos.
Descripción técnica
Una descripción formal para las vistas computacional y matemática.
Representación textual
Para traducciones exactas de latitud y longitud, Geohash es un índice espacial de base 4 , porque transforma las coordenadas espaciales continuas de latitud y longitud en una cuadrícula discreta jerárquica, utilizando una partición recurrente de cuatro del espacio. Para ser un código compacto utiliza la base 32 y representa sus valores mediante el siguiente alfabeto, que es la "representación textual estándar".
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 | mi | F | gramo | |||
Decimal | dieciséis | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | |||
Base 32 | h | j | k | metro | norte | pag | q | r | s | t | tu | v | w | X | y | z |
El "alfabeto Geohash" (32 ghs) utiliza todos los dígitos del 0 al 9 y casi todas las letras minúsculas excepto "a", "i", "l" y "o".
Por ejemplo, usando la tabla anterior y la constante , el Geohash ezs42
se puede convertir a una representación decimal mediante notación posicional ordinaria :
- [
ezs42
] 32 gh =
- =
- =
- = =
Representación geométrica
La geometría del Geohash tiene una representación espacial mixta:
- Geohashes con 2, 4, 6, ... e dígitos ( pares ) están representados por una curva de orden Z en una "cuadrícula regular" donde el par decodificado (latitud, longitud) tiene una incertidumbre uniforme, válida como Geo URI .
- Los geohashes con 1, 3, 5, ... d dígitos (dígitos impares) están representados por "curva de orden". La latitud y la longitud del par decodificado tienen una incertidumbre diferente (la longitud está truncada).
Es posible construir la "curva de orden И" a partir de orden Z fusionando celdas vecinas e indexando la cuadrícula rectangular de resultado por la función j = piso ( i ÷ 2). La ilustración lateral muestra cómo obtener la cuadrícula de 32 celdas rectangulares a partir de la cuadrícula de 64 celdas cuadradas.
La propiedad más importante de Geohash para los humanos es que conserva la jerarquía espacial en los prefijos de código .
Por ejemplo, en la ilustración "Cuadrícula de 1 dígito Geohash" de 32 rectángulos, arriba, la región espacial del código e
(rectángulo del círculo azul grisáceo en la posición 4,3) se conserva con el prefijo e
en la "Cuadrícula de 2 dígitos" de 1024 rectángulos. (muestra la escala em
y círculos de verde grisáceo a azul en la cuadrícula).
Algoritmo y ejemplo
Usando el hash ezs42
como ejemplo, así es como se decodifica en una latitud y longitud decimales. El primer paso es decodificarlo a partir del texto " base 32ghs ", como se muestra arriba, para obtener la representación binaria:
- .
Esta operación da como resultado los bits 01101
11111
11000
00100
00010
. Comenzando a contar desde el lado izquierdo con el dígito 0 en la primera posición, los dígitos en las posiciones impares forman el código de longitud ( 0111110000000
), mientras que los dígitos en las posiciones pares forman el código de latitud ( 101111001001
).
Luego, cada código binario se usa en una serie de divisiones, considerando un bit a la vez, nuevamente de izquierda a derecha. Para el valor de latitud, el intervalo de -90 a +90 se divide por 2, lo que produce dos intervalos: de -90 a 0 y de 0 a +90. Dado que el primer bit es 1, se elige el intervalo más alto y se convierte en el intervalo actual. El procedimiento se repite para todos los bits del código. Finalmente, el valor de latitud es el centro del intervalo resultante. Las longitudes se procesan de forma equivalente, teniendo en cuenta que el intervalo inicial es de -180 a +180.
Por ejemplo, en el código de latitud 101111001001
, el primer bit es 1, por lo que sabemos que nuestra latitud está entre 0 y 90. Sin más bits, supondríamos que la latitud es 45, lo que nos da un error de ± 45. Como hay más bits disponibles, podemos continuar con el siguiente bit, y cada bit subsiguiente reduce a la mitad este error. Esta tabla muestra el efecto de cada bit. En cada etapa, la mitad relevante del rango se resalta en verde; un bit bajo selecciona el rango inferior, un bit alto selecciona el rango superior.
La columna "valor medio" muestra la latitud, simplemente el valor medio del rango. Cada bit posterior hace que este valor sea más preciso.
Código de latitud 101111001001 | ||||||
---|---|---|---|---|---|---|
posición de bit | valor de bit | min | medio | max | valor medio | error máximo |
0 | 1 | -90.000 | 0.000 | 90.000 | 45.000 | 45.000 |
1 | 0 | 0.000 | 45.000 | 90.000 | 22.500 | 22.500 |
2 | 1 | 0.000 | 22.500 | 45.000 | 33.750 | 11.250 |
3 | 1 | 22.500 | 33.750 | 45.000 | 39.375 | 5.625 |
4 | 1 | 33.750 | 39.375 | 45.000 | 42.188 | 2.813 |
5 | 1 | 39.375 | 42.188 | 45.000 | 43.594 | 1.406 |
6 | 0 | 42.188 | 43.594 | 45.000 | 42.891 | 0,703 |
7 | 0 | 42.188 | 42.891 | 43.594 | 42.539 | 0.352 |
8 | 1 | 42.188 | 42.539 | 42.891 | 42.715 | 0,176 |
9 | 0 | 42.539 | 42.715 | 42.891 | 42.627 | 0.088 |
10 | 0 | 42.539 | 42.627 | 42.715 | 42.583 | 0.044 |
11 | 1 | 42.539 | 42.583 | 42.627 | 42.605 | 0,022 |
Código de longitud 0111110000000 | ||||||
---|---|---|---|---|---|---|
posición de bit | valor de bit | min | medio | max | valor medio | error máximo |
0 | 0 | -180.000 | 0.000 | 180.000 | -90.000 | 90.000 |
1 | 1 | -180.000 | -90.000 | 0.000 | -45.000 | 45.000 |
2 | 1 | -90.000 | -45.000 | 0.000 | -22.500 | 22.500 |
3 | 1 | -45.000 | -22.500 | 0.000 | -11.250 | 11.250 |
4 | 1 | -22.500 | -11.250 | 0.000 | -5.625 | 5.625 |
5 | 1 | -11.250 | -5.625 | 0.000 | -2,813 | 2.813 |
6 | 0 | -5.625 | -2,813 | 0.000 | -4.219 | 1.406 |
7 | 0 | -5.625 | -4.219 | -2,813 | -4,922 | 0,703 |
8 | 0 | -5.625 | -4,922 | -4.219 | -5.273 | 0.352 |
9 | 0 | -5.625 | -5.273 | -4,922 | -5.449 | 0,176 |
10 | 0 | -5.625 | -5.449 | -5.273 | -5.537 | 0.088 |
11 | 0 | -5.625 | -5.537 | -5.449 | -5.581 | 0.044 |
12 | 0 | -5.625 | -5.581 | -5.537 | -5.603 | 0,022 |
(Los números de la tabla anterior se han redondeado a 3 decimales para mayor claridad)
El redondeo final debe realizarse con cuidado de manera que
Entonces, si bien redondear 42.605 a 42.61 o 42.6 es correcto, redondear a 43 no lo es.
Dígitos y precisión en km
longitud geohash | bits lat | pedazos de lng | error lat | error de lng | error de km |
---|---|---|---|---|---|
1 | 2 | 3 | ± 23 | ± 23 | ± 2500 |
2 | 5 | 5 | ± 2,8 | ± 5,6 | ± 630 |
3 | 7 | 8 | ± 0,70 | ± 0,70 | ± 78 |
4 | 10 | 10 | ± 0.087 | ± 0,18 | ± 20 |
5 | 12 | 13 | ± 0.022 | ± 0.022 | ± 2,4 |
6 | 15 | 15 | ± 0,0027 | ± 0,0055 | ± 0,61 |
7 | 17 | 18 | ± 0,00068 | ± 0,00068 | ± 0.076 |
8 | 20 | 20 | ± 0,000085 | ± 0,00017 | ± 0.019 |
Limitaciones cuando se usa para decidir la proximidad
Casos de borde
Los geohashes se pueden utilizar para encontrar puntos próximos entre sí basándose en un prefijo común. Sin embargo, las ubicaciones de las cajas de borde cercanas entre sí pero en lados opuestos del meridiano de 180 grados darán como resultado códigos Geohash sin un prefijo común (longitudes diferentes para ubicaciones físicas cercanas). Los puntos cercanos a los polos norte y sur tendrán geohashes muy diferentes (longitudes diferentes para ubicaciones físicas cercanas).
Dos ubicaciones cercanas a ambos lados del ecuador (o meridiano de Greenwich) no tendrán un prefijo común largo ya que pertenecen a diferentes 'mitades' del mundo. En pocas palabras, la latitud (o longitud) binaria de una ubicación será 011111 ... y la otra 100000 ..., por lo que no tendrán un prefijo común y la mayoría de los bits se invertirán. Esto también puede verse como una consecuencia de confiar en la curva de orden Z (que podría llamarse más apropiadamente una visita de orden N en este caso) para ordenar los puntos, ya que dos puntos cercanos pueden ser visitados en momentos muy diferentes. Sin embargo, dos puntos con un prefijo común largo estarán cerca.
Para hacer una búsqueda de proximidad, se podría calcular la esquina suroeste (geohash bajo con latitud y longitud bajas) y la esquina noreste (geohash alto con latitud y longitud altas) de un cuadro delimitador y buscar geohashes entre esos dos. Esta búsqueda recuperará todos los puntos en la curva de orden z entre las dos esquinas, que pueden ser demasiados puntos. Este método también se descompone en los 180 meridianos y los polos. Solr usa una lista de filtro de prefijos, calculando los prefijos de los cuadrados más cercanos al geohash [1] .
No linealidad
Dado que un geohash (en esta implementación) se basa en coordenadas de longitud y latitud, la distancia entre dos geohashes refleja la distancia en coordenadas de latitud / longitud entre dos puntos, que no se traduce en la distancia real, consulte la fórmula de Haversine .
Ejemplo de no linealidad para el sistema latitud-longitud:
- En el Ecuador (0 grados) la longitud de un grado de longitud es de 111,320 km, mientras que un grado de latitud mide 110,574 km, un error de 0,67%.
- A 30 grados (latitudes medias) el error es 110,852 / 96,486 = 14,89%
- A 60 grados (Alto Ártico) el error es 111,412 / 55,800 = 99,67%, alcanzando el infinito en los polos.
Tenga en cuenta que estas limitaciones no se deben al geohashing ni a las coordenadas de latitud-longitud, sino a la dificultad de mapear coordenadas en una esfera (no lineal y con envoltura de valores, similar a la aritmética de módulo) a coordenadas bidimensionales y la dificultad de explorar un espacio bidimensional de manera uniforme. El primero está relacionado con el sistema de coordenadas geográficas y la proyección del mapa , y el otro con la curva de Hilbert y la curva de orden z . Una vez que se encuentra un sistema de coordenadas que representa puntos linealmente en la distancia y se envuelve en los bordes, y se puede explorar de manera uniforme, la aplicación de geohashing a esas coordenadas no sufrirá las limitaciones anteriores.
Si bien es posible aplicar geohashing a un área con un sistema de coordenadas cartesiano , solo se aplicaría al área donde se aplica el sistema de coordenadas.
A pesar de estos problemas, existen posibles soluciones y el algoritmo se ha utilizado con éxito en Elasticsearch, [7] MongoDB, [8] HBase, Redis, [9] y Accumulo [10] para implementar búsquedas de proximidad.
Sistemas de indexación similares
Una alternativa para almacenar Geohashes como cadenas en una base de datos son los códigos de ubicación , que también se denominan claves espaciales y son similares a QuadTiles. [11] [12]
En algunos sistemas de información geográfica y bases de datos espaciales de Big Data , se puede utilizar una indexación basada en la curva de Hilbert como alternativa a la curva de orden Z , como en la biblioteca de geometría S2 . [13]
En 2019, QA Locate [14] diseñó un front-end en lo que llamaron GeohashPhrase [15] para usar frases para codificar Geohashes para facilitar la comunicación a través del idioma inglés hablado. Había planes para hacer que GeohashPhrase fuera de código abierto. [dieciséis]
- Cuadrados C (2002)
- GeoKey (2018, propietario)
- Poste GPS de Ghana (2017)
- Sistema de localización de Maidenhead (1980)
- Código Makaney (2011)
- MapCode (2008)
- Sistema de referencia de cuadrícula militar
- Código de área natural
- Código de ubicación abierto (2014, también conocido como "códigos más", Google Maps )
- Localizador QRA (1959)
- Sistema de coordenadas universal transversal de Mercator
- what3words (2013, propietario)
- WhatFreeWords
- GEOREF (código de jerarquía similar de 2 dígitos)
- Xaddress
- 3Geonames (2018, código abierto)
Licencia
El algoritmo Geohash fue puesto en el dominio público por su inventor en un anuncio público el 26 de febrero de 2008. [17]
Si bien se han patentado con éxito algoritmos comparables [18] y se han reclamado derechos de autor, [19] [20] GeoHash se basa en un algoritmo y un enfoque completamente diferentes.
Ver también
- Lista de sistemas de geocodificación geodésica
- Geohash-36 (no es una variante de Geohash)
- Cuadrícula (índice espacial)
- Sistema de localización de Maidenhead
- Sistema de referencia de cuadrícula militar
- Número de Morton (teoría de números)
- Código de área natural
- Esquema de numeración
- Código de ubicación abierto (más código)
- curvas que llenan el espacio
- what3words
- Curva de orden Z
Referencias
- ^ a b Evidencias en la Wayback Machine :
- labix.org en 2008, el blog de G. Niemeyer que anuncia Geohash ;
- un artículo sobre Geohash atestiguando y citando trabajos de G. Niemeyer, antes de 2012 ;
- Publicación de G. Niemeyer en forums.geocaching.com anunciando Geohash en febrero de 2008 .
- Registros de 2008 de este artículo de Wikipedia, publicado por el usuario de G. Niemeyer : Gniemeyer . La página en los primeros registros de Wayback May y la primera versión en los registros de Wikipedia del 26 de febrero , declarando en la publicación del resumen "El algoritmo se ha puesto en dominio público" .
- ^ a b GM Morton (1966) "Una base de datos geodésica orientada por computadora y una nueva técnica en secuenciación de archivos" . Informe en IBM Canadá.
- ^ La OpenStreetMap 's enlace corto , documentado en wiki.openstreetmap.org , fue lanzado en 2009 , está cerca de la misma fuente de código 10 años después . Está fuertemente basado en el algoritmo entrelazado de Morton .
- ^ Los "64 bits binarios de Geohash" tienen soluciones clásicas, como yinqiwen / geohash-int , y soluciones optimizadas, como mmcloughlin / geohash-assembly .
- ^ Tibor Vukovic (2016), "Hilbert-Geohash - Hashing de datos de puntos geográficos utilizando la curva de llenado de espacio de Hilbert" . https://pdfs.semanticscholar.org/d23c/996f44b1443fca76276ce8d37239fb8fd6f9.pdf
- ^ https://github.com/tammoippen/geohash-hilbert
- ^ tipo de datos geo_shape en Elasticsearch
- ^ Indexación geoespacial en MongoDB
- ^ Guía de comandos de Redis
- ^ Indexación espacio-temporal en bases de datos distribuidas no relacionales
- ^ Teclas espaciales
- ^ QuadTiles
- ^ "Biblioteca de geometría S2" para la indexación espacial optimizada, https://s2geometry.io
- ^ "QA Locate | El poder de la inteligencia de ubicación de precisión" . QA Locate . Consultado el 10 de junio de 2020 .
- ^ "GeohashPhrase" . QA Locate . 2019-09-17 . Consultado el 10 de junio de 2020 .
- ^ thelittlenag (11 de noviembre de 2019). "En QA Locate hemos estado trabajando en una solución que llamamos GeohashPhrase | Hacker News" . news.ycombinator.com . Consultado el 10 de junio de 2020 .
- ^ Publicación de anuncio de geohash.org en el foro Groundspeak.com
- ^ Codificación de texto compacto de coordenadas de latitud / longitud - Patente 20050023524
- ^ ¿Microsoft infringe el sistema de codificación de áreas naturales? Archivado el 28 de diciembre de 2010 en la Wayback Machine.
- ^ El sistema de codificación de áreas naturales: legal y de licencias
enlaces externos
- Página web oficial
elasticsearch: la guía definitiva - Geo- Aproximaciones de Geohash para geometrías JTS
- El patio de juegos de Geohash