Разработка навигационной программы

[Gmurik2]

@andriano

Спасибо.
Сходу несколько замечаний:

1. При описании бинарного формата принято в первом столбце указывать смещение поля относительно начала блока. Если бы это было сделано, то сразу было бы видно, что данные в структурах не выровнены на 4 байта. А это имеет целый ряд недостатков. Кроме того, принято также указывать длину поля.

Учту, поправлю

@andriano

2. Непонятно, зачем нужна CRC32. Вместо нее лучше было бы использовать идентификатор файла.

Честно говоря в принципе не нужна, но с другой стороны даст возможность оценить корректен ли файл.

@andriano

3. Не указано, какие числа используются, bigendian или littltendian.

bigendian

@andriano

5. Чем Адрес роутингова графа отличается от Адрес первого дерева? Учитывая, что отдельно заголовка для роутингова графа не приводится, по идее они должны совпадать.
6. Почему вообще в файле может быть больше одного дерева?
7. Почему принят формат именно Q-tree?
8. Непонятно, чем quadro-tree отличается от quadro-tree графа.

По идее они как раз и не должны совпадать, одно для отображения, другое для счета. Граф в дереве для того чтобы не считать маршрут по всей карте, а взять для расчета лишь необходимый кусок( особенно если использовать алгоритм Дейкстры). Каждое дерево для своего масштаба.

@andriano

9. Какова вообще структура файла? Описано несколько заголовков, но непонятно, в каком порядке они должны следовать в файле, а также, как именно располагаются данные относительно заголовков.

Я думаю после того как я укажу смещения в файле, то должно стать белее понятно.

@andriano

10. Что такое “геометрия”?

Объект на карте со своими тегами и узлами.

[Gmurik2]

@usm78-gis

1. QString это как я понял обычный char * QString.toUtf8()

Да именно так

@usm78-gis

2. 32битные адреса уже не работают для единой карты Европы для гармин (>4G),
   на эти грабли наступила гисрусса с ее 24битными оффсетами.

Но тут я не собираюсь монстрообразные файлы создавать. Считаю, что лучше сделать много средних файлов. например квадратная карта размером 200 -250 км

@usm78-gis

3. float/double еще плохи потому, что на подавляющем большинстве ARM процессоров
   нет VFP.

Да я согласен с сообществом насчет использования int32. Теперь думаю как безболезненно для себя поменять double на int

[usm78-gis]

@Gmurik2

@andriano

3. Не указано, какие числа используются, bigendian или littltendian.

bigendian

Эээ. Зачем ?

[x10kHz]

@andriano

Проблема в том, что

Проблема в том что Вы по большей части пишите чушь… еще возможно вы думаете тут сидят люди, которые не понимаю очевидных вещей? Это не так.
Пожалуйста, не утруждайте себя комментированием моих сообщений.
Не навязываю свои идеи ни вам, ни кому-либо другому…

Что касается стеганографии, то оставляю след, может кому пригодится. Простите что не в тему…
Ессесно сконвертив неаккуратно все пропадет, такие методы применимы скорее для “своего” формата, в картах для конкретной проги/железки.
Даже если прога не знает про алгоритм стеганографии, то она просто потеряет теги.
Сжатие не в разы, конечно, но объем данных экономит.

Приведу простой пример… для маленьких по размеру объектов.

Встраивание:
Берем любой не очень большой по размерам дом (объект с тегом билдинг=yes), если видим что он имеет прямой угол образуемый первым, вторым и третьим нодом, то делаем его 91 градус, пересчитав координату третьего нода… и убираем тег билдинг=yes… у всех остальных объектов малых размеров не имеющих тега билдинг=yes проверяем углы, образуемые первым вторым и третьим нодами в вее и если найдем 91 градус поправим на 90 к примеру… чтобы не было путаницы…
Все, сохранили карту… при этом пропали теги билдинг=yes у все квадратных домиков на планете.

