Szerokość/długość przechowywania i kompresji w C

Obwód Ziemi wynosi ok. 40.000 km lub 24900 Mil.

Potrzebujesz dokładności jednego metra (3 stopy), aby móc rozwiązać precyzję gps o rząd wielkości.

Dlatego potrzebujesz precisiton do przechowywania 40.000.000 różnych wartości. To minimum 26 bitów informacji. 32-bitowy float lub int będzie dobrze.

EDIT: dodano kilka punktów z komentarzy, wartości 32-bitowe powinny być w stanie zaoferować wystarczającą precyzję.

Użyłbym 32-bitowej reprezentacji punktów stałych. Jeśli wartości są:

42.915512,-99.521654 przechowywałbym values * 100000 w int32_t's (mogą być ujemne).

int32_t lat = 42915512;
int32_t lon = -99521654;

To dobry kompromis pomiędzy prostotą a dokładnością (5 punkty dziesiętne są zwykle wystarczająco dobre, zawsze możesz podskoczyć do 1000000, aby uzyskać 6, jeśli potrzebne).

Aby wyświetlić użytkownikowi, zrób to, co caf sugeruje:

... aby wyświetlić użytkownikowi-użyj integer dzielenie i modulo, np printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)

Będą one również porównywalne / sortowalne w efektywny sposób, ponieważ kolejność względna zostanie zachowana.

EDIT: dodatkową korzyścią jest to, że może być wysyłany przez sieć lub zapisywany na dysk w formacie binarnym w przenośny sposób.

Pływaki byłyby o wiele więcej niż wystarczające do przechowywania współrzędnych GPS, nawet jeśli urządzenia GPS na poziomie konsumentów miały w pobliżu deklarowanej dla nich dokładności. Jeśli nie wierzysz, że to prawda, spróbuj tych dwóch prostych eksperymentów:

