Локатор/долгота хранения и сжатия в C

Ответ 1

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

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

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

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

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

Ответ 2

Окружность Земли составляет ок. 40.000 км или 24900 миль.

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

Поэтому вам нужно выполнить precisiton для хранения 40.000.000 различных значений. Это минимум 26 бит информации. 32-битный float или int будут хорошо работать.

Ответ 3

EDIT: добавил несколько комментариев из комментариев, 32-битные значения должны быть способны обеспечить достаточную точность.

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

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

int32_t lat = 42915512;
int32_t lon = -99521654;

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

Чтобы показать пользователю, выполните caf:

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

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

EDIT: дополнительное преимущество заключается в том, что он может переноситься по сети или записываться на диск в двоичном формате переносимым способом.

Ответ 4

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

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

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

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

Ответ 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, будет достаточно для представления. Остерегайтесь использования поплавков для расширенных вычислений! Ошибка округления может съесть ваш обед. Обратитесь к численному аналитику.

Ответ 6

В формате карты IMG Garmin они хранят координаты внутри ограничивающих прямоугольников, используя поплавки, чтобы установить края ящиков. Кодеры внутри ящиков определяются с использованием переменного количества битов, которые являются линейными между минимальными и максимальными значениями в зависимости от требуемой точности. Например: 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

Ответ 7

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

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

k + d приведет вас к любой точке d

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

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

K я I я I я I я I я I K

Это может занять несколько сумм, чтобы добраться до нужной позиции. но данные в целом меньше. SO для восстановления

k + я + я + i, чтобы перейти к 4-й точке

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

K D я I я D я I я D я I я K

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

Ответ 8

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

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

Ответ 9

Предполагая, что земля - ​​идеальная сфера (она не достаточно, но достаточно близко) с радиусом "R" 3959 миль (или × 5280 футов/миль = 20903520 футов), окружность составляет 131340690 футов (с использованием 2 × PI × R).

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

Если вы хотите сохранить lat/lng с точностью до 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 бит (эта система размещает "слишком много колья в земле вокруг полюсов". Таким образом, шокирующий ответ заключается в том, что как новая совершенная система, так и старая система lat/lng должны ОБЯЗЫВАТЬ 53 фактических бита для хранения одного места на земле с точностью до 1 фута!

Ответ 10

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

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

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

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

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