Geohash

Geohash es un sistema de geocodificación de dominio público inventado en 2008 por Gustavo Niemeyer ^[1] que codifica una ubicación geográfica en una cadena corta de letras y dígitos. GM Morton introdujo ideas similares en 1966. ^[2] Es una estructura de datos espaciales jerárquica que subdivide el espacio en cubos con 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 que llenan el 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). El geohashing garantiza que cuanto más largo sea el prefijo compartido entre dos geohashes, más cerca estarán espacialmente. Lo inverso no está garantizado, ya que dos puntos pueden estar muy cerca pero tener un prefijo compartido corto o ninguno.

La parte central del algoritmo Geohash y la primera iniciativa para una solución similar se documentaron en un informe de GM Morton en 1966, "Una base de datos geodésica orientada a 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 (2014) de Geohash-entero (basada en el entrelazado directo de enteros de 64 bits ), pero su propuesta de geocodificación no era legible para humanos y no fue popular.

Al parecer, a finales de los años 2000, G. Niemeyer aún no conocía el trabajo de Morton, y lo reinventó, añadiendo el uso de la representación en base32 . En febrero de 2008, junto con el anuncio del sistema, ^[1] lanzó el sitio web http://geohash.org, que permite a los usuarios convertir coordenadas geográficas en URL cortas que identifican de forma única posiciones en la Tierra , de modo que sea más cómodo hacer referencia a ellas en correos electrónicos , foros y sitios web .

Se han desarrollado muchas variaciones, incluido el enlace corto de OpenStreetMap ^[3] (que utiliza base64 en lugar de base32) en 2009, el Geohash de 64 bits ^[4] en 2014, el exótico Hilbert-Geohash ^[5] en 2016 y otros.

Para obtener el Geohash, el usuario proporciona una dirección a geocodificar , o coordenadas de latitud y longitud , en un único cuadro de entrada (se aceptan los formatos más comúnmente utilizados para pares de latitud y longitud), y realiza la solicitud.

Además de mostrar la latitud y longitud correspondientes al Geohash indicado, a los usuarios que accedan a un Geohash en geohash.org también se les presenta un mapa integrado y pueden descargar un archivo GPX o transferir el punto de referencia 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 ligeramente más corto de u4pruydqqvj.

Los principales usos de los Geohashes son:

• Como identificador único.
• Para representar datos puntuales, por ejemplo en bases de datos.

También se ha propuesto utilizar geohashes para geoetiquetado .

Cuando se utiliza en una base de datos, la estructura de datos geohash tiene dos ventajas. En primer lugar, los datos indexados por geohash tendrán todos los puntos de un área rectangular dada en porciones contiguas (la cantidad de porciones depende de la precisión requerida y de la presencia de "líneas de falla" 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 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 a menudo se encuentran entre los geohashes más cercanos.

Una descripción formal para las vistas computacionales y matemáticas.

Para traducciones exactas de latitud y longitud Geohash es un índice espacial de base 4 , ya que transforma las coordenadas espaciales continuas de latitud y longitud en una cuadrícula discreta jerárquica, utilizando una partición recurrente en 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".

El "alfabeto Geohash" (32ghs) utiliza todos los dígitos del 0 al 9 y todas las letras minúsculas excepto "a", "i", "l" y "o".

Por ejemplo, utilizando la tabla anterior y la constante , el Geohash se puede convertir a una representación decimal mediante notación posicional ordinaria : ${\estilo de visualización B=32}$ezs42

[ ezs42] _32ghs =${\displaystyle [(e\times B^{4})+(z\times B^{3})+(s\times B^{2})+(4\times 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}\times B^{1}+[2]_{10}\times B^{0}}$

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

La geometría del Geohash tiene una representación espacial mixta:

• Los geohashes con 2, 4, 6, ... dígitos ( dígitos pares ) se representan mediante 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) se representan mediante una "curva de orden E". La latitud y la longitud del par decodificado tienen una incertidumbre diferente (la longitud se trunca).

Es posible construir la "curva de orden И" a partir de la curva de orden Z fusionando celdas vecinas e indexando la cuadrícula rectangular resultante mediante la función . La ilustración muestra cómo obtener la cuadrícula de 32 celdas rectangulares a partir de la cuadrícula de 64 celdas cuadradas. ${\displaystyle j=\left\lfloor {\frac {i}{2}}\right\rfloor }$

La propiedad más importante de Geohash para los humanos es que preserva la jerarquía espacial en los prefijos del código .
Por ejemplo, en la ilustración de la "cuadrícula de 1 dígito de Geohash" de 32 rectángulos, arriba, la región espacial del código e(rectángulo de círculo azul grisáceo en la posición 4,3) se preserva con el prefijo een la "cuadrícula de 2 dígitos" de 1024 rectángulos (la escala muestra emcírculos de color verde grisáceo a azul en la cuadrícula).

Usando el hash ezs42como ejemplo, aquí se muestra cómo se decodifica en una latitud y longitud decimal. El primer paso es decodificarlo a partir de la "base 32ghs" textual, como se muestra arriba, para obtener la representación binaria:

${\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}}$.

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 pares forman el código de longitud ( 0111110000000), mientras que los dígitos en las posiciones impares forman el código de latitud ( 101111001001).

