MisterJohn
Времени осталось ровно на написание текста работы и для подготовки к защите (составление презентации и др.)
Если сейчас начать что-то рисовать, применять и т. п., то в лучшем случае к концу мая будет что-то еле-еле работающее, а если быть более реалистичным — ещё неработающее. При этом не будет ни текста работы, ни презентации к защите. То есть, фактически, ничего.
Поэтому вариантов может быть только 2: брать что-то готовое, изучать, чуть менять, писать текст работы и делать презентацию, компенсируя недостатки работы качественной презентацией и красноречием на защите. Или отложить защиту до следующего июня.
На мой дилетантский взгляд такие замечания:
Если вы будете делать некое веб-приложение, то у вас буду две карты - визуальная, которую пользователь видит, на которой тыкает начальные/конечные пункты и внутренняя для прокладки маршрутов. Источник первой принципиально не важен, это может как гугл так и яндекс и ОСМ тут по вашей теме не надо придумывать велосипедов и достаточно воспользоваться API (Яндека, гугла, лифлет, опенлейерс). А вот для внутренней карты надо составлять какой-то граф и по нему строить маршрут. Для чего в случае достаточно полного графа есть по идее готовые алгоритмы. И это относительно просто в случае “ткнуть мышкой две точки и построить между ними маршрут”. В случае, запрос пользователя “мне надо добраться от улицы Ленина,5 до улицы Советской, 13” то тут надо реализовывать какое-нибудь геокодирование. А это должна быть более-менее полная база адресов объектов с их координатами.
Итак нужна база содержащая все улицы, привязааные к ним маршруты ОТ, места остановок. Нужна адресная база для геокодирования. Если в ОСМ этих данных нет, значит их нужно собрать и внести.
О, ещё придумал вариант для бедных - пользователь задает только начальную и конечную остановку ОТ. Тут будет достаточно перечисления остановок на каждом маршруте и время перегонов
Не только есть, всё уже давно написано и используется. Геокодирование есть в проекте openstreetmap.ru, исходники OSRM так же на гитхабе. Если бы были по расторопней, то работа не бей лежачего.
Если хотите все готовое, то я бы предложил чуть другую тему - “Построение оптимального автомобильного маршрута между Москвой и Лиссабоном, на основе cлабоминерализированного дорожного графа”. В качестве научных руководителей - freeExec и OverQuantum. Они в этом вопросе большие доки.
Я слабо понимаю в технических аспектах. Но почему бы вам например не написать вебсайт, на котором был бы выбор А в Б, а скрипт просто бы парсил результат с того же OSRM? И в теоретической части описание алгоритмов OSRM. Или типа того.
Вы так же заглядывали в OSM файл? Загрузите, сохраните и будет вам квартал :). Писать рендер смысла нет, есть мапник.
Тут по большому писать своё вообще смысла нет. Вообще в дипломе должна быть своя изюминка - новая шестеренка повышающая точность, скорость, ещё что-то. Тут же изюменкой может быть какой-то новый коэффициент влияющий на вес ребра - таже поверхность дороги например. Но чтобы воткнуть её на нужное место и потом это спомпой преподнести существующий алгоритм надо разобрать по косточкам. Написать диплом вообщем-то реально, но не с таким патходом как:
Обратите внимание на слово “реализованы” в третьем ответе. Подсказка: на него нужно нажать левой кнопкой мыши. Затем тщательно изучить открывшийся раздел вики и по ссылкам просмотреть другие материалы.
Я уже ознакомился с интерфейсом карт эдитора, узнал возможности, приблизительно понял что да как.
О изюминке! Самая клевая функция будет- получение пути по смс. Тоесть если человек не имеющие GPS Навигатора может просто зайти на сервис - подать запрос и получить в виде смс координаты как добраться с точки А до точки Б( к примеру если я хочу добраться на автобусе, будут номера ближайших автобусов или маршруток ). Но к этому в последнюю очередь. Сейчас главная задача использовать по максимум готовые исходники OSM.
freeExec, напишите свои контакты пожалуйста, вижу Вы в этом деле профи.
Если же ближе к возможным решениям задачи силами одного студента “раздолбайского характера” - то, имхо, единственный вариант для вас это взять какой-нить ооооооочень маленький город (почему маленький - ниже), построить для него навигационный граф (т.е. грубо говоря взять только все дороги) и реализовать навигацию по этому графу банальным Дейкстрой. Алгоритм Дейкстры предельно прост для понимания:
Ищете ближайшие рёбра навигационного графа к точкам старта и финиша. Это будут соответственно рёбра старта и финиша.
Создаёте список возможных маршрутов, кладёте туда пока только два маршрута, коими будут точки-концы ребра старта.
Для каждого маршрута в списке смотрите, какие рёбра (кроме предыдущего пройденного) исходят из последней точки. Если рёбер больше одного - то клонируете текущий маршрут для каждого с дописыванием этого ребра, т.е. на каждой точке “разветвления” у вас будут расходиться разные маршруты. Все эти склонированные маршруты запихиваем в общий список маршрутов.
Повторяем шаг 3, пока либо не кончатся варианты, либо нам не попадётся ребро финиша.
Т.е. грубо говоря наш поиск “волной” расходится по дереву возможных вариантов, плодясь на каждом узле. Сей алгоритм крайне прожорлив с точки зрения памяти, поэтому работать будет лишь на небольших графах - поэтому берите маленький город. Несколько сэкономить память можно, проверяя не пошёл ли каждый маршрут по кольцу, т.к. в подграфах могут быть кольца.
Как только это заработает - научите ещё учитывать длины рёбер, тогда маршрут станет оптимизирован не по количеству перекрёстков, а по расстоянию.
А просто поднять pgRouting и чего-нибудь посчитать - не покатит?
Можно например рассчитать для каждого жилого дома города расстояние, сколько идти пешком до метро/парка/кладбища/школы/почты по пешеходному графу.
