Stockage et compression en Latitude/Longitude en C

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

vous avez besoin d'une précision d'un mètre (3 pi) pour être en mesure de dépasser la précision gps d'un ordre de grandeur.

par conséquent, vous avez besoin de precisiton pour stocker 40.000.000 de valeurs différentes. C'est au moins 26 bits d'information. Un flotteur 32 bits ou int fera l'affaire.

EDIT: a ajouté quelques points à partir des commentaires, les valeurs 32 bits devraient être capables d'offrir assez de précision.

j'utiliserais une représentation à points fixes de 32 bits. Si les valeurs sont les suivantes:

42.915512,-99.521654 Je stockerais le values * 100000int32_t (ils peuvent être négatifs).

int32_t lat = 42915512;
int32_t lon = -99521654;

C'est un bon compromis entre simplicité et précision (5 décimal points est habituellement assez bon, vous pourriez toujours elle bosse jusqu'à 1000000 pour obtenir de l' 6 si nécessaire).

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

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

ceux-ci seront également comparables/sortables d'une manière efficace puisque l'ordre relatif sera préservé.

EDIT: un avantage supplémentaire est qu'il peut envoyées sur un réseau ou stockées sur le disque dans un format binaire de manière portable.

les flotteurs seraient beaucoup plus que suffisants pour stocker les coordonnées GPS, même si les appareils GPS de niveau consommateur avaient une précision proche de celle déclarée pour eux. Si vous ne croyez pas, essayez de ces deux expériences:

