Latitud / Longitud de almacenamiento y compresión en C

Question

¿Alguien sabe la representación más eficiente para coordenadas lat / long? El nivel de precisión debería ser suficiente para los dispositivos GPS de consumo.

La mayoría de las implementaciones parecen usar double para cada unidad, pero sospecho que un float o un formato de punto fijo debería ser suficiente. Me gustaría saber de alguien que haya intentado comprimir o almacenar grandes conjuntos de estos valores.

EDITAR:

En otras palabras, ¿cuál es la precisión mínima requerida para representar lat / long para un dispositivo de nivel de consumidor?

Answer 1

Personalmente, usaría una representación de punto fijo decimal de 32 bits, dividida por 1,000,000 según la respuesta de Evan y mis comentarios.

Sin embargo, si el espacio es realmente premium, aquí hay algunas ideas adicionales:

• Podría usar una representación de punto fijo de 26 bits en el cable. Esto requerirá ordenar y desarmar la latitud y la longitud en una gran variedad de bytes, pero le ahorrará 12 bits para cada ubicación sobre la representación del valor de 32 bits, casi un ahorro del 19%, por lo que podría valer la pena.

• Podría aprovechar el hecho de que los valores de longitud necesitan menos precisión a medida que se acerca a los polos: solo necesitan 26 bits en el ecuador. Por lo tanto, podría escribir un esquema en el que el número de bits utilizados para codificar la longitud dependa del valor de la latitud.

• Si sus datos tienen otros atributos compresibles, por ejemplo, todos los puntos suelen estar bastante juntos, podría aprovecharlos específicamente, como usar un esquema de codificación delta (donde cada punto que no sea el primero puede codificarse) como un delta desde el último punto).

Answer 2

La circunferencia de la Tierra es de aprox. 40,000 km o 24900 millas.

Necesita una precisión de un metro (3 pies) para poder superar la precisión de los gps en un orden de magnitud.

Por lo tanto, necesita precisión para almacenar 40.000.000 valores diferentes. Eso es al menos 26 bits de información. Un float de 32 bits o int funcionará bien.

Answer 3

EDIT: agregó algunos puntos de los comentarios, los valores de 32 bits deberían ser capaces de ofrecer suficiente precisión.

Usaría una representación de punto fijo de 32 bits. Si los valores son:

42.915512 , -99.521654 Almacenaría los valores * 100000 en int32_t 's (pueden ser negativos).

int32_t lat = 42915512;
int32_t lon = -99521654;

Este es un buen compromiso entre lo simple y lo preciso ( 5 los puntos decimales suelen ser lo suficientemente buenos, siempre puede aumentarlo a 1000000 para obtener 6 si es necesario).

Para mostrar al usuario, haga lo que caf sugiere:

  

