Stockage de latitude / longitude et compression en C

Question

Est-ce que quelqu'un connaît la représentation la plus efficace pour les coordonnées lat / long? Le niveau de précision devrait être suffisant pour les appareils GPS grand public.

La plupart des implémentations semblent utiliser double pour chaque unité, mais je soupçonne qu'un format float ou un point fixe devrait suffire. Je serais curieux d’entendre parler de ceux qui ont essayé de compresser ou de stocker de grands tableaux de ces valeurs.

EDIT:

En d'autres termes, quelle est la précision minimale requise pour représenter lat / long pour un périphérique grand public?

Answer 1

Personnellement, j’utiliserais une représentation décimale à 32 bits décimale divisée par 1 000 000 selon la réponse d’Evan et mes commentaires.

Toutefois, si l'espace est vraiment limité, voici quelques idées supplémentaires:

• Vous pouvez utiliser une représentation en virgule fixe de 26 bits. Cela nécessitera de trier et de décomposer la latitude et la longitude dans un grand nombre d'octets, mais vous économiserez 12 bits pour chaque emplacement sur la représentation en valeur 32 bits - soit une économie de près de 19%, ce qui pourrait bien en valoir la peine.

• Vous pourriez tirer parti du fait que les valeurs de longitude ont besoin de moins de précision à mesure que vous vous rapprochez des pôles - elles n'ont besoin que de 26 bits à l'équateur. Vous pouvez donc écrire un schéma dans lequel le nombre de bits utilisés pour coder la longitude dépend de la valeur de la latitude.

• Si vos données possèdent d'autres attributs compressibles (par exemple, tous les points sont généralement assez proches les uns des autres), vous pouvez en tirer un avantage spécifique, par exemple en utilisant un schéma de codage delta (où chaque point autre que le premier peut être codé). comme un delta du dernier point).

Answer 2

La circonférence de la Terre est d'env. 40.000 km ou 24900 miles.

Vous devez disposer d’une précision d’un mètre pour pouvoir résoudre le problème de la précision du GPS par ordre de grandeur.

Par conséquent, vous avez besoin de précisions pour stocker 40.000.000 valeurs différentes. C'est au moins 26 bits d'information. Un float ou un bit de 32 bits fera l'affaire.

Answer 3

EDIT: , les points sur les commentaires ont été ajoutés. Les valeurs 32 bits doivent être capables d'offrir une précision suffisante.

J'utiliserais une représentation en point fixe 32 bits. Si les valeurs sont:

42.915512 , -99.521654 Je voudrais stocker les valeurs * 100000 dans int32_t / strong> (ils peuvent être négatifs).

int32_t lat = 42915512;
int32_t lon = -99521654;

C’est un bon compromis entre simple et précision ( 5 points décimaux est généralement suffisant, vous pouvez toujours le placer à 1000000 pour obtenir 6 si nécessaire).

Pour afficher à l'utilisateur, faites ce que caf suggère:

  

... à afficher à l'utilisateur - utiliser un entier   divide et modulo, par exemple printf (" Lat =   % d.% 06d \ n ", lat / 1000000, abs (lat)%   1000000)

Celles-ci seront également comparables / triables de manière efficace car l'ordre relatif sera préservé.

MODIFIER: un autre avantage est qu’il peut être envoyé sur un réseau ou stocké sur disque dans un format binaire de manière portable.

Answer 4

Les flotteurs seraient bien plus que suffisants pour stocker les coordonnées GPS, même si la précision revendiquée par les appareils GPS de niveau consommateur était proche de celle recherchée. Si vous ne le croyez pas, essayez ces deux expériences simples:

