Сначала немного общих соображений: в базе 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 и т.д.), которые являются фактически мусором для конечного пользователя, но могут оказаться полезными для структуризации (выявления и исправления ошибок в данных).
Итак, пристегнулись ремнями, пронумеровали кости… ныряем! Но только не в этой заметке.
Комментариев нет:
Отправить комментарий