Weź dwa lub więcej urządzeń GPS w jedno miejsce na polu i zanotuj współrzędne mierzone przez każde urządzenie. Wróć do środka i narysuj punkty z każdego urządzenia na mapie (myślę, że Google ma coś, co robi to za Ciebie). Będziesz zdumiony, jak daleko od siebie znajdują się punkty (mimo że wszystkie powinny mierzyć dokładnie to samo miejsce).
1. Weź swoje (rzekomo) najdokładniejsze urządzenie i umieść je gdzieś, gdzie może uzyskać poprawkę satelitarną, ale nie będzie padać, i nagraj serię pomiarów wykonanych w ciągu kilku dni. Wykreśl wszystkie odczyty (jak w #1). Ponownie będziecie zaskoczeni tym, jak punkty (które powinny być takie same lub prawie takie same) wędrują po całej mapie, czasami aż o kilkaset stóp.

Od lat piszę aplikacje do PDA z obsługą GPS, i sprawdzałem to w kółko dla wątpliwych klientów (nawet wygrywałem zakłady w ten sposób). Istnieją urządzenia GPS wyższej jakości, które osiągają lepszą dokładność niż to, ale lepsza dokładność jest osiągana dzięki droższym chipsetom, a urządzenia pozostają w jednym miejscu przez kilka dni lub nawet tygodni, a odczyty uśredniane w czasie.

Czterobajtowy float jest o wiele bardziej dokładne niż same urządzenia . Oczywiście nie zaszkodzi ci w ogóle użyć podwójnego, o ile czynnik 2X nie jest dla Ciebie problemem.

23 bity precyzji przy 179 stopniach długości daje poniżej 10-metrowej dokładności, która jest najlepsza, jaką dają zwykłe urządzenia GPS. Na równiku:

% 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

Więc liczba zmiennoprzecinkowa o pojedynczej precyzji IEEE 754, znana kompilatorowi C jako float, będzie odpowiednia do reprezentacji. Uwaga na używanie pływaków do rozszerzonych obliczeń! Błąd zaokrąglenia może zjeść lunch. Skonsultuj się z analitykiem numerycznym.

W formacie mapy img firmy Garmin przechowują współrzędne wewnątrz obwiedni za pomocą pływaków do ustawiania krawędzi pudełek. Coords wewnątrz pól są definiowane za pomocą zmiennej liczby bitów, które są tylko liniowe między wartościami min i max w zależności od wymaganej precyzji.

Na przykład: minlat=49.0, maxlat=50.0, minlon=122.0, maxlon=123.0, ilość bitów=16

Więc wartość:
32768,32768 zostanie zamienione na 49.5, 122.5
16384,00 zł, 122.0

Jeśli potrzebujesz mniejszej precyzji, to samo wyjście może zostać wygenerowane z liczbą bitów=4
8,8 byłoby zamienione na 49,5, 122,5
4,0 byłoby 49.25, 122.0

Jeśli przechowujesz duże tablice tych wartości, istnieje kilka prostych sztuczek, jeśli wykonasz kompresję delta i przechowasz delty, możesz znacznie zmniejszyć rozmiar strumienia danych. Możesz zrobić delty z"kluczowego punktu"

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

K + d doprowadzi Cię do dowolnego punktu d

Wszystkie delty odwołują się do poprzedniego K, więc aby odtworzyć dowolny punkt, potrzebujesz K I D

Or you can do incrimental deltas

K I

To może wymagać wielu sum, aby dostać się do żądanej pozycji. ale ogólnie dane są mniejsze. So to reconsturct

K + i+i + I do 4 punktu

Wreszcie możesz połączyć oba

K D I I I I D I I I K

To jest jak mpeg-2 z ramkami IPB, ale w ten sposób nigdy nie masz więcej niż 4 sum do dowolnej pozycji, a otrzymasz część korzyści z kompresji Delta i Incrimental.

Można spakować zarówno szerokość i długość wartości w pojedynczej 32-bitowej liczbie całkowitej z rozdzielczością co najmniej ~2,4 metra/piksel (na równiku), jeśli używasz rekurencyjnego systemu płytek. Używając dwóch bitów na poziom, możesz zapisać 16 poziomów w 32 bitach. Możesz dowiedzieć się, jak to działa, patrząc na ten artykuł o systemie płytek wirtualnej ziemi. To używa Mercatora, więc dałoby to problemy Polakom. Zamiast tego możesz użyć innej projekcji i nadal uzyskać bardzo podobne wyniki.

To może być również użyte do filtra zgrubnego , aby znaleźć dowolne punkty w danej płytce nadrzędnej, ponieważ pierwsze N bitów będzie takie samo (i tak wyszukiwanie staje się maskowaniem bitów).

Zakładając, że ziemia jest idealną kulą (nie jest, ale wystarczająco blisko) o promieniu " R " 3959 mil (lub ×5280 ft/mi = 20903520 ft), obwód wynosi 131340690 stóp (przy 2×PI×R).

360 stopni długości obejmuje 131340690 stóp. 180 stopni szerokości geograficznej obejmuje 65670345 stóp.

Jeśli chcesz przechowywać lat / lng z dokładnością do 3 stóp, musisz być w stanie przechowywać wartości 43780230 (131340690/3) długość i 21890115 (65670345/3) szerokość. 437802300 25.38 bitów (log(43780230)/log(2)) do przechowywania, a 21890115 wymaga 24.38 bitów (log(21890115)/log(2)) do przechowywania – lub mniej niż 50 bitów (lub 6.25 bajtów).

Więc oczywiste staje się pytanie, jeśli chcesz przechowywać szerokość i długość geograficzną w zaledwie 6 bajtach, jaka będzie dokładność? 6 bajtów to 48 bitów. Oznacza to 23,5 bitów szerokości geograficznej i 24,5 bitów długości geograficznej (Długość ma dwa razy więcej wartości, czyli tylko jeden bit i 24,5-23,5=1 bit). Więc 23,5 bitów pozwala na reprezentowanie liczby od 0 do 11863282 (11863283 wartości). A 65670345 stóp podzielonych przez 11863283 wartości to 5.53 stóp (i taka sama wartość dokładności dla długości geograficznej).

Podsumowując: jeśli więc możesz żyć z dokładnością do 5,5 metra zarówno dla szerokości i długości geograficznej, możesz spakować obie wartości do zaledwie sześciu bajtów.

* uwaga na marginesie: odnośnie komentarzy, że szerokość i Długość geograficzna są straszne do przechowywania informacji pozycyjnych wokół kuli (ponieważ jest mniej informacji do przechowywania na biegunach) – cóż, te komentarze nie trzymają się matematyki! Rozwiążmy to. Powiedzmy, że chcemy zaprojektować nowy doskonały system, który może nagrywać i umieszczać kołek w ziemi w środku każdego metra kwadratowego ziemi. Powierzchnia ziemi (z R 3959 Mil; wzór na powierzchnię sfery) wynosi 5490965469267303 stóp kwadratowych – to wiele stawek wymaga 52,29 bitów do reprezentowania. Obecnie istniejący system szerokości i długości geograficznej wykorzystuje system prostokątny. Szerokość prostokąta wynosi obwód Ziemi i wysokość prostokąta wynosi 1/2 obwodu) - co wynosi 131340690 * 65670345 (patrz daleko powyżej), lub 8625188424838050 stóp kwadratowych-co wymaga 52,94 bitów do reprezentowania (ten system umieszcza "zbyt wiele" stawek w ziemi wokół biegunów). Szokująca odpowiedź jest taka, że zarówno nowy system perfect, jak i stary system lat / lng, wymagałyby 53 rzeczywistych bitów do przechowywania pojedynczej lokalizacji na ziemi, z dokładnością do 1 stopy!

Jestem zaskoczony, że nikt nie opublikował faktu, że long / lat jest okropnym sposobem przechowywania danych na kuli (ktoś wspomniał, że długość wymaga mniejszej precyzji w pobliżu biegunów).

W zasadzie można przechowywać pozycję danych jako współrzędne X i Y w metrach. Wyobraź sobie sześcian wokół Ziemi, który dokładnie pasuje (haha ok prawie pasuje do niego). Trzeba tylko przechowywać X i Y pozycji, nie wszystkie 3 co-ord, ponieważ 3-rd co-ord może pochodzić z redius ziemi , r = pierwiastek kwadratowy[x^2 + y^2 + z^2].

Więc przekształć swój lat / long na x / y w metrach. Będziesz potrzebował tylko w sumie 12756200m na co-ord (to średnice ziemi). Więc twoja całkowita wartość będzie musiała rozciągać się od 0 do 25,512,400 (ktoś inny twierdził 40,000,000, ponieważ używali long/lat), aby być dokładnym do +/- 0.5 m.

To daje tylko 25 bitów na pozycję. Na Twoim miejscu zrobiłbym dokładność do 2M i używał 24 bitów na pozycję, bo to jest uporządkowane 3 bajty.

Także jeśli przechowują informacje o punkcie drogi na ścieżce, można przechowywać każdy punkt drogi jako przesunięcie od ostatniego punktu drogi. Jak zacząć z 24-bitowym X/Y co-ord. a następnie mieć 16-bitową "aktualizację", która dostosowuje pozycję przez dodawanie/odejmowanie X / Y metrów. 16bit pozwoliłby na aktualizację waypointa w odległości ponad 400m. Jeśli więc wiesz, że urządzenie nie jest przeznaczone do samolotów i aktualizacji co jakiś czas, może to być również dopuszczalne.