1. Placez deux ou plusieurs appareils GPS au même endroit sur un champ et notez les coordonnées mesurées par chaque appareil. Retournez à l'intérieur et tracez les points de chaque appareil sur une carte (je pense que Google a quelque chose qui le fait pour vous). Vous serez surpris de la distance qui sépare les points (même s'ils sont censés mesurer exactement le même point).
2. Prenez votre (prétendument) appareil le plus précis et placez-le dans un endroit où il peut obtenir une position satellite sans être exposé aux pluies et enregistrez une série de mesures effectuées sur une période de quelques jours. Tracer toutes les lectures (comme dans # 1). Encore une fois, vous serez surpris de la façon dont les points (qui devraient tous être identiques ou presque identiques) se promènent sur la carte, parfois même à une centaine de pieds.

J'écris des applications pour PDA compatibles GPS depuis des années et j'ai vérifié cela encore et encore pour des clients douteux (j'ai même gagné des paris de cette façon). Il existe des dispositifs GPS de meilleure qualité qui offrent une meilleure précision, mais la meilleure précision est obtenue avec des jeux de puces plus coûteux, et les dispositifs sont laissés au même endroit pendant des jours, voire des semaines, avec des lectures moyennées dans le temps. / p>

Un flottant de quatre octets est beaucoup plus précis que les périphériques eux-mêmes . Évidemment, vous ne feriez aucun mal à utiliser un double, tant que le facteur 2X ne vous pose pas de problème.

Answer 5

Une précision de 23 bits à 179 degrés de longitude donne une précision inférieure à 10 mètres, ce qui est le meilleur résultat obtenu avec un GPS ordinaire. A l'équateur:

% 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

Ainsi, un nombre à virgule flottante simple précision IEEE 754, connu sous le nom de float dans votre compilateur C, sera tout à fait approprié pour la représentation. Attention aux flotteurs pour les calculs prolongés! Erreur d'arrondi peut manger votre déjeuner. Consultez un analyste numérique.

Answer 6

Dans le format de carte IMG de Garmin, ils stockent les coordonnées dans des boîtes de contour à l’aide de flotteurs pour définir les bords des boîtes. Les coords dans les boîtes sont définis à l'aide d'un nombre variable de bits qui sont simplement linéaires entre les valeurs min et max, en fonction de la précision requise.

Par exemple: minlat = 49,0, maxlat = 50,0, minlon = 122,0, maxlon = 123,0, nombre de bits = 16

Donc, une valeur de:
32768,32768 serait converti en 49,5, 122,5
16384,0 serait 49,25, 122,0

Si vous avez besoin de moins de précision, la même sortie peut être générée avec un nombre de bits = 4

8,8 serait converti en 49,5, 122,5
4,0 serait 49,25, 122,0

Answer 7

Si vous stockez de grands tableaux de ces valeurs, il existe quelques astuces simples si vous effectuez une compression delta et que vous stockez des deltas, vous pouvez réduire considérablement la taille d'un flux de données. Vous pouvez créer des deltas à partir d'un "point clé"

.

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

k + d vous amène à n'importe quel point d

Les deltas font tous référence au K précédent, aussi, pour reconstruire un point, vous avez besoin d’un K et d’un D

ou vous pouvez faire des deltas incroyables

K I I I I I I I K I

Cela peut prendre plusieurs sommes pour arriver à la position désirée. mais les données sont globalement plus petites. SO pour reconstituer

k + i + i + i pour arriver au 4ème point

Enfin, vous pouvez combiner les deux

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

Cela ressemble à mpeg-2 avec des cadres IPB, mais de cette façon, vous n’êtes jamais plus de 4 sommes pour n’importe quelle position, et vous bénéficiez des avantages de la compression delta et incrémentielle.

Answer 8

Vous pouvez regrouper les valeurs de latitude et de longitude dans un entier de 32 bits avec une résolution d'au moins ~ 2,4 mètres / pixel (à l'équateur) si vous utilisez un système de mosaïque récursif. En utilisant deux bits par niveau, vous pouvez stocker 16 niveaux en 32 bits. Vous pouvez vous faire une idée de la façon dont cela fonctionnerait en regardant cet article sur Mosaïque de Virtual Earth système . Cela utilise Mercator, donc cela vous poserait des problèmes pour les pôles. Vous pouvez utiliser une projection différente et obtenir des résultats très similaires.

Ceci peut également être utilisé pour un filtre approximatif afin de rechercher des points dans une mosaïque parent donnée, car les N premiers bits sont identiques (la recherche devient donc un masquage de bits).

Answer 9

En supposant que la Terre soit une sphère parfaite (elle ne l’est pas, mais suffisamment proche) avec un rayon "R" de 3959 miles (ou 5280 ft / mi = 20903520 ft), la circonférence est de 131340690 pieds (avec 2 × PI). × R).

360 degrés de longitude couvre 131340690 pieds. 180 degrés de latitude couvre 65670345 pieds.

