Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Jigga001
1 / 1 / 0
Регистрация: 20.12.2012
Сообщений: 27
1

Google Maps - ищется алгоритм обхода ремонтных участков дорог

06.02.2015, 17:18. Просмотров 386. Ответов 1
Метки нет (Все метки)

Необходимо проложить маршрут, который обходит участки с ремонтом дорог.

С помощью полилиний на карту наносятся участки с ремонтом дорог. Вот так:

http://files.rsdn.ru/90586/map.jpg

Прокладываем путь (синяя линия), например, Москва — Ижевск. Дальше — проверяем, пересекает ли наш путь ремонтные участки. Если пересекает, то ищем обходной путь.

Главный вопрос — как его искать. Имеются массивы точек (широта и долгота) каждого ремонтного участка (по которым строились полилинии), также имеется массив "прямого" пути, необходимо найти "обходной" путь.

Было решено делать так: у каждого пересекаемого ремонтного участка берем начало и конец, прокладываем между ними прямую, берем середину и делаем перпендикуляр от этой середины. Начинаем с длины перпендикуляра = 5 км. Т.е. примерно так:

http://files.rsdn.ru/90586/map1.jpg

Google Maps работает по следующему принципу. Если передать 3 точки: начало (Москва), транзитную точку и конец (Ижевск), то Google Maps строит маршрут проходящий через транзитную точку. Если возле транзитной точки нет близлежащей дороги, то Google Maps "возвращает" на "прямой" путь. Итак, берем шаг=5 км. — см. на рисунке точку A, делаем запрос к Google Maps и передавая 3 точки (начало, транзит, конец) и получаем массив точек "обхода". Проверяем, если возвращенный путь пересекает ремонтируемый участок, то увеличиваем в цикле длину перпендикуляра (см. рисунок) с шагом=5 км. до точки B, C, D, E и т.д. В каждой итерации делаем проверку на предмет пересечения с ремонтным участком, до тех пор пока "обходной" путь не перестанет пересекать ремонтный участок.

Проблема №1:

http://files.rsdn.ru/90586/map2.jpg

Крюк образуется слишком большой. В данной случае ремонтный участок 60 км., такая же ситуация если ремонтный участок 1-2 км. Неужели нет варианта объезда ближе к ремонтному участку?

Проблема №2:

http://files.rsdn.ru/90586/map3.jpg

Петля образуется в результате того, что при откладывании перпендикуляра Google Maps ищет ближайшую дорогу и "стремится" попасть в транзитную точку (см. картинку №2 точки A,B,C,D,E). Как убрать эту петлю?

Приветствуются любые замечания по алгоритму поиска обходного пути. Заранее благодарен.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2015, 17:18
Ответы с готовыми решениями:

Вывести списки участков по каждой из дорог, у которых протяженность более 2 и менее 3 км
Даны массивы дорога №1 H1, …, H20 – шифры участков; L1, …, L20 – протяженности...

Как подключить географические карты типа Google Maps или Open street maps в своё приложение
Всем доброго времени суток. Вопрос такой: как подключить географические карты типа Google Maps или...

Google сделала браузерную версию Google Maps трехмерной
Интернет-гигант Google вчера представил обновление для сервиса Google Maps. Компания показала новую...

Google Maps 2. Ограничение на количество запросов к google
Google накладывает ограничение на количество запросов в день к Google Maps (2500 в день на ключ)....

google maps
Как прикрепить Google maps к сайту на Joomla 1.5? Зарание спасибо!

1
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 955
10.02.2015, 13:52 2
#1
Например,вместе с удлинением перпендикуляра в качестве начала и конца брать более дальние от участка с ремонтом узловые точки. Т.е. будет не одна, а 3 транзитные точки. Надеюсь вы учитываете что тут два перпендикуляра?
#2
А в таком случае узловые точки будут совпадать, или они разные? Вот не могу точно вспомнить название класса задач на удаление точек кривой чтобы найти готовые решения.
Можно сделать так - для каждого узла в некотором радиусе проверять чтобы расстояние между узлами перед ним и за ним было больше чем расстояние между текущим узлом и каждым из выбранных (и не менее некоторого числа - тут возможно что мы можем потерять значимые близлежащие узлы).
Или разделить полученный маршрут на части и проверять что новый маршрут между краями каждой части примерно равен длине такой части в исходном маршруте. Это можно проделывать несколько раз с уменьшением длинны частей, но в двух "соседних" итерациях в качестве границ частей не брать узел который уже был использован в предыдущей итерации.
Впрочем это тоже не идеальный подход.

А разве с гугла нельзя утащить граф дорог? Для реалтайма в России можно попробовать Яндекс-Пробки (передаются отрезки дорог, а не картинки). И еще есть OpenStreetMap. А если есть граф дорог, то дальше проще.
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.02.2015, 13:52

Google maps
что нужно удалить вкоде google maps,чтобы не отображалось выделенное на скрине ?

Google maps
Уважаемые, подскажите что не так. Пытаюсь подключить карту. mapFragment = (SupportMapFragment)...

Google maps
Здравствуйте! Недавно начал разработку приложения с использованием google maps и при первом же...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.