С момента первоначальной публикации были внесены следующие изменения:
- Уточнен набор опций для запуска утилиты "osmosis"
Задача 1: усечение карты
Код задачи: geo.
Краткое описание: необходимо написать утилиту, которая будет извлекать из указанной карты в формате OpenStreetMap только элементы, находящиеся внутри заданного полигона обрезки.
Развернутое описание: утилита принимает три аргумента командной строки: имя xml-файла с векторной картой в формате OSM, имя файла с координатами вершин полигона обрезки и имя выходного файла в формате OSM.
Базовым элементом карты является узел (node) — это точка с указанными координатами. Узлы входят в состав путей (ways). Кроме того, в состав карты могут входить группирующие объекты, называемые отношениями (relations). В состав отношения могу входить любые другие объекты карты: пути, узлы, другие отношения. В том числе, отношения могут быть пустыми. Более подробное описание типов данных можно найти на wiki проекта OpenStreetMap.
Полигон обрезки состоит из нескольких произвольных (не обязательно выпуклых) многоугольников, которые, в частности, могут содержать «дырки» произвольной формы и иметь самопересечения.
Необходимо извлечь из указанной карты и сохранить в выходной файл только те элементы карты, которые лежат внутри полигона обрезки.
Для обработки объектов, которые попали внутрь полигона обрезки частично, необходимо предусмотреть в программе опцию с семантикой «включать частично обрезанный объект в результат целиком», далее называемую completeObjects.
Если эта опция отключена, то все узлы, не попавшие в полигон обрезки, удаляются из всех путей и отношений, которые на них ссылаются. Пустые пути и отношения тоже удаляются.
Если эта опция включена, то обработка путей и отношений происходит по следующим правилам: если внутрь полигона обрезки попал хотя бы один узел пути, весь путь целиком (все входящие в него узлы) должен быть включен в результат. Также в результат должны попасть все отношения, в которые входят какие-либо узлы, пути и отношения, попавшие в результат (рекурсивно). Однако пути, узлы и отношения, являющиеся членами каких-либо отношений, попавших в результат, но при этом лежащие целиком за пределами полигона обрезки, в результат не попадают.
Рис. 1: Пример фильтрации с опцией completeObjects
Карта имеет вид XML-документа, все теги второго уровня в котором — это либо узел, либо путь, либо отношение. В теги узлов, путей и отношений могут быть заключены другие теги, которые должны быть перенесены в выходной файл без изменений.
Уровень 1: программа может выполнить обрезку по произвольному выпуклому многоугольнику, без реализации опции completeObjects. Пример восьмиугольного полигона, ограничивающего город Киев, находится в файле octagon.poly.
Уровень 2: программа может выполнить обрезку по произвольному многоугольнику, который может быть невыпуклым, состоять из нескольких частей и содержать «дыры», без реализации опции completeObjects. Пример прямоугольника, ограничивающего город Киев, и имеющего прямоугольную дыру в центре находится в файле hollow_rectangle.poly.
Уровень 3: программа может выполнить обрезку по произвольному многоугольнику, который может быть невыпуклым, состоять из нескольких частей и содержать «дыры», с поддержкой опции completeObjects.
Уровень 4: программа способна за вменяемое время вырезать фрагмент по контуру произвольной административно-территориальной единицы из полной карты России с включенной опцией completeObjects. Приблизительное определение понятия «вменяемое время» таково: «порядка получаса для извлечения Московской области».
Карты всех стран мира в формате OSM можно найти на сайте CloudMade. Файлы с картами имеют суффикс .osm.bz2, там же находятся и полигоны обрезки, использованные для извлечения этих карт из карты мира (файлы с суффиксом .poly).
Для проверки своей программы можете сравнивать ее вывод с результатом работы утилиты Osmosis на небольших картах и полигонах обрезки. Чтобы Osmosis генерировал результаты, соответствующие опции completeObjects, необходимо запускать его так (команда разделена на несколько строк для лучшей читаемости):
osmosis --read-xml file=russian_federation.osm
--bounding-polygon file=mosobl.poly
completeWays=true
completeRelations=true
idTrackerType=BitSet
--write-xml file=moscow.osm