Cada código binario se utiliza entonces en una serie de divisiones, considerando un bit a la vez, nuevamente desde el lado izquierdo al derecho. 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. Como 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 manera 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á en algún lugar 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.

(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

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

Si bien redondear 42,605 a 42,61 o 42,6 es correcto, redondear a 43 no lo es.

Los geohashes se pueden utilizar para encontrar puntos próximos entre sí basándose en un prefijo común. Sin embargo, las ubicaciones de casos extremos cercanas entre sí, pero en lados opuestos del meridiano de 180 grados, darán como resultado códigos Geohash sin 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 lugares cercanos 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 binaria (o longitud) de un lugar será 011111... y la del otro 100000...., por lo que no tendrán un prefijo común y la mayoría de los bits estarán invertidos. 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 podrían ser visitados en momentos muy diferentes. Sin embargo, dos puntos con un prefijo común largo estarán cerca.

Para realizar 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 falla en los 180 meridianos y los polos. Solr utiliza una lista de filtros de prefijos, calculando los prefijos de los cuadrados más cercanos al geohash [1].

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, lo que no se traduce en 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 111,320 km, mientras que un grado de latitud mide 110,574 km, un error del 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%, llegando al infinito en los polos.

Tenga en cuenta que estas limitaciones no se deben al geohashing ni a las coordenadas de latitud y longitud, sino a la dificultad de mapear coordenadas en una esfera (no lineal y con envoltura de valores, similar a la aritmética módulo) a coordenadas bidimensionales y la dificultad de explorar un espacio bidimensional de manera uniforme. La primera está relacionada con el sistema de coordenadas geográficas y la proyección de mapas , y la otra 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 del geohashing a esas coordenadas no sufrirá las limitaciones anteriores.

Si bien es posible aplicar geohashing a un área con un sistema de coordenadas cartesianas , entonces solo se aplicaría al área donde se aplica el sistema de coordenadas.

A pesar de estos problemas, existen posibles soluciones alternativas y el algoritmo se ha utilizado con éxito en Elasticsearch, ^[6] MongoDB, ^[7] HBase, Redis, ^[8] y Accumulo ^[9] para implementar búsquedas de proximidad.

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 los QuadTiles. ^{[10] [11]}

En algunos sistemas de información geográfica y bases de datos espaciales de Big Data , se puede utilizar una indexación basada en una curva de Hilbert como alternativa a una curva de orden Z , como en la biblioteca S2 Geometry . ^[12]

^{En 2019, QA Locate [13]} diseñó una interfaz llamada GeohashPhrase ^[14] para codificar Geohashes mediante frases y facilitar la comunicación a través del idioma inglés hablado. Había planes para que GeohashPhrase fuera de código abierto. ^[15]

El algoritmo Geohash fue puesto en el dominio público por su inventor en un anuncio público el 26 de febrero de 2008. ^[16]

Si bien se han patentado con éxito algoritmos comparables ^[17] y se han reclamado derechos de autor sobre ellos, ^{[18] [19]} GeoHash se basa en un algoritmo y un enfoque completamente diferentes.

Geohash está estandarizado como CTA-5009. ^[20]   Este estándar sigue el artículo de Wikipedia a partir de la versión 2023, pero proporciona detalles adicionales en una referencia formal (normativa). En ausencia de una especificación oficial desde la creación de Geohash, la organización CTA WAVE publicó CTA-5009 para ayudar a una adopción y compatibilidad más amplia entre los implementadores de la industria.

• 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 abierta (más código)
• curvas que llenan el espacio
• ¿Qué tres palabras?
• Curva de orden Z

• Sitio web oficial
• Aproximaciones de geohash para geometrías JTS
• El patio de juegos de Geohash