Сначала немного общих соображений: в базе OSM имеется три типа данных: node way и relation. Узлы содержат координаты в формате «широта-долгота», траектории типа way позволяют прорисовывать на карте линии (точнее, ломаные, в т.ч. замкнутые) и представляют собой обычные массивы идентификаторов узлов, а данные типа relation могут содержать в качестве дочерних элементов не только узлы, но и данные остальных типов. Кроме того, все три типа могут иметь описания, представленные в модели EAV (Entity-Attribute-Value). Структурно в базе данных больше ничего нет.
Земля у нас шар, а окно видимости плоское. Координаты объектов в базе заданы в виде «широта-долгота», и это нам представляется не вполне разумным. Объёмы карты (по крайней мере, самого малого масштаба) просто гигантские, но пользователю нужно обеспечить эффективный доступ к любому уголку планеты для карты любого масштаба — как для чтения, так и для редактирования. Какой из всего этого вывод? На мой взгляд, очевидный: каждая из карт разрезается на дольки в размер более-менее терпимого объема (в смысле скорости закачки).
Разрезается именно на сервере, т.е. одни и те же куски передаются одинаковыми для всех пользователей. Ещё один момент: хотя координаты являются числами и, следовательно, могут храниться в двоичном формате, браузеру придётся передавать только текст. Решение этой проблемы давно известно: двоичные данные передаются в кодировке base64, когда из 8 бит байта несут информацию только 6. Правильнее сказать, целых 6 — формат весьма компактный. Вот такую 64-разрядную систему счисления мы и будем использовать.
Координаты объектов на карте лучше всего задавать так, чтобы объём передаваемых данных был минимальным. Нам представляется удачным решение, когда широта и долгота (или, на плоскости, X и Y) задавались бы одним символом (в формате base64), что позволяет позиционировать элемент как клетку шахматной доски размером 8*8 (единиц длины соответствующего масштаба). То есть двумя символами мы можем позиционировать элемент уже на карте 64*64, тремя — 512*512, а восемь символов (девятый — код самой карты, как будет показано ниже) обеспечивают нам точность указания координат 134217728*134217728, что более, чем достаточно даже для самой точной карты (для планеты Земля это означает позиционирование объектов с точностью менее полуметра). Вам мало? Можете добавить ещё 2-3 символа! А я бы ещё и убавил один — точности в пару шагов тоже предостаточно.
А как получить стартовый набор (плоских) карт самого грубого масштаба? Очень просто!
- Разрежем Землю по экватору и избавимся от отрицательных значений широты. Отныне лишь один бит будет определять, северное это полушарие или южное (сам экватор отнесём к северному полушарию, чтобы не дублировать лежащие строго на нём объекты).
- Сделаем ещё две пары сечений: по 32-му и 64-му градусу по широте. Теперь планета поделена на 6 областей: две «полярные шапки», две «приэкваториальные» области и две зоны «средней полосы».
- На каждую из «полярных шапок» посмотрим сверху (это называется «азимутальная проекция»). Мы увидим круг с центром в полюсе, граница которого проходит по 64-й параллели. Опишем вокруг этого круга квадрат — так, чтобы он касался круга в точках пересечения этой параллели с Гринвичем и 90-м меридианом, а сами эти меридианы (в азимутальной проекции они выглядят как прямые) разрежут этот квадрат на 4 равные части. Это и будут карты самого грубого масштаба.
- Оставшийся «бочонок» (Земля без «полярных шапок») разрежем по меридианам с шагом 30 градусов, начиная от Гринвича. Таким образом, планета разрезана на (12+12+4) * 2 = 56 почти плоских карт, каждую из которых (и каждую из дочерних) мы при дальнейшем позиционировании считаем квадратом 8*8. Код дочерней карты также передаётся одним символом, т.е. дочерняя карта соотносится с родительской как клетка шахматной доски с самой доской.
А теперь посмотрим, с какой точностью заданы координаты объектов в базе данных OSM. МАМА ДОРОГАЯ! Семь знаков после запятой! Господа, да вы что, СДУРЕЛИ?! Вы действительно указываете координаты очертаний домов, береговой линии континентов и всё остальное с точностью до долей сантиметра?! Позвольте вам не поверить! Впрочем, можно и поверить: пусть даже это не полный бред, а чистая правда, но скажите мне, кому и зачем нужна такая сумасшедшая точность? Это же идиотизм! Нет, мы пойдём другим путём!(с)
Теперь вспомним, что земная поверхность у нас весьма неоднородна. Что-то мне подсказывает, что информационная насыщенность квадратного километра карты в центре Парижа будет несколько выше, чем у такого же километра в центре Тихого океана. Что будем делать?
Правильно: вовсе не обязательно, чтобы все дольки этой «шоколадки» имелись в наличии. Если на соответствующей карте объектов слишком мало, они просто прописываются на родительской карте, а эта в БД не хранится и пользователю не передаётся. Как узнать, что информация на карте предназначена для одной из дочерних? Элементарно! Формат записи координат объектов на карте любого масштаба один и тот же, поэтому если объект указан для дочерней карты на карте родителя, его код удлиняется на один байт (идентификатор карты относительно родителя + координаты), для внука — ещё на один, и так до карты самого мелкого масштаба. Таким образом, для карты «дециметровой точности» длина идентификатора объекта не превышает 9 байт в «абсолютных» координатах (для всей БД в целом) — это даже меньше, чем длина большинства идентификаторов узлов, представленных сейчас в БД. Но ведь наш идентификатор содержит теперь всю информацию о его географическом положении! Стало быть, следующие два поля структуры node (lat/lon) больше не нужны, и потому подавляющее большинство узлов становятся литеральными объектами (не адресуемыми самостоятельно в БД и существующие только в составе родительских объектов, каковыми для узлов являются траектории). Нам больше не нужно копаться в БД, чтобы по идентификатору узла получить его координаты, да и объём базы узлов сократится примерно втрое и, соответственно, объём всей БД примерно на треть! Даром! Наконец, автоматически убираются ошибки в данных вида, когда узлы с разными идентификаторами имеют одинаковые координаты или, наоборот, для одного и того же идентификатора в разных местах БД указаны разные координаты.
Важный нюанс: точка, заданная координатами на текущей карте или на любой из родительских вышеописанным способом — это одна и та же точка: она предназначена для карты одного и того же масштаба. А вот траектории, заданные для карт разных масштабов — это уже другие, живущие собственной жизнью геометрические объекты! Даже если они описывают один и тот же объект логического уровня. Пример: очертания какого-либо озера на карте мелкого масштаба могут описываться данными типа relation — например, по причине имеющегося ограничения на количество точек (не более 2000) в данных типа way. На карте более крупного масштаба то же озеро может уже «уместиться» в объект типа way, на ещё более крупном — выродиться в точку, а на остальных вообще исчезнуть с карты. А вот описание этого объекта (внегеометрическое), разумеется, должно быть одним и тем же объектом, связанным с его геометрическими описаниями на каждой из карт, где он присутствует.
По нашей задумке, сами идентификаторы узлов отныне и будут содержать всю необходимую информацию о своих координатах. При этом выявляются ошибки вида:
- Не найдены дочерние элементы, на которые есть ссылки из родительских (отдельно для каждого типа данных). Родительские элементы, содержащие такие ссылки, помечаются как «потенциально бракованные».
- Не найдены элементы, для которых имеются описания. Очевидная ошибка в БД.
Тип node
Основная масса узлов переводится в литеральные значения траекторий типа way. При этом возможны варианты:
- Все узлы данной траектории благополучно конвертированы в новый формат. Успешное завершение процесса конвертации, так и должно быть.
- Хотя бы один узел траектории не удалось перевести к новому формату. Ошибка в данных, траектория помечается как «бракованная».
После завершения конвертации мы, помимо набора «бракованных» траекторий можем получить и массив «ненужных» узлов, которые не принадлежат ни одной траектории. Это ещё не означает ошибку в данных: ведь узлы могут принадлежать траекториям типа relation или быть самостоятельными элементами БД, имеющими собственное описание. Если этих связей не обнаружено, такие узлы должны быть удалены как «мусор».
Как ни странно, при переводе траекторий типа way в новый формат данных не было обнаружено ни одной бракованной! Это означает высочайшее качество данных, которое, конечно, обеспечивается программным обеспечением OSM — люди настолько безошибочно работать не могут! А вот с другими данными дела обстоят заметно хуже. В частности, обнаружено 312057 траекторий типа way, которые не только не имеют описаний, но на них никто и не ссылается. Что с ними делать? Выбросить? Или пометить как бракованные и натравить на них волонтёров? На карте ведь всё равно какие-то линии ими могут быть прорисованы. Ладно, пока оставим. Узлы-пустышки выбросим, а траектории-пустышки оставим. Но вообще, объект без описания — это ненормально, это ошибка. И таких объектов в базе не так уж и мало — тех же way-траекторий без описаний более 12 миллионов!
Забавно, но, как оказалось, в Монако и на Азорских островах нет ни единой траектории, которая не дублировалась бы в каком-то другом файле. Оно и понятно: попробуй-ка нарисовать карту Франции, чтобы не зацепить Монако! Азоры — это, разумеется, Португалия. Столь же понятно, почему Антарктида, Куба, Мадагаскар или Мальдивы не имеют ни одного дубля в других нарезках. А вот траектория с ID rel=148838 дублируется аж в 64 файлах! Нетрудно догадаться, что она называется «административные границы США».
В большинстве случаев данные, дублирующиеся в разных файлах, полностью совпадают. Но встречаются и отличия! А это означает, что эти дубли представляют собой физически разные записи, живут своей жизнью и требуют синхронизации изменений в них (что не всегда удаётся). Кстати, использование предложенного формата записи координат автоматически убирает ошибки этого вида.
Как будем исправлять ошибки? Да очень просто! Ссылки на отсутствующие в БД элементы игнорируем, а данные из разных нарезок тупо сливаем в одну: либо они полностью поглощаются (нет ошибок рассогласования), либо имеем некоторый «дребезг» при прорисовке траектории (если они похожи друг на друга). Если же они совсем непохожи — что ж: мы уже пометили траекторию как бракованную.
Все эти проверки, хотя и довольно громоздкие по времени выполнения, имеют весьма простые и очевидные алгоритмы: это фактически проверка уникальности тех или иных идентификаторов (без значений информационных полей), иногда совмещённая с операциями пересечения или объединения тех или иных множеств. Последняя проверка чуть сложнее: проверяется уникальность идентификаторов траекторий вместе с полем порядкового номера узла в траектории (также без значений).
Очевидно, что основная (и, возможно, единственная) ценность траекторий типа relation — они работают как контейнеры дочерних элементов. Попытка привнести туда рёберную информацию (если рассматривать БД как граф) с помощью насильственно втиснутого атрибута role явно не удалась — достаточно сказать, что львиная доля элементов данных в этих траекториях (61.5%) значением этого атрибута имеют пустышку (role=""). И вообще редакторы БД плохо понимают что с ним делать — здесь сплошь и рядом встречаются описания (место которым в данных формата EAV — например, URL) и просто мусор. Самыми распространёнными значениями атрибута являются outer, inner, forward, stop, from, to, via, информационная ценность которых стремится к нулю. Немало и явно описательных значений (house, platform, street, admin_centre, subarea). Ладно, пока оставим — возможно, приткнём кое-что в описания.
Масштабирование
В новом формате записи координат подготовка карт разных масштабов тривиальна — она заключается всего лишь в обработке данных типа way. В самом деле, информация о местоположении точечных объектов на карте любого масштаба содержится в их идентификаторах уже сейчас, а траекториям типа relation (не говоря уже про описания) и вообще нет никакого дела до карты — они просто группируют дочерние объекты по измерению принадлежности. Да и сам алгоритм формирования траекторий для карты очередного масштаба намного проще и быстрее, чем даже процесс конвертации данных в этот формат. Отметим, что не только полигон фактически ничем не отличается от любой другой линии (просто первый и последний элементы совпадают), но и одиночный узел есть та же ломаная, состоящая из одного элемента. Таким образом, мы вообще избавились от типа данных node — отныне вся «геометрия» представлена только элементами типа way, которые, при необходимости, собираются в контейнеры типа relation и имеют описания в формате EAV. Их идентификаторы — последнее, что связывает [пока ещё] нашу БД с исходной базой OpenStreetMap.
Алгоритм формирования комплекта карт всех масштабов полностью автоматизирован и выглядит следующим образом: у элементов траекторий типа way карты текущего масштаба отрезается последний символ, после чего убираются образовавшиеся (идущие подряд) дубли. Затем из общего массива выделяются группы схлопнувшихся в точку траекторий, а также группа «отрезков» — траекторий, в которых осталось ровно два узла. Ни те, ни другие на карту более грубого масштаба не переносятся (если не будет найдено убедительных аргументов за то, чтобы их оставить на формируемой карте). Остальные траектории (если не будет найдено убедительных аргументов за то, чтобы их не переносить на карту нового масштаба) образуют новую карту и процесс повторяется. Комплект карт готов!
Я знаю, что вы знаете, что «гладко было на бумаге»! Простейший (и нокаутирующий) вопрос: «Если масштабирование выполняется столь просто, то почему же до сих пор нет этого набора карт»? Ведь его вообще нет! Это мы так лихо описали (и даже реализовали) алгоритм: траектории, состоящие из одного узла и «отрезки» на карту следующего масштаба не переносятся. А на деле? Разве кому-то непонятно, что Храм Василия Блаженного на любой карте должен быть гораздо заметнее, чем какая-нибудь «хрущёвка» или современная железобетонная коробка — пусть даже намного более крупная! Так что решение о существовании любого объекта, включая точечные, должно приниматься индивидуально для карты каждого масштаба. И алгоритмы этих решений не такие уж и простые. Скажем, какой-нибудь задрипанный «Учкудук», в котором всего-то «три колодца» в «горячей пустыне» очень даже важный ориентир, а кому он нужен вне её? Тем не менее, техническая часть подготовки карт разных масштабов действительно проста именно в той степени, как это описано.
Точка имеет параметры «широта» и «долгота» (в желаемых свойствах предлагается добавить третий параметр — «высота»).
Вот уж нафиг! Вы что, собрались задавать рельеф в растровом формате?! Совсем сдурели? Только векторный! Тем более, что все эти изолинии принципиально ничем не отличаются от любых других с точки зрения обслуживающей математики. Впрочем, раз в базе объёма нет, то и нам он нафиг не нужен. Схема у нас гибкая, и рельеф (если он когда-нибудь вообще появится) спокойно подключается в любой момент как отдельный слой видимости.
А теперь немного поработаем с EAV. Наша задача — отрезать наиболее раздражающий мусор, и структурировать то, что может хоть как-то структурироваться. Обработку ведём, ориентируясь на типы данных, хотя общий принцип одинаковый: выдёргиваем из общей кучи данные под самыми популярными тегами, и отправляем их либо на свалку, либо в какое-то подобие структур. И даже не с тегами, а просто с данными! Кто, собственно, сказал, что метаданные расположены именно в тегах? Как говорится, должны, но не обязаны. Вот и проверим.
Вот иллюстрация (часть описания для узла с ID=1027246737 под префиксом tiger):
tlid=147661845:147661846:147661853
upload_uuid=bulk_upload.pl-9e2fc80e-9312-407e-9603-ca030ab40414
Вот скажите, только честно: вам хочется ковыряться в подобных данных в надежде выловить оттуда полезную информацию? Вот и я не хочу. Тем более, что неряшливость составителей БД уже многократно доказана. Вместе с тем, имеется довольно много данных (street_num, city_id и т.д.), которые являются фактически мусором для конечного пользователя, но могут оказаться полезными для структуризации (выявления и исправления ошибок в данных).
Итак, пристегнулись ремнями, пронумеровали кости… ныряем! Но только не в этой заметке.
Комментарии (51)
Alek_roebuck
19.04.2019 20:47+8Вы не пояснили, чем вам не угодили сферические координаты. Или код Мортона. С точки зрения экономии места, которое, похоже, для вас основная цель, сферические координаты должны получиться [на мизерную долю] выгоднее. Если вы надеетесь таким образом упростить вычисления расстояний, обойдясь без богомерзкой «формулы говерсинуса», то с широтой-долготой можно обращаться гораздо проще по обычной теореме Пифагора с поправкой на косинус широты: на масштабах до сотен километров ошибка пренебрежимо мала, а специальная формула (медленнее Пифагора, но заметно быстрее «говерсинуса») даёт даже большую точность, чем «говерсинус», потому что подогнана под референц-эллипсоид. Причём, в отличие от «говерсинуса», она ещё и официально рекомендована геодезической службой США.
Идея сжимать данные, учитывая то, что часть контура одного объекта совпадает с частью контура другого объекта, не нова, я на неё наталкивался. Не помню, почему она не используется — видимо, неудобна. Потому что вообще-то она используется в критических случаях: для границ между странами или даже адм. регионами, это особенно важно для репутации геосервиса в случае территориальных диспутов. Но, хотя реализация уже существует и экономит место, территории всё-таки все описывают полным контуром — потому что так очевидно удобнее.rybvv Автор
19.04.2019 21:03Объясняю: новый формат данных, имеет, на мой взгляд, следующие преимущества:
1. Идентификаторы узлов содержат всю информацию об их географическом положении, то есть ссылочные значения переводятся в литеральные, и при прорисовке ломаных уже не нужно обращаться в БД за координатами по их идентификаторам. Эт не только скорость, но и упрощение обслуживающей математики.
2. Обычная сортировка данных группирует их уже не по линиям (горизонталям или вертикалям), а по площадям.
3. Имеется возможность на одной карте задавать координаты для карт разных масштабов, то есть строить иерархическую систему карт, в зависимости от их насыщенности объектами.
4. Автоматически убираются ошибки вида «один ID с разными координатами» и «разные ID с одинаковыми координатами». В частности, все имеющиеся сейчас в OSM 50 Южных полюсов в этом формате автоматически схлопнутся в одну точку.
5. Построение карты более грубого масштаба из более мелкого тривиально до неприличия: последний символ просто отбрасывается.
6. Объём данных в этом формате сокращается примерно втрое.
Ну и, наконец, любой луч из центра пересечёт поверхность шара в одной точке, но и предлагаемый 56-гранник он пересечёт тоже в одной точке, так что между разными форматами записи координат имеется взаимно однозначное соответствие, и при желании можно пользоваться любым из них, написав несколько конвертеров.
Это не «идея сжимать данные» — это идея убрать дубли (тем более, РАЗЛИЧАЮЩИЕСЯ дубли) из разных нарезок по странам (например, Франция-Монако) и вообще в «пограничных» зонах.Alek_roebuck
19.04.2019 21:19+33. Имеется возможность на одной карте задавать координаты для карт разных масштабов, то есть строить иерархическую систему карт, в зависимости от их насыщенности объектами.
5. Построение карты более грубого масштаба из более мелкого тривиально до неприличия: последний символ просто отбрасывается.
6. Объём данных в этом формате сокращается примерно втрое.
Всё вышеперечисленное обеспечивается кодом Мортона. Ваши грани, получается, нужны лишь для более адекватного картографирования окрестностей полюсов, где из объектов-то, собственно, только сам полюс и есть. И при этом разбиение глобуса на грани усложняют расчёты в окрестности рёбер, которые проходят в таких важных местах, как Лондон и Санкт-Петербург, Чикаго и т.п. Ещё меньше повезло Новому Орлеану, который оказался в районе вершины вашего многогранника: добираться оттуда в соседний Джексон придётся через два ребра.rybvv Автор
20.04.2019 09:24Я первый раз слышу про код Мортона, заглянул в Вики — там какой-то кошмар: многомерное пространство, чередование двоичных цифр координатных значений, дерево квадрантов, рекурсивная Z-образная кривая, округленный вниз двоичный логарифм каждой точки… ЗАЧЕМ это всё?! Здесь же просто гео-координаты! Просто каждая карта рассматривается как квадрат, а «разбиение глобуса на грани» нужно для независимого хранения данных, которые в формате OSM не просто дублируются в нарезках разных стран, но и даже представляют собой физически разные объекты! Какие проблемы с Новым Орлеаном? Не понимаю совершенно. Мне казалось, что если попадётся какой-нибудь сарай, лежащий на стыке четырёх карт самого крупного или чуть более мелких масштабов, это может вызвать какие-то смешные проблемы, но даже его мне ни разу пока что не попалось. А после масштабирования до одного символа (только код карты, одной из 56) в базе осталось только несколько элементов — Енисей, помню, туда прорвался и ещё что-то, по мелочи.
56 карт у меня получилось почти автоматически: я хотел чтобы код карты кодировался одним символом в формате base64, и чтобы даже самую грубую карту можно было рассматривать как плоский квадрат без особых искажений элементов на ней. А если ещё и нормально разметить коды (большие буквы латинского алфавита относятся к северному полушарию, малые — к южному, начальные буквы — приэкваториальные карты, далее — карты средней полосы), то уже первый же символ записи координат становится чрезвычайно информативен! Каждый следующий — тоже. Даже длина несёт информацию! Компактность кода весьма приличная — к тому же, его можно передавать браузеру «в готовом виде»… ну сказка же!
Hardcoin
19.04.2019 22:33+1любой луч из центра
Возможно, я что-то недостаточно хорошо понимаю, но луч из центра любой выпуклой фигуры пересечёт поверхность только в одной точке.
rybvv Автор
20.04.2019 09:43Вот и славно! Я просто хотел акцентировать: хотя новый формат выглядит «страшненько», но там те же самые координаты, как и были, только для браузера. Вот, например, одна из траекторий Монако в этом формате:
164243289
MGyR6Rckm
MGyJynt6_
MGyR627J6
MGyJxrqNL
MGyJyln93
sshikov
19.04.2019 22:30Почему не используется? Этот формат называется topojson, если я ничего не путаю.
Alek_roebuck
19.04.2019 22:50Ну, я знаком с одной известной картографической системой изнутри и ещё с несколькими — постольку-поскольку. На практике ведущие компании (которые я называть не буду из-за NDA, но речь о минимум трёх коммерческих и двух краудсорсовых) свои города и районы хранят в виде многоугольников (MULTIPOLYGON в WKT/WKB, Polygon в Shapefile или как-то так). Потому что экономия места от топоджейсона незначительная, а возни много. «Геополитические данные» (границы стран и спорных территорий) обрабатываются отдельно.
sshikov
20.04.2019 09:25Если вы хотите сказать, что он используется мало (меньше, чем может быть заслуживал бы) — то я вполне согласен. Но где-нибудь на клиенте, где память и ресурсы вообще ограничены, при отображении (особенно при помощи D3, автор которого кажется topojson и изобрел) — он вполне себе распространен.
Ну и сама идея сжатия путем выкидывания совпадающих отрезков границ (и еще сжатия самих координат) — она давно известна, и в общем применяется. И эффект от нее есть — размер уменьшается в разы.
extempl
19.04.2019 21:22+1А теперь посмотрим, с какой точностью заданы координаты объектов в базе данных OSM. МАМА ДОРОГАЯ! Семь знаков после запятой! Господа, да вы что, СДУРЕЛИ?! Вы действительно указываете координаты очертаний домов, береговой линии континентов и всё остальное с точностью до долей сантиметра?!
Точность может быть, например, потенциальная, или для записи/чтения координат для всяких роботов-пылесосов-газонокосилок-доставщиков. Может быть на карте эта точка от ближайших десяти и не отличается, но в записи робота это может быть не так (например, точка вылета, она же точка возвращения).
rybvv Автор
20.04.2019 09:46Ага, особенно если учесть, сколько там ошибок. Взять хотя бы те же 50 Южных полюсов. :)
Ах, да — зачем нам потенциальная точность? Нужна именно кинетическая!
saege5b
20.04.2019 19:10Кое-где, давно-давно, в свидетельствах на землю, координаты земельного участка описывались в румбах с точность до градуса :)
Кому-то тоже показалось, что можно съэконмить на записи.rybvv Автор
20.04.2019 20:17Да не экономьте, Господи! Этот формат ТОЖЕ позволяет записывать координаты С ЛЮБОЙ точностью! Просто это маразм, указывать координаты с точностью до долей сантиметра!
VJean
20.04.2019 20:35Это не маразм, а реальность. Никому не нужны лишние такты на преобразование координат, особенно на слабом железе. Уж молчу про хранение в базе с обработкой пространственных запросов.
rybvv Автор
20.04.2019 20:41Какая это «реальность»? Это именно дурость: дают координаты в формате float, которые не имеют ничего общего с действительностью. Указывать координаты домов, дорог, береговой линии с точностью до долей сантиметра — это именно маразм! И никак иначе! И «слабость железа» не имеет к этому ни малейшего отношения. Это вообще база данных — при чём тут железо? Это ДАННЫЕ! А если уж Вы беспокоитесь за скорость, так замените айдишки узлов в траекториях непосредственно их координатами. В ЛЮБОМ формате!
VJean
20.04.2019 21:29Не float, а double.
WGS84 EPSG:4326, пожалуй, самая распространенная система координат в картографии и навигации, что позволяет без проблем использовать её без всяких преобразований и прочих заморочек практически везде.
Про читабельность вообще молчу. «37.617635 55.755814» приблизительно можно понять куда указывает координата. «MGyR6Rckm MGyJynt6_ ...» — что тут происходит?
Если так нужно уменьшить размер базы и точность до метров, то что мешает округлять координаты?rybvv Автор
21.04.2019 11:20Господи, float4m float8 — какая разница? А читабельность предназначена для компьютера, а не для человека — он прекрасно понимает, куда указывает координата — куда нагляднее, чем lat-lon. И дело не в уменьшении размера базы (это просто дополнительный пряник) дело в удобстве обработки, скорости доступа, верификации, исключении дублирования, возможности автономной обработки разных частей БД… в общем, это я уже перечислял. Например, в этом формате я подготовил полный комплект карт всех масштабов фактически в полностью автоматическом режиме — а что прикажете с «наглядными» координатами делать? Их неремонопригодность фактически доказывается недавно появившейся здесь заметкой о том, что всю БД OSM нужно выбросить и создать заново, с нуля!
Ну и Оккамом прошёлся чуток — данные типа node вообще исчезли из базы!
Jef239
21.04.2019 00:04+17 знаков после запятой — это всего лишь 11 миллиметров по широте.
И да, нам лично — это существенно. Погорели уже на сантиметровой точности. Оказалось — мало.
История такая. Ведем комбайн в ручном режиме, отмеряем две точки — А и В. На расстоянии 10 метров друг от друга. Далее комбайн в автовождении едет по этой линии, а бортовой комп — эту линию и траекторию комбайна отрисовывает.
Ошибка каждой точки — до 1см. Между точками — 10 метров. На расстоянии в 1 км (а поле бывает и 2-3 км) расхождение будет — 2*1000/10 = 200 см., то есть до 2х метров.
Получается, что автовождение рапортует расхождение в 5 миллиметров, а карта показывает — 2 метра.
Пришлось делать маразм — после установки точек на карте и определения курса передавать его обратно в блок автовождения. Ибо увеличивать точность картографического можлуя — выйдет сильно дороже.
Так что для разных работ — лучше точки ставить с точностью 0.1 мм. Шум измерений 5-7 мм СКО не надо его усиливать дробным шумом карты.rybvv Автор
21.04.2019 11:28Сударь, там ошибок НЕМЕРЯНО! Вы всерьёз доверяете этой точности? К тому же, с какой радости у Вас ошибка накапливается? Ну, допустим, будут точки с точностью 1 метр на расстоянии 100 километров — и чего? Точность координат каждой точки ВСЁ РАВНО один метр! Так что Ваш комбайн и через 100 километров не должен промахнуться более, чем на метр! :) Вы знаете, например, что в базе есть одинаковые айдишки с разными координатами? Как я когда-то писал:
При переводе координат в новый формат автоматически убираются ошибки вида: «узлы с разными ID, но с одинаковыми координатами». Как правило, это ошибки округления (в районе 5-6 знака после запятой), но не только. Также автоматически убираются ошибки вида: «узлы с одинаковым ID, но с разными координатами». Так что Вы там «миллиметрите»? :)Jef239
22.04.2019 13:56Вы путаете 2 разные вещи. Одно дело — статические объекты на карте. Другое дело — работа с картографическим софтом. Теоретически, я вполне представляю себе софт, у которого разная точность для статических объектов и для нарисованных поверх них точек и линий. Практически, в имеющихся движках, эти точности совпадают и равны, увы, точности float. А её — откровенно мало.
Ну вот ещё пример, более наглядный. Делаем сравнительное испытание RTK-приемников. Декларированный шум каждого — 5 мм СКО. Накладываем траектории на карту. Что мы увидим? Да прежде всего дробный шум карты в 1 см и увидим. Отличия в качествах приемников просто пропадают за шумом карты. Ну вот вам пример сравнительного теста приемников с точностью 3 метра СКО. А нам нужно то же самое, но точность в 600 раз лучше. Причем нам не важен сдвиг координат на карте — это мы можем скомпенсировать. А вот соблюдение формы — очень интересно.
Картинка из статьи по ссылке
rybvv Автор
22.04.2019 16:07Не понимаю. Ваш трактор по гироскопу едет? Или как-то иначе определяет СВОЁ местоположение? Если Вы находитесь, скажем, в километре от точки-ориентира, то какая разница, какая там у неё точность: миллиметр, сантиметр, метр или даже 10 метров? Всё равно Вы поедете точнёхонько в ту же сторону.
Насколько немеряно — я не знаю, но те же 50 Южных полюсов говорят сами за себя. А уж сколько разного дерьма в описаниях — это вообще тихий ужас!Jef239
22.04.2019 16:45Ну а что тут непонятно. Есть статическая подложка — карта и есть динамические данные на ней. Ну принято так в индустрии в качестве подложки — использовать карту. При этом точность подложки — никого не волнует.
Беда в другом. Точность отрисовки динамических данных — примерно такая же, как дробный шум их отображения движком карты. Да, можно не использовать карту и сделать отдельный движок для траекторий. Но это — лишняя работа, поэтому все используют картографические движки. А у них, увы, точность отображения координат наших траекторий — 1 см.
Чувствуете как нелепица? Координаты с СКО 5 мм отображаются на сетке с шагом 1 см.
Как бы вам на пальцах объяснить? Ну вот представьте, вы попали в ДТП. Инспектор рулеткой измеряет, строит схему. Какая вам разница, что схема сдвинута вдоль дороги на 10 метров? Да никакая. А вот разница между «задели» и «не задели» может быть в пару см.
Ваш трактор по гироскопу едет?
По GNSS (GPS+ГЛОНАСС) в режиме RTK. Гироскопы дороги и прилично уходят. Самолетные — чуть ли не по миле в час, например.
Если Вы находитесь, скажем, в километре от точки-ориентира, то какая разница, какая там у неё точность: миллиметр, сантиметр, метр или даже 10 метров?
Тут вы правы — никакой разницы. А вот едем ли мы прямо (5 мм болтанки) или болтаемся на 2-3 см в сторону — разница есть.
P.S. Скоро будут автомобильные навигаторы с СКО 30 см. Так что довольно быстро дороги будут отрисованы с точностью, достаточной для прямого определения, в какой полосе машина едет.rybvv Автор
22.04.2019 21:41Чесслово не понимаю! Я в молодости немного игрался с алгоритмом маловысотного полёта, когда самолёт (ну или там крылатая ракета) должен уворачиваться от всяких там зениток и рельефа местности, но карта была вполне себе статичной. Но и там ограничение пространства поиска определялось скорее техническими возможностями — ну нельзя мгновенно повернуть на 90 градусов ли даже на 10! А почему ошибка может накапливаться — не понимаю! Наоборот, она должна корректироваться по маякам!
Ладно, спорить не буду — тем более, что предлагаемый формат в принципе позволяет указывать координаты с ЛЮБОЙ точностью, но странно как-то это всё… :)Jef239
22.04.2019 22:06А почему ошибка может накапливаться — не понимаю!
Потому что синус малого угла — это величина малая, но не ноль.
У нас есть две линии курса — одна на карте, проведенная по точкам. Вторая — реальная траектория, по которой едет комбайн. Комбайн пользуется своим курсом, вычисленным точно. А на карте, из-за погрешности в задании координат, курсовая линия проведена не точно.
Если мы ставим две точки, задающие линию, на расстоянии метр, то отличие в курсе может быть до градуса. Если на расстоянии 10 метров — до 0.1 градуса.
Наоборот, она должна корректироваться по маякам!
Зачем? Задача конкретно этого «автопилота» — вести строго по заданному курсу. Взяли 2 точки, просчитали по ним курс и едем по нему. Раз в секунду считаем координаты, смотрим отклонение от курса и чуть-чуть подруливаем. То есть фактически — рулим по спутниковому компасу.
уворачиваться от всяких там зениток и рельефа местности, но карта была вполне себе статичной.
Отобразите на карте траектории полета ракет и текущие сектора облучения радаров. И сразу поймете, что они важнее, чем картографическая подложка.
но странно как-то это всё… :)
Ну странного здесь только применение картографической основы как подложки для рисования траекторий. Но так принято делать.rybvv Автор
23.04.2019 09:36И что? Синус малого угла — это результаты вычислений, а не измерений координат. Траектория на карте — это же ломаная! И там нет никаких синусов — есть именно координаты точек. Так с какой стати «на карте, из-за погрешности в задании координат, курсовая линия проведена не точно»? И что значит «зачем»? Как раз затем, чтобы знать, насколько расходится то, что мы там насчитали с действительностью.
Ничего подобного! Картографическая подложка не менее (если не более!) важна, чем «сектора облучения радаров». Для того, чтобы снизить вероятность поражения, мы должны лететь «как крокодилы, низенько-низенько». И если мы летим в условиях сложного рельефа (грубо говоря, где-нибудь в Гималаях), то рельеф обладает куда более высокой «поражающей способностью», чем какие-то там радары, которые даже если что и заметят, всё равно ничего не успеют сделать, а если даже успеют, то наверняка промажут. :) А вот если мы залетели в зону, откуда не способны выбраться из-за технических ограничений на маневренность нашего «летательного аппарата», тут нам и кранты!
hippohood
19.04.2019 21:51А какая у вас будет точность при пересечении граней? У меня ощущение что вы Землю представили в виде какого-то правильного многогранника. Для настоящих карт мы используем эллипосоид потому что так быстрее и дешевле. И желательно подогнать элипсоид так чтобы он повторял эквипотенциальную поверхность какую-нибудь. Поэтому для локальных карт используются разные элипсоиды — тот элипсоид который хорошо подходит в Европе, даёт очень большую ошибку в Бразилии, и наоборот. Поэтому все так сложно
mistergrim
19.04.2019 23:30+1Земля ещё и не эллипсоид, а геоид.
Akdmeh
20.04.2019 05:58+3Замечу, что это схематическое изображение карты гравитации земли. Реальная форма — это почти идеальный шар почти без видимых искривлений (да, немного приплюснутый, но незаметно). В космосе вы подобной формы как на картинке не увидите, посмотрите на любую спутниковую фотографию Земли.
Еще немного подтверждений: www.sciencealert.com/don-t-be-fooled-by-a-viral-gif-that-claims-earth-is-actually-lumpy-not-roundmistergrim
20.04.2019 10:23Ну я думал, все знают, что это утрированное изображение. Гравитация в общем-то в таких пределах тоже не меняется. И зависито она, как раз, в основном от формы.
Akdmeh
20.04.2019 10:27К сожалению, эта картинка часто ходит в группах направленности: «От нас скрывают» с текстом: «а вы знали, что вот так на самом деле выглядит форма Земли?».
Поэтому решил уточнить, вдруг Вы тоже неправильно поняли это изображение.
rybvv Автор
20.04.2019 09:47Да та же самая! Новый формат позволяет задавать координаты С ЛЮБОЙ точностью. Я же предлагаю ограничиться РАЗУМНОЙ точностью. Только и всего.
aamonster
20.04.2019 11:39Ужас. На ровном месте создать себе проблемы с переходом через рёбра вашего многогранника? С каким-то сложным и трудноотлаживаемым кодом, когда надо посчитать расстояние между точками на разных гранях?
Меркатор используется потому, что он прост.
Впрочем, что я беспокоюсь? Ваш подход всё равно не примет никто из тех, от кого зависит развитие OSM (для них проблемы очевидны).
ЗЫ: а если вас беспокоит количество знаков для хранения данных
rybvv Автор
20.04.2019 14:04Убей, не понимаю, чем метод расчёта расстояний на одной грани сложнее, чем на разных. :)
Нет, меня беспокоит количество ошибок, исчисляемое многими миллионами, и то, что здесь недавно прошла статья, что OSM надо выбросить и создать заново.
Zverik
20.04.2019 13:10Всё здорово (хотя и слишком сумбурно, чтобы кто-нибудь понял), но получается, вы изобрели векторные тайлы и идентификацию точек координатами (ну ещё и очень странный алгоритм упрощения линий). Всё это либо обсуждалось и признано недостаточно гибким вне специфичных применений (идентификаторы), либо после десятка итераций стандартизовано и широко применяется почти всеми, кто имеет отношение к картам (тайлы, симплификация, топология). Даже про точность люди задумались: посмотрите гугловские полилинии, например. Хотя тут ответ должен быть ещё сложнее, с упоминанием киноплёнки и прочего, но суть в том, что все эти мысли уже подумали.
VJean
20.04.2019 16:17Пожалуйста, переведите статью. Автор изобрел квадродерево?
А теперь посмотрим, с какой точностью заданы координаты объектов в базе данных OSM. МАМА ДОРОГАЯ! Семь знаков после запятой! Господа, да вы что, СДУРЕЛИ?! Вы действительно указываете координаты очертаний домов, береговой линии континентов и всё остальное с точностью до долей сантиметра?
В сыром дампе osm координаты в нодах заданы для эллипсоида WGS84 (проекция EPSG:4326). Для тайлов — EPSG:3857 (Веб-Меркатор) Google Web Mercator: неоднозначная система координат.
Резюмирую: не используйте велосипеды, там где не надо.rybvv Автор
20.04.2019 20:22Нет, автор даже и не слышал никогда про квадродерево. И уж чего-чего, а дерева у него нет и в помине — здесь всего лишь формат записи географических координат. И вообще, автор деревья не любит, предпочитает работать с графами общего вида. :)
InterceptorTSK
20.04.2019 22:34+1Нет, автор даже и не слышал никогда про квадродерево.
Ну так услышьте)
Возьмите четыре квадратика, и впишите их в квадрат.
Эти четыре квадратика будут иметь коды 0,1,2,3, например по часовой стрелке. Самой собой для их кодирования нужно два бита, т.е. 00, 01, 10, 11, а так же это четверичная система счисления.
Каждый из этих квадратиков что выше так же можно разбить на 4 квадратика, и ровно так же задать коды, т.е. 0,1,2,3, но таким образом вы получите более точные области плоскости. Итого, с учетом первых квадратиков вы закодируете 16 областей четырьмя битами.
Ну и продолжайте дробить полученное) Как показывает практика — что бы указать точку на карте областью где-то в районе 20-30 см, точно не помню — нужно где-то 17 четверичных цыфер, а это 17*2=34 бита всего лишь.
Ваша задача совсем простая, если вам точность не нужна, то любая координата глобуса задается 32-битным числом и все)
Более того, если вы зададите вменяемую алгебру оного пространства, то все преобразования и прочие вычисления — будут астрономически быстры.
Более того — оно изумительно подходит как раз таки для картографии, потому что такое кодирование в общем и целом линейное, т.е. избавлено от коллизий. А так же такое кодирование не только кодирует двумерную плоскость, но и зум «из коробки».
По-сути вы получите чрезвычайно универсальную штуку, причем кодирующую абсолютно просто даже не двумерное, а двумерное зуммируемое пространство.
Более того, оная система чрезвычайно отлично подходит для дальнейшего расширения геоданных. Если вы кодируете плоскость, то это вовсе не значит что вы не будете кодировать высоты этой плоскости. Так вот от кодирования квадрантами легко перейти к кодированию октантами. Крайне легко будет перейти к трехмерному пространству на основе того что у вас было двумерным, но с добавлением высот. При этом это октантное пространство будет так же тривиально зуммироваться опять же «из коробки».
Ну и так же кодирование квадрантами позволяет задавать любую точность. Хотите точнее — бейте квадратики на более мелкие — получите точнее чем было. При этом, само кодирование настолько удобно «спроектировано», что и это реализуется опять же тривиальным образом.
Извините, но то что вы придумали — не очень… Есть более удобные, а главное — гораздо универсальные штуки.
Единственное с чем пожалуй соглашусь, что вы упомянули вскользь — юзерам не нужны карты. Им нужны схемы) Но при этом, вы почему-то на этом не заострили внимание.
Совершенно верно тут то, что вы и написали — не нужен юзерам собор блаженного именно картографический. На схеме он должен быть больше, чем есть на самом деле) А этим делом занимается уже не совсем картография, а конформная геометрия) Это когда у вас углы и формы сохраняются, но метрики как таковой — нет. И это очень интересная штука смею заметить. Поройте в этом направлении.rybvv Автор
21.04.2019 11:44Да я уже глянул как услышал. :)
Я вначале и сам собирался использовать степень двойки, но она неудобна: двоичный код надо как-то передавать, а тут один символ в формате base64 — и нет проблем! Те самые 64 области шестью битами. И разница в масштабах комплекта карт именно в 8 раз представляется мне весьма разумной. И задача ещё проще: кодируется ЛЮБАЯ точность — хоть до микрона, хоть меньше просто увеличением длины идентификатора точки. Сказка! :) И алгебра фактически та же самая! Я потому и разбил шар на 56 граней, чтобы дальше работать с плоскостями! А вот насчёт растрового формата рельефа я сильно сомневаюсь — векторный не в пример компактнее и удобнее. Впрочем, в OSM нет ни того, ни другого. :)
Ха! Насчёт «юзерам нужны схемы» — это не просто отдельная заметка — это целый цикл заметок должен быть! А компактно задача формулируется так: вытащить из БД всю информацию, которая там вообще есть, структурировать, верифицировать, оптимизировать и дать юзерам не просто конфетку, а целую коробку!
Не, не, не — у меня другое направление — рыть хватит до конца жизни! Называется — «многомерный граф». И это очень интересная штука смею заметить. :)
Siddthartha
20.04.2019 17:47вполне неплохая идея.
конвертацию из/в wgs84 только все равно придется хорошую реализовывать. а как свою внутреннюю систему координат, заточенную под легкое хранение и быструю работу (пожертвовав точностью) — вполне.
Rulexec
21.04.2019 12:24Посмотрите на Military Grid Reference System.
Это способ записи UTM-координат, который так же делит Землю на прямоугольники:
Заголовок спойлера
rybvv Автор
21.04.2019 12:57Похоже, но за уши притянутая десятичная система счисления. У меня лучше! :)
MooNDeaR
Возможно, здесь написано нечто интересное, но стиль изложения таков, что я ничего не понял. Какой-то поток мыслей и "очевидных" выводов.
rybvv Автор
Ну, здесь уж я бессилен — как умею… я старался, по крайней мере. :)
Xalium
для начала неплохо бы кратко объяснить почему
чтобы не продираться сквозь дебри для ответа на этот вопрос/утверждение
rybvv Автор
Да вот не знаю я, как объяснить кратко. Формат вырисовался постепенно, и сейчас мне представляется оптимальным для записи «географии». Как-то по пунктам я постарался описать его преимущества здесь в комментарии, чуть ниже.
perevedko
по-моему, статье явно не хватает иллюстраций для наглядности
rybvv Автор
Возможно, но рисовать не умею с детства. Мой старший сын уже в 2-3 года рисовал на порядок лучше, чем я.