Latitude de armazenamento / Longitude e compressão em C

Question

Alguém sabe a representação mais eficiente para Lat Long coordenadas /? nível de precisão deve ser suficiente para o consumidor dispositivos GPS.

A maioria das implementações parecem usar double para cada unidade, mas estou desconfiado de que um float ou formato de ponto fixo deve ser suficiente. Eu seria curioso para ouvir de ninguém que tenha tentado comprimir e ou armazenar grandes conjuntos de esses valores.

EDIT:

Em outras palavras, o que é a precisão mínima exigida para representar latitude / longitude para um dispositivo nível do consumidor?

Answer 1

Pessoalmente, eu usaria uma representação decimal ponto fixo de 32 bits, dividindo-se por 1.000.000 de acordo com a resposta de Evan e os meus comentários.

No entanto, se o espaço é realmente um prêmio, aqui estão algumas ideias adicionais:

• Você pode usar uma representação de ponto fixo de 26 bits no fio. Isso vai exigir de triagem e unmarshalling a latitude e longitude em uma grande variedade de bytes, mas você vai economizar 12 bits para cada local sobre a representação valor de 32 bits -. Quase uma poupança de 19%, por isso pode muito bem valer a pena

• Você pode tirar proveito do fato de que os valores de longitude precisa de menos precisão como você chegar mais perto dos pólos - eles só precisam de 26 bits pena no equador. Então, você poderia escrever um esquema em que o número de bits usado para codificar a longitude depende do valor da latitude.

• Se os dados tem outros atributos compressíveis - digamos, todos os pontos são geralmente muito próximas umas das outras - você poderia tirar proveito específico daqueles, como usar um delta esquema de codificação (onde cada ponto diferente do primeiro pode ser codificado como um delta a partir do último ponto).

Answer 2

A circunferência da Terra é de aprox. 40,000 km ou 24900 milhas.

Você precisa de precisão de um metro (três pés) para ser capaz de fora-resolve gps de precisão por uma ordem de magnitude.

Por isso você precisa precisiton para armazenar 40.000.000 valores diferentes. Isso é, no mínimo, 26 bits de informação. Um flutuador 32 bits ou int vai fazer bem.

Answer 3

EDIT:. acrescentados alguns pontos de comentários, valores de 32 bits deve ser capaz de oferecer precisão suficiente

Gostaria de usar uma representação de ponto fixo de 32 bits. Se os valores são:

42.915512, -99.521654 eu iria armazenar o values * 100000 em O int32_t (que pode ser negativo).

int32_t lat = 42915512;
int32_t lon = -99521654;

Este é um bom compromisso entre simples e precisa ( 5 pontos decimais é geralmente bom o suficiente, você poderia sempre galo-lo até 1000000 para obter 6 se necessário).

Para exibir para o usuário, fazer o que caf sugere:

... para exibir para o usuário - o uso inteiro dividir e modulo, por exemplo printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)

Estes também serão comparáveis ??/ classificáveis ??de forma eficiente uma vez que a ordem relativa será preservada.

EDIT:. um benefício adicional é que ele pode enviados por uma rede ou armazenado em disco em um formato binário de uma forma portátil

Answer 4

flutua seria a maneira mais do que suficiente para armazenar as coordenadas do GPS, mesmo em nível de consumidor dispositivos GPS teve qualquer lugar perto da precisão exigido para eles. Se você não acredita que isso é verdade, tente estas duas experiências simples:

