Хранение и сжатие широты/долготы в C

Question

Кто-нибудь знает наиболее эффективное представление координат широты и долготы?Уровень точности должен быть достаточным для потребительских GPS-устройств.

Большинство реализаций, похоже, используют double для каждой единицы, но я подозреваю, что float или формата с фиксированной точкой должно быть достаточно.Мне было бы любопытно услышать мнение любого, кто пытался сжать или сохранить большие массивы этих значений.

РЕДАКТИРОВАТЬ:

Другими словами, какова минимальная точность, необходимая для представления широты и долготы для устройства потребительского уровня?

Answer 1

Лично я бы использовал 32-битное десятичное представление с фиксированной запятой, разделив на 1 000 000 согласно ответу Эвана и моим комментариям.

Однако, если пространство действительно в дефиците, вот несколько дополнительных идей:

• Вы можете использовать 26-битное представление с фиксированной точкой на проводе.Это потребует маршаллинга и демаршаллинга широты и долготы в большой массив байтов, но сэкономит вам 12 бит для каждого местоположения по сравнению с 32-битным представлением значения — экономия почти 19%, так что это вполне может оказаться целесообразным.

• Вы можете воспользоваться тем фактом, что значения долготы требуют меньшей точности по мере приближения к полюсам — на экваторе им требуется всего 26 бит.Таким образом, вы можете написать схему, в которой количество битов, используемых для кодирования долготы, зависит от значения широты.

• Если ваши данные имеют другие сжимаемые атрибуты (скажем, все точки обычно расположены довольно близко друг к другу), вы можете воспользоваться ими, например, используя схему дельта-кодирования (где каждая точка, кроме первой, может быть закодирована как дельта от последней). точка).

Answer 2

Окружность Земли составляет ок.40 000 км или 24 900 миль.

Вам нужна точность в один метр (3 фута), чтобы на порядок превзойти точность GPS.

Поэтому вам нужна точность для хранения 40 000 000 различных значений.Это минимум 26 бит информации.32-битное число с плавающей запятой или int подойдет.

Answer 3

РЕДАКТИРОВАТЬ: добавлено несколько замечаний из комментариев: 32-битные значения должны обеспечивать достаточную точность.

Я бы использовал 32-битное представление с фиксированной запятой.Если значения:

42.915512,-99.521654 Я бы сохранил values * 100000 в int32_t's (они могут быть отрицательными).

int32_t lat = 42915512;
int32_t lon = -99521654;

Это хороший компромисс между простотой и точностью (5 десятичных знаков обычно достаточно, вы всегда можете увеличить их до 1000000 получить 6 если нужно).

Чтобы отобразить пользователю, сделайте следующее кафе предлагает:

...Чтобы отобразить пользователю - используйте целочисленное разделение и модулю, например, printf("Lat = %d.%06d\n", lat / 1000000, abs(lat) % 1000000)

Их также можно будет эффективно сравнивать/сортировать, поскольку относительный порядок будет сохранен.

РЕДАКТИРОВАТЬ: Дополнительным преимуществом является то, что его можно пересылать по сети или сохранять на диск в двоичном формате портативным способом.

Answer 4

Поплавков было бы более чем достаточно для хранения GPS-координат, даже если бы GPS-устройства потребительского уровня имели хоть сколько-нибудь заявленную точность.Если вы не верите, что это правда, попробуйте два простых эксперимента:

1. Возьмите два или более GPS-устройства в одну точку где-нибудь на поле и запишите координаты, измеренные каждым устройством.Вернитесь внутрь и нанесите на карту точки каждого устройства (я думаю, у Google есть что-то, что сделает это за вас).Вы будете удивлены тем, насколько далеко друг от друга находятся точки (хотя предполагается, что все они измеряют одно и то же место).
2. Возьмите свое (предположительно) самое точное устройство и поместите его где-нибудь, где оно сможет определить положение спутника, но не попадет под дождь, и запишите серию измерений, проведенных за пару дней.Постройте график всех показаний (как в № 1).Опять же, вы будете удивлены тем, как точки (которые должны быть одинаковыми или почти одинаковыми) перемещаются по карте, иногда на целых пару сотен футов.

