Построение графа дорог по данным о треках транспортных средств (задача с данными)

Материал из MachineLearning.

Версия от 08:32, 16 октября 2010; Vokov (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

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

Задача и исходные данные предоставлены компанией Яндекс.

Описание задачи

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

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

Исходные данные

В качестве исходных данных вам дается огромное количество точек на земном шаре (GPS сигналов), полученные от пользователей. Предполагается, что большинство объектов, передающих точки находились на дорогах. Однако стоит учитывать, что это не всегда так, кроме этого, ошибка при определении положения может быть большой, и точки могут оказаться достаточно далеко от дороги.

Кроме самого положения для каждой точки дополнительно дан азимут — направление, в котором машина двигалась. Погрешность этих данных также достаточно велика, что стоит иметь в виду. Азимут — это угол, отсчитанный по ходу движения часовой стрелки между направлениями на север и на ориентир.

Формат входных данных

Вам задан единственный файл, в каждой строке которого написано ровно по три действительных числа: долгота, широта и азимут. (осторожно! возможны линуксовые переводы строк) Все три числа заданы в градусах.

Доступные файлы:

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

Формат выходных данных

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

Долготу и широту выводите с максимальной точностью: имейте в виду, что в одном градусе порядка 100 километров.

Критерией качества

Для оценки качества построеной карты предлагается сравнивать её с эталонной картой дорог (абсолютная точность которой также не гарантируется) по следующему алгоритму:

  1. Каждый отрезок дорог обеих карт разбивается на куски не более 10 метров (каждый кусок будет делиться пополам, пока не станет меньше 10 метров).
  2. Центры каждого из получившихся отрезков выбираются как опорные точки. После этого находится паросочетание (соответствие между опорными точками эталонного и проверяемого графа). Суммарное расстояние между парами вершин, а также «штраф» 500 метров за вершины, которым не нашлось пары — это расстояние между графами. Подразумевается, что точки на расстоянии больше 500 метров не могут образовывать пару.
  3. Паросочетание находится жадным алгоритмом — на каждом шаге в пару объединяются две ближайшие точки.

Лучшее решение — то, у которого расстояние между графами наименьшее.

В прилагаемом архиве (40 Kб) находится программа metric.cpp, которая вычисляет соответствующее расстояние. Программа компилируется компиляторами GNU C++ (g++ 4.2.4) и Visual Studio 10. В качестве параметров командной строки ей необходимо передать файл с тестируемым и эталонным графом. В исходном коде можно найти функцию вычисления расстояния на земле. Ею можно пользоваться в своем коде (можно ее немного упростить, если предполагать, что земля круглая. Это предположение вполне уместно в наших широтах). В этом же архиве находится файл toyml.py — вспомогательный скрипт для генерации YML по готовому ответу.

Средства, которыми полезно пользоваться

Возможно, получив результат, вы захотите как-то его визуализировать. Это можно сделать следующим образом:

  1. Сгенерировать YML, который вы хотите отобразить. Хороший, годный пример есть тут: linestring.xml. Более подробная документация по возможностям есть тут: ymapsml.
  2. Следущим шагом нужно выложить xml в любое публичное место так, чтобы к нему был доступ по http. Один из способов это сделать — создать сайт на narod.yandex.ru, зайти в меню управление файлами и загрузить туда xml (не более 10 мегабайт). После этого вы сможете получить прямую ссылку.
  3. Открыть maps.yandex.ru] и ввести в строку поиска полную ссылку к выложенному xml файлу.

Например как сделано тут: CNrorsC.

Пример данных Строгино можно увидеть тут: CNvpZbs

См. также

Личные инструменты