Широта / Долгота хранения и сжатия в C

Question

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

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

EDIT:

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

Answer 1

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

Тем не менее, если пространство действительно дорого, вот несколько дополнительных идей:

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

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

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

Answer 2

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

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

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

Answer 3

РЕДАКТИРОВАТЬ: добавил несколько комментариев из комментариев, 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)

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

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

Answer 4

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

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

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

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

Answer 5

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

K D D 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, чтобы добраться до 4-й точки

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

К Д Я Я Я Я Я Я Я Я Я Я Я Я * K

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

Answer 6

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

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

Так что значение:
3276832768 будут преобразованы в 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

Точность

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 8

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

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

Если вы хотите сохранить широту / долготу с точностью до 3 футов, вам необходимо сохранить значения долготы 43780230 (131340690/3) и широты 21890115 (65670345/3). Для 43780230 требуется 25,38 бит (журнал (43780230) / журнал (2)) для хранения, а для 21890115 требуется 24,38 бит (журнал (21890115) / журнал (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 бит. Теперь существующая система широты и долготы использует прямоугольную систему. Ширина прямоугольника - это окружность земли, а высота прямоугольника равна половине окружности), что составляет 131340690 * 65670345 (см. Выше) или 8625188424838050 SQ FT - для представления которого требуется 52,94 бита (эта система размещает «слишком много» ставок в землю вокруг полюсов). Таким образом, шокирующий ответ заключается в том, что и для новой совершенной системы, и для старой системы широты и ширины ОБА потребуется 53 фактических бита для хранения одного местоположения на земле с точностью до 1 фута!

Answer 9

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

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

Answer 10

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

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

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

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

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