1. prendre deux ou plusieurs appareils GPS dans un seul endroit sur un champ quelque part, et noter les coordonnées mesurées par chaque appareil. Retournez à l'intérieur et tracer les points de chaque appareil sur une carte (je pense que Google a quelque chose qui fait cela pour vous). Vous serez surpris par la distance entre les points (même s'ils sont tous censés mesurer exactement le même point).
2. prenez votre appareil (prétendument) le plus précis, et placez-le quelque part où il peut obtenir un fixe satellite, mais ne sera pas pleuvoir sur, et enregistrer une série de mesures prises sur une couple de jours. Tracer toutes les lectures (comme dans #1). Encore une fois, vous serez surpris par la façon dont les points (qui devraient tous être les mêmes ou presque) se déplacent sur toute la carte, parfois d'autant que quelques centaines de pieds.

j'écris des applications pour les PDA compatibles GPS depuis des années, et j'ai vérifié cela pour des clients douteux encore et encore (j'ai même gagné des paris de cette façon). Il y a des appareils GPS de meilleure qualité là-bas qui atteignent une meilleure précision que cela, mais la meilleure précision est atteinte avec des chipsets plus chers, et les appareils sont laissés dans un endroit pendant des jours ou même des semaines, avec les lectures moyennes sur temps.

un flotteur de quatre octets est beaucoup plus précis que les appareils eux-mêmes. Bien sûr, cela ne vous nuirait pas du tout d'utiliser un double à la place, à condition que le facteur 2X ne soit pas un problème pour vous.

23 bits de précision à 179 degrés de longitude donne moins de 10 mètres de précision, ce qui est le meilleur que les appareils GPS ordinaires donnent. Au niveau de 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

donc un numéro IEEE 754 à virgule flottante de précision simple, connu par votre compilateur C comme float, wil être juste suffisante pour la représentation. Méfiez-vous de l'utilisation de flotteurs pour les calculs prolongés! Erreur d'arrondi peut manger votre déjeuner. Consulter un analyste numérique.

dans le format de carte IMG de Garmin ils stockent les coordonnées à l'intérieur des boîtes de limites en utilisant des flotteurs pour régler les bords des boîtes. Les accords à l'intérieur des boîtes sont définis en utilisant un nombre variable de bits qui sont juste linéaires entre les valeurs min et max en fonction de la précision nécessaire.



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 à 49,5, 122.5

4,0 serait 49.25, 122.0

si vous stockez de grands tableaux de ces valeurs, il y a quelques trucs simples si vous faites une compression delta, et stockez des deltas, vous pouvez réduire considérablement la taille d'un flux de données. Vous pouvez faire des deltas à partir d'un "point clé"

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

k + d obtenir de vous à n'importe quel point d

Les deltas tous référence à la précédente, K, afin de reconstituer n'importe quel point, vous avez besoin d'un K et un D

ou vous pouvez le faire incrémentielle les deltas

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

Cela peut prendre plusieurs sommes pour obtenir la position souhaitée. mais les données sont plus petites dans l'ensemble. DONC, pour reconsturct

k+i+i+i pour l'obtention de la 4ème point

Enfin, vous pouvez combiner les deux

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

c'est comme mpeg-2 avec des cadres IPB, mais de cette façon vous n'êtes jamais plus de 4 sommes à n'importe quelle position, et vous obtenez une partie de L'avantage de Delta et Incrimental Compression.

Vous pouvez emballer la latitude et la longitude valeurs simple entier 32 bits avec une résolution d'au pire ~2,4 mètres/pixel (à l'équateur) si vous utilisez un circuit de carrelage système. En utilisant deux bits par niveau, vous pouvez stocker 16 niveaux en 32 bits. Vous pouvez avoir une idée de comment cela pourrait fonctionner en regardant cet article sur Virtual Earth de carrelage system. Cela utilise Mercator, donc il vous donnerait des problèmes pour les pôles. Vous pouvez également utiliser un projection différente et encore obtenir des résultats très similaires.

Cela peut aussi être utilisé pour un bruts filtre pour trouver n'importe quels points dans une tuile de parent donnée puisque les premiers N bits seront les mêmes (et ainsi la recherche devient masquage de bit).

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

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

si vous voulez stocker lat/lng jusqu'à une précision de 3 pieds, vous devez être en mesure de stocker 43780230 (131340690/3) valeur de longitude et 21890115 (65670345/3) valeurs de latitude. 43780230 nécessite 25.38 bits (log(43780230)/log(2)) pour stocker et 21890115 nécessite 24.38 bits (log(21890115)/log(2)) de magasin ou un peu moins de 50 bits (soit 6,25 octets).

ainsi la question évidente devient, si vous voulez stocker la latitude et la longitude en seulement 6 bytes, quelle sera la précision? 6 octets, c'est 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, qui est juste un bit et 24,5-23,5=1 bit). Donc 23,5 bits permet vous devez représenter un nombre de 0 à 11863282 (11863283 valeurs). Et 65670345 pieds divisé par 11863283 valeurs est de 5,53 pieds (et la même valeur de précision pour la longitude).

le résultat: donc, si vous pouvez vivre avec 5,5 pieds de précision à la fois pour la latitude et la longitude, vous pouvez regrouper les deux valeurs en seulement six octets.

*une note secondaire: concernant les commentaires que la latitude et la longitude sont horribles pour stocker l'information de position autour d'une sphère (parce qu'il y a moins de information à stocker aux pôles) - Eh bien, ces commentaires ne résistent pas au calcul! Voyons voir. Disons que nous voulons concevoir un nouveau système parfait qui peut enregistrer et placer un pieu dans le sol au centre de chaque pied carré de la terre. La surface de la terre (avec un R de 3959 miles; formule pour la surface d'une sphère) est 5490965469267303 pi2 – que de nombreux pieux nécessite 52.29 bits pour représenter. Le système existant de latitude et de longitude utilise maintenant un système rectangulaire. Le 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 haut), ou 8625188424838050 m2 – qui nécessite 52,94 bits pour représenter (ce système Place "trop" de pieux dans le sol autour des pôles). Ainsi, la réponse choquante est que le nouveau système parfait, et l'ancien système lat / lng, nécessiterait tous les deux 53 bits réels pour stocker un seul emplacement sur terre, jusqu'à une précision d'un pied!

je suis surpris que personne n'ait posté le fait que long/lat est un terrible moyen 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).

fondamentalement, vous pouvez stocker la position des données comme X et Y co-ords en mètres. Imaginez un cube autour de la Terre qui correspond exactement (haha ok presque il s'adapte). Vous n'avez besoin de stocker que la position X et Y, pas tous les 3 co-ords, car le co-ord 3-rd peut provenir de la redirection 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 Co-ord (c'est le diamètre de la terre). Donc votre valeur totale ne devra s'étendre que de 0 à 25.512.400 (quelqu'un d'autre a réclamé 40.000.000 parce qu'ils utilisaient long/lat) pour être précis à +/- 0.5 m.

Cela donnera seulement 25 bits par position. Si j'étais vous, je ferais juste précision à 2m et utiliser 24 bits par position, comme c'est un tidy 3 octet.

aussi si vous stockez des informations de point de cheminement sur un chemin, vous pouvez stocker chaque point de cheminement comme un décalage par rapport au dernier point de cheminement. Comme commencer avec un co-ord 24bit x/Y. Et ensuite avoir une "mise à jour" de 16 bits qui ajuste la position en ajoutant/soustrayant des compteurs x/Y. 16bit permettrait une mise à jour de waypoint à plus de 400m de distance. Donc, si vous savez que l'appareil n'est pas destiné à des avions et des mises à jour de temps en temps, cela pourrait être acceptable aussi.