Математическое ориентирование
Летом мы сбегали один рогейн, недавно на зимнию версию того же ходили друзья (бегали по одному району и даже сделали почти одинаковые фотки, см. отчет. Мне стало интересно, как же правильно прокладывать маршрут (теоретически готовиться всегда проще, чем начать бегать по утрам).
Сегодня я хочу предложить всем интересующимся результат: программу для прокладывания маршрута. Подойдет, кстати, не только для спортивного ориентирования. Она анализирует доступные точки и пытается их соединить выгоднейшим образом (это вариант задачи коммивояжёра, только обойти надо не все пункты).
Программа, исходники плюс две карты с точками: rogaine-0.2.zip.
Получилось "улучшить" выбранные нами маршруты примерно на 10% (найти вариант на 10% дороже с не большей длиной дистанции по прямой).
Варианты развития проекта - добавить распознавание пунктов с карты (привет, машграф), улучшить алгоритм, перенести на айфон наконец :)
Правила рогейна, кстати, запрещают пользоваться компьютером для планирования дистанции (но для анализа - почему бы и нет). Скоро и мобильником запретят.
Тут можно обсудить ориентирование, алгоритмы поиска пути, проблемы в работе программы, статическую линковку qt-приложения.
Сегодня я хочу предложить всем интересующимся результат: программу для прокладывания маршрута. Подойдет, кстати, не только для спортивного ориентирования. Она анализирует доступные точки и пытается их соединить выгоднейшим образом (это вариант задачи коммивояжёра, только обойти надо не все пункты).
Программа, исходники плюс две карты с точками: rogaine-0.2.zip.
Получилось "улучшить" выбранные нами маршруты примерно на 10% (найти вариант на 10% дороже с не большей длиной дистанции по прямой).
Варианты развития проекта - добавить распознавание пунктов с карты (привет, машграф), улучшить алгоритм, перенести на айфон наконец :)
Правила рогейна, кстати, запрещают пользоваться компьютером для планирования дистанции (но для анализа - почему бы и нет). Скоро и мобильником запретят.
Тут можно обсудить ориентирование, алгоритмы поиска пути, проблемы в работе программы, статическую линковку qt-приложения.