Пожалуйста, ознакомьтесь со списком призов, правилами оформления результатов и прочими условиями конкурса.

С момента первоначальной публикации были внесены следующие изменения:

  1. Уточнен набор опций для запуска утилиты "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