1. Tome dois ou mais dispositivos de GPS para fora em um ponto em um algum lugar campo, e anotar as coordenadas medidas por cada dispositivo. Volte para dentro e traçar os pontos de cada dispositivo em um mapa (eu acho que o Google tem algo que faz isso para você). Você vai ficar surpreso com o quão distantes os pontos são (embora todos eles são suposto ser medir exatamente o mesmo local).
2. Leve o seu (supostamente) dispositivo mais preciso, e colocá-lo em algum lugar onde ele pode obter uma correção via satélite, mas não vai ficar choveu, e gravar uma série de medidas tomadas ao longo de um par de dias. Traçar todas as leituras (como em # 1). Mais uma vez, você vai ser surpreendido pela forma como os pontos (que devem ser todos do mesmo ou quase o mesmo) vagar por todo o mapa, às vezes por tanto como um par cem pés.

Eu tenho escrito aplicações para PDAs GPS habilitados por anos, e eu tenho verificado isso para clientes duvidosos uma e outra vez (Eu mesmo ganhou apostas desta forma). Há mais de alta qualidade dispositivos GPS lá fora que conseguir uma melhor precisão do que isso, mas a melhor precisão é conseguido com chipsets mais caros, e os dispositivos são deixados em um local por dias ou mesmo semanas, com as leituras em média ao longo do tempo.

A quatro bytes float é muito mais preciso do que os próprios dispositivos . Seria, claro, não feri-lo em tudo para usar um casal em vez, desde que o fator 2X não é um problema para você.

Answer 5

23 bits de precisão em 179 graus de longitude dá sob precisão de 10 metros, que é o melhor que os dispositivos GPS comuns dar. No equador:

% 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

Assim, um número de ponto flutuante 754 de precisão única IEEE, conhecido por seu compilador C como float, wil ser apenas adequado para a representação. Cuidado ao usar flutuadores para computações prolongadas! Arredondamento de erro pode comer o seu almoço. Consulte um analista numérica.

Answer 6

formato de mapa IMG do Em Garmin eles armazenam coordenadas dentro delimitadora caixas usando carros alegóricos para definir as bordas das caixas. Coordenadas dentro das caixas são definidas utilizando um número variável de bits que são são apenas linear entre valores mínimo e máximo, dependendo da precisão necessária.
Por exemplo: minlat = 49,0, maxlat = 50,0, Minlon = 122,0, maxlon = 123,0, número de bits = 16

Assim, um valor de:
32768,32768 seria convertido para 49,5, 122,5
16384,0 seria 49,25, 122,0

Se você precisa de menos precisão, o mesmo resultado poderia ser gerado com um número de bits = 4
8,8 seria convertido para 49,5, 122,5
4,0 seria 49,25, 122,0

Answer 7

Se você está armazenando grandes conjuntos de estes valores, existem alguns truques simples, se você fizer uma compressão delta, e armazenar deltas, você pode reduzir significativamente o tamanho de um fluxo de dados. Você pode fazer deltas de um "ponto-chave"

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

k + d levá-lo a qualquer ponto d

Os deltas toda referência a anterior K, de modo a reconstruir qualquer ponto, você precisa de um K e D

ou você pode fazer incrimental deltas

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

Este processo pode demorar várias somas para chegar à posição desejada. mas os dados é menor geral. SO para reconsturct

k + i + i + i para chegar ao quarto ponto

Finalmente, você pode combinar os dois

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

Isto é como MPEG-2 com quadros IPB, mas desta forma você nunca são mais de 4 somas para qualquer posição, e você começa a alguns dos benefícios da Delta e Incrimental Compression.

Answer 8

Você pode embalar tanto a latitude e longitude valores em um único 32-bit inteiro com uma resolução de pelo pior ~ 2,4 metros / pixel (no equador) se você usa um sistema de azulejos recursiva. Usando dois bits por nível, você pode armazenar 16 níveis em 32 bits. Você pode ter uma idéia de como isso funciona olhando para este artigo sobre azulejos Virtual da Terra sistema. Este usa Mercator, por isso lhe daria problemas para os pólos. em vez disso você pode usar uma projeção diferente e ainda obter resultados muito semelhantes.

Isto pode também ser usado para um filtro áspero para encontrar quaisquer pontos dentro de um determinado telha pai desde os primeiros N bits será o mesmo (e assim pesquisa torna-se mascaramento bit).

Answer 9

Assumindo que a Terra é uma esfera perfeita (não é, mas perto o suficiente) com um raio 'R' de 3959 milhas (ou × 5280 pés / mi = 20.903.520 pés), a circunferência é 131340690 pés (usando 2 × PI × R).

360 graus de longitude cobre 131340690 pés. 180 graus de latitude tampas 65670345 pés.

Se você deseja armazenar latitude / longitude para baixo com uma precisão de 3 pés, você precisa ser capaz de armazenar 43.780.230 valor (131340690/3) longitude e 21890115 (65670345/3) valores de latitude. 43780230 requer 25,38 pedaços (log (43780230) / log (2)) para armazenar e 21890115 requer 24.38 bits (log (21890115) / log (2)) para armazenamento - ou um pouco menos de 50 bits (ou 6,25 bytes)

Assim, a pergunta óbvia torna-se, se você deseja armazenar latitude e longitude em apenas 6 bytes, o que a precisão seja? Bem, 6 bytes é 48 bits. Isso significa que 23,5 bits para latitude e longitude 24,5 bits para (longitude possui o dobro de valores, que é apenas um pouco e 24,5-23,5 = 1 bit). Assim, 23,5 pedaços permite representar um número de 0 a 11863282 (11863283 valores). E 65670345 pés divididos por 11863283 valores é 5,53 pés (e o mesmo valor de precisão para longitude).

A linha inferior:. Então, se você pode viver com 5,5 pés de precisão tanto para latitude e longitude, você pode embalar ambos os valores em apenas seis bytes

* A SIDE NOTA: Quanto comentários que latitude e longitude são horríveis para armazenar as informações de posição em torno de uma esfera (porque há menos informação para armazenar nos pólos) - bem, esses comentários não armazenar até a matemática! A figura de deixá-lo fora. Digamos que quer projetar um novo sistema perfeito que pode gravar e colocar uma estaca no chão no centro de cada pé quadrado de terra. A área de superfície da Terra (com um R de 3959 milhas; fórmula para a área da superfície de uma esfera) é 5490965469267303 SQ FT - que muitas estacas requer 52,29 bits para representar. Agora, o sistema de latitude e longitude existente usa um sistema retangular. A largura do rectângulo é a circunferência da terra, e a altura do rectângulo é 1/2 da circunferência) - que é * 131340690 65670345 (ver muito acima), ou 8625188424838050 SQ FT - o que requer 52,94 bits para representar (estes locais do sistema 'muitos' estacas no chão em torno dos pólos). Portanto, a resposta chocante é que tanto o novo sistema perfeito, e o antigo sistema / lng lat, que ambos exigem 53 bits de reais para armazenar um único lugar da Terra, até a precisão de 1 pé!