Я уже много лет пишу приложения для КПК с поддержкой GPS и проверяю это на сомнительных клиентах снова и снова (я даже выигрывал таким образом ставки).Существуют более качественные GPS-устройства, которые обеспечивают более высокую точность, чем это, но лучшая точность достигается с более дорогими чипсетами, и устройства остаются на одном месте в течение нескольких дней или даже недель, а показания усредняются с течением времени.

Четырехбайтовое число с плавающей запятой гораздо точнее, чем сами устройства..Конечно, вам не помешало бы вместо этого использовать двойной, если фактор 2X не является для вас проблемой.

Answer 5

23 бита точности на 179 градусах долготы обеспечивают точность менее 10 метров, что является лучшим показателем, который дают обычные GPS-устройства.На экваторе:

% 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

Таким образом, число с плавающей запятой одинарной точности IEEE 754, известное вашему компилятору C как float, будет достаточно для представления.Остерегайтесь использования чисел с плавающей запятой для расширенных вычислений!Ошибка округления может съесть ваш обед.Проконсультируйтесь с числовым аналитиком.

Answer 6

В формате карт Garmin IMG они хранят координаты внутри ограничивающих рамок, используя поплавки для установки краев рамок.Координаты внутри блоков определяются с использованием переменного числа битов, которые линейно зависят от минимального и максимального значений в зависимости от необходимой точности.

Например: minlat=49.0, maxlat=50.0, minlon=122.0, maxlon=123.0, количество бит=16

Итак, значение:
32768,32768 будут преобразованы в 49,5, 122,5.
16384,0 будет 49,25, 122,0

Если вам нужна меньшая точность, тот же результат можно сгенерировать с количеством бит = 4.
8,8 будет преобразовано в 49,5, 122,5.
4,0 будет 49,25, 122,0

Answer 7

Если вы храните большие массивы этих значений, есть несколько простых приемов: если вы выполняете дельта-сжатие и сохраняете дельты, вы можете значительно уменьшить размер потока данных.Вы можете делать дельты из «ключевой точки».

К Д Д Д Д Д Д Д Д Д Д К Д Д Д Д ...

k + d доставит вас в любую точку d

Все дельты ссылаются на предыдущий K, поэтому для восстановления любой точки вам нужны K и D.

или вы можете сделать дополнительные дельты

К I I I I I I I I I I K

Для достижения желаемой позиции может потребоваться несколько сумм.но в целом данные меньше.ТАК реконструировать

k+i+i+i, чтобы добраться до 4-й точки

Наконец, вы можете объединить оба

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

Это похоже на mpeg-2 с кадрами IPB, но таким образом вы никогда не получаете более 4 сумм в любой позиции и получаете некоторые преимущества дельта- и добавочного сжатия.

Answer 8

Вы можете упаковать и широта, и долгота ценности в одно 32-битное целое число с разрешением в худшем случае ~2,4 метра на пиксель (на экваторе), если вы используете рекурсивную систему листов.Используя два бита на уровень, вы можете хранить 16 уровней в 32 битах.Вы можете получить представление о том, как это будет работать, прочитав эту статью о Система листов виртуальной Земли.Здесь используется Меркатор, поэтому у вас могут возникнуть проблемы с полюсами.Вместо этого вы можете использовать другую проекцию и при этом получить очень похожие результаты.

Это также можно использовать для фильтр грубой очистки чтобы найти любые точки внутри данного родительского тайла, поскольку первые N бит будут одинаковыми (и поэтому поиск становится битовой маскировкой).

Answer 9

Если предположить, что Земля представляет собой идеальную сферу (это не так, но достаточно близко) с радиусом «R» 3959 миль (или ×5280 футов/миль = 20903520 футов), длина окружности составит 131340690 футов (при использовании 2×PI×R). .

