| stankhat | 06.02.2015 17:12 |
Google Maps - ищется алгоритм обхода ремонтных участков дорог
Задача: необходимо проложить маршрут, который обходит участки с ремонтом дорог.
С помощью полилиний на карту наносятся участки с ремонтом дорог. Вот так:
Прокладываем путь (синяя линия), например, Москва — Ижевск. Дальше — проверяем, пересекает ли наш путь ремонтные участки. Если пересекает, то ищем обходной путь.
Главный вопрос — как его искать. Имеются массивы точек (широта и долгота) каждого ремонтного участка (по которым строились полилинии), также имеется массив "прямого" пути, необходимо найти "обходной" путь.
Было решено делать так: у каждого пересекаемого ремонтного участка берем начало и конец, прокладываем между ними прямую, берем середину и делаем перпендикуляр от этой середины. Начинаем с длины перпендикуляра = 5 км. Т.е. примерно так:
Google Maps работает по следующему принципу. Если передать 3 точки: начало (Москва), транзитную точку и конец (Ижевск), то Google Maps строит маршрут проходящий через транзитную точку. Если возле транзитной точки нет близлежащей дороги, то Google Maps "возвращает" на "прямой" путь. Итак, берем шаг=5 км. — см. на рисунке точку A, делаем запрос к Google Maps и передавая 3 точки (начало, транзит, конец) и получаем массив точек "обхода". Проверяем, если возвращенный путь пересекает ремонтируемый участок, то увеличиваем в цикле длину перпендикуляра (см. рисунок) с шагом=5 км. до точки B, C, D, E и т.д. В каждой итерации делаем проверку на предмет пересечения с ремонтным участком, до тех пор пока "обходной" путь не перестанет пересекать ремонтный участок.
Проблема №1:
Крюк образуется слишком большой. В данной случае ремонтный участок 60 км., такая же ситуация если ремонтный участок 1-2 км. Неужели нет варианта объезда ближе к ремонтному участку?
Проблема №2:
Петля образуется в результате того, что при откладывании перпендикуляра Google Maps ищет ближайшую дорогу и "стремится" попасть в транзитную точку (см. картинку №2 точки A,B,C,D,E). Как убрать эту петлю?
Приветствуются любые замечания по алгоритму поиска обходного пути. Заранее благодарен.
С помощью полилиний на карту наносятся участки с ремонтом дорог. Вот так:
Прокладываем путь (синяя линия), например, Москва — Ижевск. Дальше — проверяем, пересекает ли наш путь ремонтные участки. Если пересекает, то ищем обходной путь.
Главный вопрос — как его искать. Имеются массивы точек (широта и долгота) каждого ремонтного участка (по которым строились полилинии), также имеется массив "прямого" пути, необходимо найти "обходной" путь.
Было решено делать так: у каждого пересекаемого ремонтного участка берем начало и конец, прокладываем между ними прямую, берем середину и делаем перпендикуляр от этой середины. Начинаем с длины перпендикуляра = 5 км. Т.е. примерно так:
Google Maps работает по следующему принципу. Если передать 3 точки: начало (Москва), транзитную точку и конец (Ижевск), то Google Maps строит маршрут проходящий через транзитную точку. Если возле транзитной точки нет близлежащей дороги, то Google Maps "возвращает" на "прямой" путь. Итак, берем шаг=5 км. — см. на рисунке точку A, делаем запрос к Google Maps и передавая 3 точки (начало, транзит, конец) и получаем массив точек "обхода". Проверяем, если возвращенный путь пересекает ремонтируемый участок, то увеличиваем в цикле длину перпендикуляра (см. рисунок) с шагом=5 км. до точки B, C, D, E и т.д. В каждой итерации делаем проверку на предмет пересечения с ремонтным участком, до тех пор пока "обходной" путь не перестанет пересекать ремонтный участок.
Проблема №1:
Крюк образуется слишком большой. В данной случае ремонтный участок 60 км., такая же ситуация если ремонтный участок 1-2 км. Неужели нет варианта объезда ближе к ремонтному участку?
Проблема №2:
Петля образуется в результате того, что при откладывании перпендикуляра Google Maps ищет ближайшую дорогу и "стремится" попасть в транзитную точку (см. картинку №2 точки A,B,C,D,E). Как убрать эту петлю?
Приветствуются любые замечания по алгоритму поиска обходного пути. Заранее благодарен.