Извлечение:
При открытии такой карты в проге, которая знает о стегоалгоритме прога будет проверять нужный угол… найдет 91 градус присвоит объекту тег билдинг=yes… при этом можно поправить угол на 90, и соответственно вернуть первоначальное положение третьего нода.

Алгоиртмы можно усложнять… нет предела совершенству))
Экономию объема оценить трудно, многое зависит от хитрости алгоритма…
Чем они умнее, тем больше инфы можно спрятать, хотя и вычислений тогда делать нужно больше…
Наверное подобные методы - дело не самого близкого будущего… т.к., как уже было замечено, и без этих понтов есть более простые методы карту пожать.

[andriano]

@Gmurik2

По идее они как раз и не должны совпадать, одно для отображения, другое для счета. Граф в дереве для того чтобы не считать маршрут по всей карте, а взять для расчета лишь необходимый кусок( особенно если использовать алгоритм Дейкстры). Каждое дерево для своего масштаба.

Под “счетом” подразумевается построение маршрута?

По поводу расчета маршрута: правильно ли я понял, что в дереве ищется вершина, являющаяся предком начала и конца маршрута, после чего граф строится только для данной вершины? Если это так, то может оказаться, что оптимальный, а то и вовсе единственный маршрут лежит за ределами фрагмента карты, относящегося к этой вершине.
Или я что-то не так понял?

[Gmurik2]

Не совсем так. Граф будет строится по точкам попадающим в область, образованной начальной и конечной точками маршрута + некоторое разумное расширение границ соответственно влево, вверх, вправо, вниз, например на половину расстояния между точками. Считаю, в этот граф должен попасть оптимальный маршрут. Если же маршрут не будет найден, то тогда уже можно считать по всему quadtree.

[andriano]

Gmurik2, в таком случае я не понимаю, каким образом Q-tree используется для построения маршрута.

[dkiselev]

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

[andriano]

@Gmurik2

Учту, поправлю

В первой таблице явно ошибки со смещением. Следует посмотреть в районе 2 и 22 байтов.
Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.
Коль скоро для координат используется int32, следовало бы указать, каким координатам (в вещественных градусах) соответствуют какие целые числа. Т.е. формулы преобразования.
Слово “адрес” обычно применяется к адресации в оперативной памяти. При этом реальное значение адреса заранее неопределено и определяется менеджером памяти. В файле же присутствуют смещения - фиксированные величины относительно начала файла либо начала блока.
Непонятно, что находится между “30” и “30+(Количество графов)*4”.
Смещения во всех таблицах даются от 0, что принимается за 0? Надеюсь, не начало файла? Вероятно, это начало заголовка, тогда хотелось бы, чтобы явно было указано, где хранится адрес данного заголовка.
И еще: как разбирать поля, для которых указано n/a? Вероятно, если этому препятствует структура Qstring, то надо от нее отказаться, чтобы снять неопределенность в формате файла.
Кстати, что все-таки такое Qstring?

Я думаю после того как я укажу смещения в файле, то должно стать белее понятно.

Увы, пока не стало.

[Gmurik2]

@andriano

Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.

А можно поинтересоваться какие?

@andriano

Коль скоро для координат используется int32, следовало бы указать, каким координатам (в вещественных градусах) соответствуют какие целые числа. Т.е. формулы преобразования.

Формула примитивна до ужаса lat = int32/10000000
так пока и не придумал как отойти от вещественных вычислений, Есть предложения получше?

@andriano

И еще: как разбирать поля, для которых указано n/a? Вероятно, если этому препятствует структура Qstring, то надо от нее отказаться, чтобы снять неопределенность в формате файла.
Кстати, что все-таки такое Qstring?

Этому препятствует то, что заранее нельзя знать длину QString.
QString это строка в UTF-8, при записи в файл, сначала указывается длина строки в байтах, а далее идет собственно строка по 2 байта на символ.

[liosha]

@Gmurik2

@andriano

Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.

А можно поинтересоваться какие?