... para mostrar al usuario - use entero   dividir y módulo, por ejemplo printf (" Lat =   % d.% 06d \ n '', lat / 1000000, abs (lat)%   1000000)

Estos también serán comparables / clasificables de manera eficiente ya que se preservará el orden relativo.

EDITAR: un beneficio adicional es que puede enviarse a través de una red o almacenarse en disco en formato binario de forma portátil.

Answer 4

Los flotadores serían mucho más que suficientes para almacenar coordenadas GPS, incluso si los dispositivos GPS de nivel de consumidor tuvieran alguna precisión cercana a la requerida. Si no cree que esto sea cierto, pruebe estos dos experimentos simples:

1. Tome dos o más dispositivos GPS en un punto en un campo en algún lugar y anote las coordenadas medidas por cada dispositivo. Vuelva adentro y trace los puntos de cada dispositivo en un mapa (creo que Google tiene algo que hace esto por usted). Te sorprenderá la distancia que separan los puntos (aunque se supone que todos miden exactamente el mismo punto).
2. Tome su dispositivo (supuestamente) más preciso y colóquelo en algún lugar donde pueda obtener una reparación satelital, pero no lloverá, y registre una serie de mediciones tomadas en un par de días. Trace todas las lecturas (como en el n. ° 1). Nuevamente, se sorprenderá de cómo los puntos (que deberían ser todos iguales o casi iguales) vagan por todo el mapa, a veces hasta unos cientos de pies.

He estado escribiendo aplicaciones para PDA con GPS durante años, y lo he verificado para clientes dudosos una y otra vez (incluso he ganado apuestas de esta manera). Hay dispositivos GPS de mayor calidad que logran una precisión mejor que esta, pero la mejor precisión se logra con conjuntos de chips más caros, y los dispositivos se dejan en un solo lugar durante días o incluso semanas, con un promedio de las lecturas a lo largo del tiempo. / p>

Un flotante de cuatro bytes es mucho más preciso que los dispositivos mismos . Por supuesto, no le haría ningún daño usar un doble, siempre que el factor 2X no sea un problema para usted.

Answer 5

23 bits de precisión a 179 grados de longitud da menos de 10 metros de precisión, que es lo mejor que ofrecen los dispositivos GPS comunes. En el ecuador:

% gps distance "0.0, 179.0" "0.0, $((179 * (1 + 2**-23)))"
From 0.0, 179.0 to 0.0, 179.00002133846283 is 7.79 feet E
From 0.0, 179.0 to 0.0, 179.00002133846283 is 2.38 meters E

Entonces, un número de coma flotante de precisión simple IEEE 754, conocido por su compilador de C como float , será adecuado para la representación. ¡Cuidado con el uso de flotadores para cálculos extendidos! El error de redondeo puede comer su almuerzo. Consulte a un analista numérico.

Answer 6

En el formato de mapa IMG de Garmin, almacenan las coordenadas dentro de los cuadros delimitadores utilizando flotadores para establecer los bordes de los cuadros. Las coordenadas dentro de los cuadros se definen utilizando un número variable de bits que son lineales entre los valores mínimo y máximo, según la precisión necesaria.

Por ejemplo: minlat = 49.0, maxlat = 50.0, minlon = 122.0, maxlon = 123.0, número de bits = 16

Entonces un valor de:
32768,32768 se convertiría a 49.5, 122.5
16384,0 sería 49.25, 122.0

Si necesita menos precisión, se podría generar la misma salida con varios bits = 4
8,8 se convertirían a 49,5, 122,5
4,0 sería 49.25, 122.0

Answer 7

Si está almacenando grandes matrices de estos valores, existen algunos trucos simples si realiza una compresión delta y almacena deltas, puede reducir en gran medida el tamaño de una secuencia de datos. Puede hacer deltas desde un " punto clave "

K D D D D D D D D D D K D D D D ...

k + d te lleva a cualquier punto d

Todos los deltas hacen referencia a la K anterior, por lo que para reconstruir cualquier punto, necesita una K y una D

o puedes hacer deltas incriminales

K I I I I I I I I I I K

Esto puede tomar varias sumas para llegar a la posición deseada. pero los datos son más pequeños en general. SO para reconstruir

k + i + i + i para llegar al cuarto punto

Finalmente puedes combinar ambos

K D I I I D I I I D I I I K

Esto es como mpeg-2 con marcos IPB, pero de esta manera nunca tendrá más de 4 sumas en cualquier posición, y obtendrá algunos de los beneficios de Delta y Compresión Incrimental.

Answer 8

Puede empaquetar los valores de latitud y longitud en un entero de 32 bits con una resolución de al menos ~ 2,4 metros / píxel (en el ecuador) si Utiliza un sistema de mosaico recursivo. Usando dos bits por nivel, puede almacenar 16 niveles en 32 bits. Puede hacerse una idea de cómo funcionaría esto mirando este artículo sobre Mosaico de Virtual Earth sistema . Esto usa Mercator, por lo que le daría problemas para los polos. En su lugar, podría usar una proyección diferente y aún así obtener resultados muy similares.

Esto también se puede usar para un filtro aproximado para encontrar cualquier punto dentro de un mosaico principal dado, ya que los primeros N bits serán los mismos (y la búsqueda se convierte en enmascaramiento de bits).

Answer 9

Suponiendo que la Tierra es una esfera perfecta (no lo es, pero lo suficientemente cerca) con un radio 'R' de 3959 millas (o × 5280 pies / mi = 20903520 pies), la circunferencia es 131340690 pies (usando 2 × PI × R).

360 grados de longitud cubren 131340690 pies. 180 grados de latitud cubren 65670345 pies.

Si desea almacenar lat / lng con una precisión de 3 pies, debe poder almacenar 43780230 (131340690/3) valor de longitud y 21890115 (65670345/3) valores de latitud. 43780230 requiere 25.38 bits (log (43780230) / log (2)) para almacenar y 21890115 requiere 24.38 bits (log (21890115) / log (2)) para almacenar, o un poco menos de 50 bits (o 6.25 bytes).

Entonces, la pregunta obvia es: si desea almacenar la latitud y la longitud en solo 6 bytes, ¿cuál será la precisión? Bueno, 6 bytes son 48 bits. Eso significa 23.5 bits para la latitud y 24.5 bits para la longitud (la longitud tiene el doble de valores, que es solo un bit y 24.5-23.5 = 1 bit). Entonces, 23.5 bits le permite representar un número de 0 a 11863282 (valores de 11863283). Y 65670345 pies divididos por 11863283 valores son 5.53 pies (y el mismo valor de precisión para la longitud).

LA LÍNEA INFERIOR: Entonces, si puede vivir con 5.5 pies de precisión para latitud y longitud, puede empaquetar ambos valores en solo seis bytes.

* UNA NOTA LATERAL: Con respecto a los comentarios de que la latitud y la longitud son horribles para almacenar la información posicional alrededor de una esfera (porque hay menos información para almacenar en los polos), bueno, ¡esos comentarios no son compatibles con las matemáticas! Vamos a resolverlo. Digamos que queremos diseñar un nuevo sistema perfecto que pueda grabar y colocar una estaca en el suelo en el centro de cada pie cuadrado de tierra. El área de superficie de la tierra (con una R de 3959 millas; fórmula para el área de superficie de una esfera) es 5490965469267303 SQ FT: muchas apuestas requieren 52.29 bits para representar. Ahora el sistema de latitud y longitud existente usa un sistema rectangular. El ancho del rectángulo es la circunferencia de la tierra y la altura del rectángulo es 1/2 de la circunferencia), que es 131340690 * 65670345 (ver más arriba), o 8625188424838050 SQ FT - que requiere 52.94 bits para representar (este sistema coloca 'demasiadas' estacas en el suelo alrededor de los polos). Entonces, la respuesta sorprendente es que tanto el nuevo sistema perfecto como el antiguo sistema lat / lng, ¡AMBOS requerirían 53 bits reales para almacenar una sola ubicación en la tierra, con una precisión de hasta 1 pie!

