Приложение для "Бегущего города" (проект) — различия между версиями

Версия 12:35, 7 апреля 2016

Что это за проект?

Одним из наиболее популярных соревнований по городскому ориентированию является "Бегущий город" ((http://runcity.org)). Проходят они в общих чертах так: есть несколько этапов, в начале этапа выдаётся список адресов КП (задание загадками в рамках проекта не рассматриваем), которые надо посетить на этом этапе, и адрес финиша этапа, на котором даётся задание на следующий этап. На каждом КП надо рассмотреть что-то на местности и записать увиденное. КП можно посетить в любом порядке, и первая задача участника — найти КП на карте и определить, в каком порядке их проходить. Хочется сделать приложение, по возможности автоматизирующее эту задачу.

Выбор платформы

Чтобы быть полезным, это приложение должно работать на каком-то устройстве, которое участник носит с собой, то есть разумной платформой будут Android, iOS или Windows 10. Мой выбор — Windows 10, но можно на свой страх и риск работать с какой-то другой платформой.

Распознавание задания

Итак, на вход это приложение получает фото листа с заданием (+2 балла, если научите его работать прямо с камерой устройства). Для начала надо распознать текст на этом изображении, выделить из него адреса КП и сохранить их список в каком-нибудь распространённом формате данных — я предлагаю json. Для распознавания под Windows 10 есть встроенная библиотека, под другими платформами можно попробовать Tesseract или какой-нибудь веб-сервис на его основе, скажем, http://ocrwebservice.com, http://ocr.a9t9.com или http://onlineocr.net. Эксперименты с Tesseract'ом показали, что он не иправляет перекос на фотографиях, я завёл страницу о том, как делать это самому. Выделять адреса из текста можно либо ещё на картинке по размеру шрифта в строках, либо по всяким словам-маркерам типа "ул." ((https://en.wikipedia.org/wiki/Named-entity_recognition Named entity recognition)). Фото нескольких заданий выложены в папку на Яндекс.Диске: https://yadi.sk/d/wN6Y39wRoHGrD

Формат промежуточного результата

Итак, это json (примеры в википедии). Изображение

должно переходить в такой json (см. http://www.runcity.org/ru/events/2015/routes/rider-middle/#stage2):

{
 "city":"Санкт-Петербург",
 "leg":"2",
 "category":"Всадник-Мидл",
 "start": "Заневский пр., д. 30",
 "finish": "Кирочная ул., д. 8",
 "points": ["Дом на углу Потемкинской и Захарьевской ул.", "Малоохтинский парк, угол Новочеркасского пр. и Республиканской ул.",
 "ул. Маяковского, д. 8", "Манежный пер., д. 15-17", "ул. Радищева, д. 42", "Угол Шпалерной и Таврической ул."]
}

"leg" также может иметь значение "bonus". "start" — это "finish" прошлого этапа (или точка, в которой человек сфотографировал задание этого этапа). Возможно, про points следует сохранять больше информации, но пока ограничимся этим.

Отображение на карте

После того как список адресов получен, нужно отобразить его как точки на картах. Можете выбрать карты на свой вкус, скажем, одни из https://maps.yandex.ru, https://maps.me, https://maps.google.com, https://maps.here.com, https://www.openstreetmap.org, почитав документацию на их API (+1 балл за поддержку 3 карт из списка). После этого хорошо дать пользователю возможность поправить эти точки, скажем, передвинуть точку к конкретному подъезду дома, но в минимальном варианте можно обойтись без этого. Затем нужно через API маршрутизации померить расстояния между этими точками по допустимым маршрутам. В "Бегущем городе" есть разные категории, скажем, пешая, велосипедная, автомобильная, общественный транспорт. Если API выбранных вами карт поддерживает разные способы маршрутизации, то имеет смысл предоставить пользователю выбор.

Маршрутизация

Получив расстояния, следует построить кратчайший маршрут от начала до конца этапа, проходящий через все КП. Это вычислительно сложная задача (задача коммивояжёра), для которой, как я понимаю, нет методов сильно лучше полного перебора, но на этапе около 10 КП, так что перебор должен быть осуществим.

Дополнительные функции

Бонус: в "Бегущем городе" также есть бонусные КП, список которых выдаётся на старте. В качестве бонуса можно научиться рисовать на карте также и их, а также учитывать их в построении маршрутов. Здесь нужно будет принимать решение, стоит ли посещать бонусный КП на данном этапе или лучше отложить его до одного из следующих, так как он очень далеко от всех КП данного этапа. Видимо, решение стоит принимать на основании какого-нибудь несложного классификатора из машинного обучения, используя в качестве факторов расстояния между КП этапа, а также между КП этапа и бонусным КП.

Да, и "Бегущий город - Москва" 16 апреля, хорошо бы, чтобы к этому моменту уже что-то работало.

Чему вы научитесь?

Вы научитесь работать с API веб-сервисов и слегка ознакомитесь со структурой веб-страницы и, видимо, с языком Javascript, потому что без него с API карт никак. А также научитесь собирать умные приложения из готовых блоков. И немножко поделаем пользовательские интерфейсы. Ну, и ещё работа с репозиторием и ревью кода, это само собой.

Какие начальные требования?

Готовность читать англоязычную документацию и подбирать инструменты под задачу.

Какие будут использоваться технологии?

API карт, какие-либо библиотеки или сервисы OCR, машинное обучение.

Темы вводных занятий

По согласованию со студентами.

Направления развития

Довольно много рюшечек уже описано выше и ниже. Ещё можно попытаться сделать маршрутизацию на общественном транспорте с учётом его расписания (т.е. 10 минут на КП и беги на электричку). Ещё хорошо научиться рисовать точки на закешированных картах в отсутствие интернета (под Windows 10 встроенное приложение работает с here maps, например), в том числе посмотреть на возможности 2gis.

Критерии оценки

4-5 баллов: либо этап от фото до json'а, либо этап от json'а до маршрута.

6 баллов: от фото до json'а + нанести точки на карту как они есть; либо от json'а до маршрута + выбор типа маршрутизации + возможность поправить точки перед маршрутизацией.

8 баллов: оба этапа из категории "4-5 баллов".

+2 балла: на входе работать с камерой, а не с готовым фото.

+1 балл: выбор типа маршрутизации

+1 балл: возможность поправить точки (в браузере) перед маршрутизацией.

+1 балл: автоматическое определение типа маршрутизации по тексту задания (категории "Бегущего города").

+1 балл: поддержать 3 сервиса карт из списка.

+1 балл: отображать бонусные КП на карте.

+2 балла: учитывать бонусные КП при маршрутизации.

Расписание занятий

По итогам первой встречи решено перенести занятия в офис "Яндекса". Занятия будут проходить в среду в 16:00 в бизнес-центре "Мамонтов" (ул. Тимура Фрунзе, д. 11 к.2, в районе метро "Парк Культуры"). Примерный маршрут от метро: https://maps.yandex.ru/-/CVD2N47u (там также отмечено, с какой именно стороны входить в здание). С улицы Тимура Фрунзе надо сворачивать во двор по стрелке "Яндекс. Теперь налево". В конце следует подняться на крыльцо под вывеской "Мамонтов" и ждать перед турникетами.