Скорость: два чтения памяти вместо одного.

@Gmurik2

Формула примитивна до ужаса lat = int32/10000000
так пока и не придумал как отойти от вещественных вычислений, Есть предложения получше?

Обычно переводят в целые числа по-другому: ilat = int( lat / 90 * 2^31 ), ilon = int( lon / 180 * 2^ 31 )

[Gmurik2]

@liosha

Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.

А можно поинтересоваться какие?
Скорость: два чтения памяти вместо одного.

64-битные целые это уже насущная необходимость

@liosha

Обычно переводят в целые числа по-другому: ilat = int( lat / 90 * 2^31 ), ilon = int( lon / 180 * 2^ 31 )

Точность в семь знаков, после запятой я считаю более чем достаточна для навигатора, тем более исходные данные так же содержат 7 знаков после запятой.

[liosha]

Gmurik2, речь о том что с бинарными долями окружности работать будет удобнее, чем с десятичными долями градусов.

[Gmurik2]

@liosha

Gmurik2, речь о том что с бинарными долями окружности работать будет удобнее, чем с десятичными долями градусов.

Пока не вижу удобств… Переделать не долго…

Есть небольшие продвижения, ознакомиться можно здесь

Внимание! Присутствует проблема утечки память. И не оптимизирован вывод quad’ов, так что при перемещении карты есть тормоза. Ну как говорится лед тронулся

[Hind]

Она скомпилена в дебажном режиме и требует QtCored4.dll

[Fortress (Vitaly Ivanov)]

@Hind

Она скомпилена в дебажном режиме и требует QtCored4.dll

А ещё msvcp71d.dll и msvcr71d.dll
У меня так и не запустилась.

[andriano]

@Gmurik2

@andriano

Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.

А можно поинтересоваться какие?

На нормальных процессорах адресация ведется по словам, а не по байтам. Представь, что тебе на архитектуре Intel пришлось бы читать данные, в которых байты расположены не каждый по своему адресу, а 3 бита по одному адресу и 5 - по соседнему. А потом из этих фрагментов собирать нужные тебе байты.
Вот на 32-разрядной архитектуре примерно так надо будет работать с невыравненными данными.

@andriano

Коль скоро для координат используется int32, следовало бы указать, каким координатам (в вещественных градусах) соответствуют какие целые числа. Т.е. формулы преобразования.

Формула примитивна до ужаса lat = int32/10000000
так пока и не придумал как отойти от вещественных вычислений, Есть предложения получше?

На мой взгляд, наиболее естественным был бы вариант lat=int32/2147483647*180.0. Компьютер ведь работает в двоичной, а не десятичной системе.

@andriano

И еще: как разбирать поля, для которых указано n/a? Вероятно, если этому препятствует структура Qstring, то надо от нее отказаться, чтобы снять неопределенность в формате файла.
Кстати, что все-таки такое Qstring?

Этому препятствует то, что заранее нельзя знать длину QString.
QString это строка в UTF-8, при записи в файл, сначала указывается длина строки в байтах, а далее идет собственно строка по 2 байта на символ.

Кошмар!
При такой организации данные будут КАТАСТРОФИЧЕСКИ медленно читаться, т.к. вменяемая буферизация их будет крайне затруднена.
В такой ситуации следует собирать все строки переменной длины в отдельный массив, а в заголовке указывать только смещение в этом массиве (или в файле), чтобы заголовок имел фиксированную длину. Иначе на файловых операциях потеряешь в производительности порядки.

64-битные целые это уже насущная необходимость

Для компактных систем (типа навигаторов, КПК и телефонов) это пока неактуально.
Кстати, в заголовке я не обнаружил ни одного int64, с чего бы это?

[Shasoft]

@andriano

Этому препятствует то, что заранее нельзя знать длину QString.
QString это строка в UTF-8, при записи в файл, сначала указывается длина строки в байтах, а далее идет собственно строка по 2 байта на символ.