Answer 10

Estou surpreso que ninguém publicou o fato de que long / lat é uma péssima maneira de armazenar dados em uma esfera (alguém fez menção de que longitude exige menos precisão perto dos pólos).

Basicamente, você pode armazenar posição de dados como X e Y co-ords em metros. Imagine um cubo em torno da Terra que exactally fits (haha ok quase se encaixa-lo). Só é necessário armazenar X e Y posição, não todos os 3 co-ords, porque a co-ord 3-estr pode vir do redius da terra, r = raiz quadrada [x ^ 2 + y ^ 2 + z ^ 2] .

Assim converter sua latitude / longitude para X / Y em metros. Você só vai precisar de um total de 12756200m por co-ord (que é o diâmetro da Terra). Portanto, o seu valor total, apenas terão de extensão 0 a 25.512.400 (alguém reivindicou 40.000.000 porque eles estavam usando long / lat) para ter uma precisão de +/- 0,5 m.

Isso vai resultar em apenas 25 bits por posição. Se eu fosse você eu iria apenas fazer precisão para dentro de 2m e usar 24 bits por posição, como é que um arrumado 3 bytes.

Além disso, se você estiver armazenando informações waypoint em um caminho, você pode armazenar cada waypoint como uma compensação a partir do último ponto de passagem. Como começar com um co-ord 24bit x / y. E, em seguida, ter um 'update' 16bit que ajusta a posição adicionando / subtraindo x / y metros. 16bit permitiria uma atualização waypoint a ser mais de 400m de distância. Então, se você souber que o dispositivo não é para aviões e atualiza a cada tantas vezes, isso pode ser aceitável também.