Answer 10

Me sorprende que nadie haya publicado el hecho de que long / lat es una forma terrible de almacenar datos en una esfera (alguien mencionó que la longitud requiere menos precisión cerca de los polos).

Básicamente puede almacenar la posición de datos como coordenadas X e Y en metros. Imagina un cubo alrededor de la tierra que se ajusta exactamente (jaja ok casi se ajusta). Solo necesita almacenar la posición X e Y, no las 3 coordenadas, porque la 3ª coordinación puede provenir del redius de la tierra, r = raíz cuadrada [x ^ 2 + y ^ 2 + z ^ 2] .

Entonces convierta su lat / long a x / y en metros. Solo necesitará un total de 12756200m por coordenada (es decir, los diámetros de la tierra). Por lo tanto, su valor total solo tendrá que abarcar de 0 a 25,512,400 (alguien más reclamó 40,000,000 porque estaban usando long / lat) para tener una precisión de +/- 0.5m.

Eso dará como resultado solo 25 bits por posición. Si yo fuera usted, solo haría una precisión de 2m y usaría 24 bits por posición, ya que eso es un orden de 3 bytes.

Además, si está almacenando información de punto de ruta en una ruta, puede almacenar cada punto de ruta como un desplazamiento desde el último punto de ruta. Como comenzar con una coordenada x / y de 24 bits. Y luego tenga una 'actualización' de 16 bits que ajuste la posición sumando / restando x / y metros. 16 bits permitirían una actualización de waypoint a más de 400 m de distancia. Entonces, si sabe que el dispositivo no está diseñado para aviones y actualizaciones de vez en cuando, esto también podría ser aceptable.