Кошмар!
При такой организации данные будут КАТАСТРОФИЧЕСКИ медленно читаться, т.к. вменяемая буферизация их будет крайне затруднена.
В такой ситуации следует собирать все строки переменной длины в отдельный массив, а в заголовке указывать только смещение в этом массиве (или в файле), чтобы заголовок имел фиксированную длину. Иначе на файловых операциях потеряешь в производительности порядки.

Извиняюсь, что влезаю в середину разговора. Но вообще-то такая организация файла работу никак не замедлит. При чтении байтов из файла как правило читается сразу блок данных, чтобы как раз избежать проблем со скоростью. Так называемое “упреждающее чтение”. Так что такое хранение никаких на скорость не повлияет.

P.S. Ещё раз извиняюсь, если сказал что-то совсем неверное. Попробовал найти обсуждение этого куска в предыдущих мессагах. Не получилось. Так что надеюсь я правильно понял суть высказываний andriano

P.S.S.Влез в тему, так как увидел знакомые слова про фиксированную математику, которая последнее время ненавижу всё больше.

[Alexey_Guseynov]

@andriano

@Gmurik2

@andriano

Кроме того, я бы настоятельно рекомендовал использовать поля, выравненные на границу 4. Иначе с обработкой на 32-разрядных процессорах будут большие проблемы.

А можно поинтересоваться какие?

На нормальных процессорах адресация ведется по словам, а не по байтам. Представь, что тебе на архитектуре Intel пришлось бы читать данные, в которых байты расположены не каждый по своему адресу, а 3 бита по одному адресу и 5 - по соседнему. А потом из этих фрагментов собирать нужные тебе байты.
Вот на 32-разрядной архитектуре примерно так надо будет работать с невыравненными данными.

Мне несколько лениво перечитывать весь тред. Речь идет о формате файла или о формате данных в оперативке. Если про файл, то при чем тут вообще адресация RAM? Не надо никакого выравнивания в файлах. Если про выравнивание в операвке, то компилятор лучше вас знает, что и как выравнивать. Например для ARM местами надо на 8 байт выравнивать.

@andriano

Кошмар!
При такой организации данные будут КАТАСТРОФИЧЕСКИ медленно читаться, т.к. вменяемая буферизация их будет крайне затруднена.
В такой ситуации следует собирать все строки переменной длины в отдельный массив, а в заголовке указывать только смещение в этом массиве (или в файле), чтобы заголовок имел фиксированную длину. Иначе на файловых операциях потеряешь в производительности порядки.

Вы сами буферизацию собираетесь писать? Или все-таки доверите это glibc и ОС? Кстати, упреждающее чтение работает намного лучше, если данные одним куском, а не размазаны по файлу. А на то, одинаковой ли длинны записи, glibc и ОС пофиг, они про эти самые записи ничего не знают.

А еще файл можно засунуть в память операцией memmap. И тогда замечательно будет работать кэширование в памяти блоков, к которым доступ производится наиболее часто (конкретная стратегия зависит от ОС).

@andriano

На мой взгляд, наиболее естественным был бы вариант lat=int32/2147483647*180.0. Компьютер ведь работает в двоичной, а не десятичной системе.

Обратите внимание, что замыкание координат при переходе через 180 меридиан получается автоматически за счет overflow. И в полной мере используется диапазон допустимых значений целочисленного типа.

P.S. Надо сделать typedef int32_t CoordType и в случае надобности можно будет использовать другой тип. Аналогично поступить со всякими идентификаторами и смещениями в файлах.
P.P.S. В stdint.h объявлены платформонезависимые типы uint32_t uint64_t int32_t int64_t и т.д.

[Ivan_Komarov]

@Alexey Guseynov

P.P.S. В stdint.h объявлены платформонезависимые типы uint32_t uint64_t int32_t int64_t и т.д.

Угу, только он не часть стандарта С++ и под виндой не во всех компиляторах доступен from the box.