360 градусов долготы охватывают 131340690 футов.180 градусов широты покрывают 65670345 футов.

Если вы хотите сохранить широту и долготу с точностью до 3 футов, вам необходимо иметь возможность хранить значения долготы 43780230 (131340690/3) и значения широты 21890115 (65670345/3).43780230 требует 25,38 бит (log(43780230)/log(2)) для хранения, а 21890115 требует 24,38 бит (log(21890115)/log(2)) для хранения – или чуть менее 50 бит (или 6,25 байт).

Таким образом, возникает очевидный вопрос: если вы хотите хранить широту и долготу всего в 6 байтах, какова будет точность?Ну 6 байт это 48 бит.Это означает 23,5 бита для широты и 24,5 бита для долготы (долгота имеет в два раза больше значений, что составляет всего один бит и 24,5–23,5 = 1 бит).Таким образом, 23,5 бита позволяют представлять число от 0 до 11863282 (11863283 значения).А 65670345 футов, разделенные на 11863283 значения, составляют 5,53 фута (и такое же значение точности для долготы).

НИЖНЯЯ ЛИНИЯ:Итак, если вы можете жить с точностью 5,5 футов как по широте, так и по долготе, вы можете упаковать оба значения всего в шесть байтов.

*Примечание:Что касается комментариев о том, что широта и долгота ужасны для хранения информации о положении вокруг сферы (потому что на полюсах хранится меньше информации) – ну, эти комментарии не выдерживают математики!Давайте разберемся.Допустим, мы хотим разработать новую совершенную систему, которая сможет записывать и размещать колышки в центре каждого квадратного фута земли.Площадь поверхности Земли (при R 3959 миль;формула площади поверхности сферы) равна 5490965469267303 SQ FT – для представления многих ставок требуется 52,29 бита.Сейчас существующая система широты и долготы использует прямоугольную систему.Ширина прямоугольника равна длине окружности Земли, а высота прямоугольника равна 1/2 длины окружности) – что составляет 131340690 * 65670345 (см. выше) или 8625188424838050 SQ FT – для представления которого требуется 52,94 бита (эта система помещает «слишком много» кольев в земле вокруг полюсов).Итак, шокирующий ответ заключается в том, что и новая идеальная система, и старая система широты и долготы ОБА потребуют 53 фактических бита для хранения одного местоположения на Земле, с точностью до 1 фута!

Answer 10

Я удивлен, что никто не опубликовал тот факт, что долгота/широта — ужасный способ хранения данных на сфере (кто-то упомянул, что долгота требует меньшей точности вблизи полюсов).

По сути, вы можете хранить положение данных в виде координат X и Y в метрах.Представьте себе куб вокруг Земли, который точно соответствует (ха-ха, ок) почти подходит).Вам нужно сохранить только позиции X и Y, а не все 3 координаты, потому что 3-я координата может исходить из Редиуса Земли, r = квадратный корень [x^2 + y^2 + z^2] .

Итак, преобразуйте широту/долготу в x/y в метрах.Вам понадобится всего 12756200 м на координату (это диаметры Земли).Таким образом, ваше общее значение должно будет находиться в диапазоне от 0 до 25 512 400 (кто-то другой заявил, что 40 000 000, потому что он использовал долготу/широту), чтобы быть точным до +/- 0,5 м.

В результате получится всего 25 бит на позицию.На вашем месте я бы просто сделал точность с точностью до 2 м и использовал бы 24 бита на позицию, так как это аккуратные 3 байта.

Кроме того, если вы сохраняете информацию о путевых точках на пути, вы можете сохранить каждую путевую точку как смещение от последней путевой точки.Например, начнем с 24-битной координаты x/y.А затем сделайте 16-битное «обновление», которое корректирует положение путем добавления/вычитания метров x/y.16-битная версия позволит обновить путевую точку на расстоянии более 400 метров.Так что, если вы знаете, что устройство не предназначено для самолетов и периодических обновлений, это тоже может быть приемлемо.