Si vous souhaitez enregistrer la latitude / longitude avec une précision de 3 pieds, vous devez pouvoir enregistrer les valeurs de longitude 43780230 (131340690/3) et de latitude 21890115 (65670345/3). 43780230 nécessite de stocker 25,38 bits (log (43780230) / log (2)) et 21890115 nécessite de stocker 24,38 bits (log (21890115) / log (2)) - à peine moins de 50 bits (ou 6,25 octets).

La question évidente est donc la suivante: si vous souhaitez stocker la latitude et la longitude sur 6 octets seulement, quelle sera la précision? Eh bien, 6 octets correspondent à 48 bits. Cela signifie 23,5 bits pour la latitude et 24,5 bits pour la longitude (la longitude a deux fois plus de valeurs, ce qui correspond à un bit et 24,5 à 23,5 = 1 bit). Donc, 23,5 bits vous permettent de représenter un nombre compris entre 0 et 11863282 (valeurs 11863283). Et 65670345 pieds divisé par 11863283 valeurs est 5,53 pieds (et la même valeur de précision pour la longitude).

THE BOTTOM LINE: Ainsi, si vous pouvez vivre avec une précision de 5,5 pieds pour la latitude et la longitude, vous pouvez regrouper les deux valeurs sur seulement six octets.

* NOTE LATÉRALE: En ce qui concerne les commentaires tels que la latitude et la longitude sont horribles pour stocker les informations de position autour d’une sphère (car il y a moins d’informations à stocker aux pôles) - eh bien, ces commentaires ne tiennent pas la route! Voyons le comprendre. Imaginons que nous voulions concevoir un nouveau système parfait capable d’enregistrer et de placer un pieu dans le sol au centre de chaque pied carré de terre. La surface de la terre (avec un R de 3959 miles; formule pour la surface d'une sphère) est de 5490965469267303 m² - cela représente beaucoup de mises que 52,29 bits à représenter. Le système de latitude et de longitude existant utilise maintenant un système rectangulaire. La largeur du rectangle est la circonférence de la terre et la hauteur du rectangle est la moitié de la circonférence) - qui est 131340690 * 65670345 (voir plus loin), ou 8625188424838050 SQ FT - qui nécessite 52,94 bits pour représenter (ce système met "trop" de pieux dans le sol autour des pôles). Donc, la réponse choquante est que le nouveau système parfait, ainsi que l’ancien système de synchronisation, nécessiteraient à la fois 53 bits pour stocker un seul emplacement sur terre, avec une précision de 1 pied!

Answer 10

Je suis surpris que personne n'ait signalé le fait que long / lat est un moyen terrible de stocker des données sur une sphère (quelqu'un a mentionné que la longitude nécessite moins de précision près des pôles).

En principe, vous pouvez stocker la position des données sous forme de coordonnées X et Y en mètres. Imaginez un cube autour de la terre qui vous va parfaitement (haha ok presque lui va bien). Vous n'avez besoin que des positions X et Y, et non des 3 coordonnées, car la 3ème coordonnée peut provenir du redius de la terre, r = racine carrée [x ^ 2 + y ^ 2 + z ^ 2] .

Convertissez donc votre lat / long en x / y en mètres. Vous n'aurez besoin que d'un total de 12756200m par coordonnée (c'est le diamètre de la terre). Ainsi, votre valeur totale ne devra varier que de 0 à 25 512 400 (une autre personne en aurait déclarée 40 000 000 parce qu'elle utilisait long / lat) pour être précise à +/- 0,5 m.

Cela donnera seulement 25 bits par position. Si j'étais vous, je ferais juste une précision de moins de 2 m et utiliserais 24 bits par position, car il s'agit d'un bon rang de 3 octets.

De même, si vous stockez des informations sur les points de cheminement sur une trajectoire, vous pouvez stocker chaque point de cheminement en tant que décalage par rapport au dernier point de cheminement. Comme commencer avec un coordinateur x / y 24bits. Et puis avoir une «mise à jour» de 16 bits qui ajuste la position en ajoutant / soustrayant x / y mètres. Une résolution de 16 bits permettrait à une mise à jour de point de route d’être à plus de 400 m. Donc, si vous savez que l'appareil n'est pas destiné aux avions et qu'il est mis à jour de temps en temps, cela pourrait également être acceptable.