Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Поиск маршрутов за 1 человеко-месяц

Anna | 24.06.2014 | нет комментариев
Однажды для нашего плана понадобился функционал прокладки маршрутов. Программистов у нас не то Дабы дюже много, а скорее напротив, следственно мы хотели обнаружить какое-то готовое решение, поискали и ничего отменного не обнаружили.

Данные дорожного графа у нас были, но в таком виде, что ни в одну библиотеку либо какой-то middle-ware их так легко не подать. Да и middle-ware по навигации, Добросовестно говоря, мы не обнаружили, так Дабы легко встраивалось в нашу систему (спасибо, если кто подскажет куда посмотреть). Следственно приняли решение сделать независимо, применяя по максимуму существующие библиотеки для каждого.

О процессе разработки обслуживания и расскажу.

О графе.

Несколько слов о данных. Данные мы получаем от стороннего подрядчика, на формат и состав данных влиять не можем. Данные о дорогах имеют вид файла в формате ArcView (Shapefile). Все улицы разбиты на секции от перекрестка до перекрестка, всякому сегменту сопоставлены признаки:
— неповторимый идентификатор сегмента
— геометрическая ломаная, изображающая секция дороги
— данные о разрешенной максимальной скорости по ПДД
— данные о вероятности разворота в начале и конце сегмента
— знак одностороннего движения на сегменте
— Z ярус начала и конца сегмента (скажем въезд на эстакаду имеет в начале ярус 0, а в конце ярус 1)

Помимо того есть обособленный файл с ограничениями движения, накладываемыми логикой и/или ПДД. Всякое лимитация — это вектор идентификаторов, ссылающихся на секции улицы (из первого файла), последовательное движение по которым запрещено.

Пример того, как все это выглядит, висит в заголовке поста (красным — запреты, к сожалению, наш софт в данном случае не разрешает нарисовать запреты с направлением).

Для работы алгорифмов на графе, требуется, Дабы граф был представлен в каком-то общепризнанном виде, скажем в виде списка связанности вершин, либо матрицы связанности. То есть реально требуются данные о вершинах и связях между ними. От того что в наших данных данные о вершинах дюже неполные, есть только данные об их геометрическом местоположении, пришлось провести обработку, Дабы все вершины получили уникальные идентификаторы.

За основу мы взяли геометрическое местоположение вершин, но было одно обстоятельство: координаты финальных вершин секций не неизменно совпадали на 100%, скажем на перекрестках (допустимо недостатки работы операторов ГИС системы, верно не знаю). Следственно мы приняли решение считать одной вершиной графа все финальные точки секций, имеющие идентичный Z-ярус и отстоящие друг от друга не дальше чем на 1 метр.

Каждого секций уличной дорожной сети в наших данных приблизительно 140 000, а значит финальных точек приблизительно 280 000. Соответственно необходим был какой-то нелобовой алгорифм нахождения всех соседей на расстоянии до 1 метра всякой точки. Лобовой перебор всех пар имеет квадратичную трудность и работает Безмерно длинно. От того что мы решили, что наша программка будет трудиться напрямую с начальным представлением данных, то есть с Shape-файлами (поводы: легко обновлять, не необходимо поддерживать, документировать, версионировать личный формат хранения), то необходим был результативный алгорифм идентификации вершин.

Придумали вот что (тут и дальше код на С ):
1. Сделали контейнер для ребер графа:

typedef size_t EdgeID;
typedef size_t VertexID;
struct EdgeDesc
{
    VertexID vtxSrc, vtxDest;
    EdgeInfo info;
};

typedef std::unordered_multimap<EdgeID, EdgeDesc> EdgeMap;

Мультимэп, потому что мы решили не вводить новые идентификаторы сегментов/ребер графа, а информацию о прямом и обратном ребре сберегать соответственно с идентичными идентификаторами. Возможно это было не самое верное решение, потому что на мой взор усложнило логику некоторых процедур, но в начале казалось, что так будет типично.


Рис 1.

2. Координатную плоскость разбили на квадратики метр на метр (рис 1).
Всякой вершине сопоставили ключ:

static_assert(sizeof(size_t) >= 8, "size_t type should be 64 bit or larger");

auto keyPartX = [this](double x)
{ return (size_t)(x - bound_.first.x)   1; };
auto keyPartY = [this](double y)
{ return (size_t)(y - bound_.first.y)   1; };
auto getKey = [](size_t x, size_t y)
{ return x << (sizeof(size_t) / 2 * 8) | y; };
auto getKeyXY = [&keyPartX, &keyPartY, &getKey](double x, double y)
{ return getKey(keyPartX(x), keyPartY(y)); };

3. Сделали хэш-контейнер

typedef size_t CellKey;
typedef std::unordered_map<CellKey, std::vector<VertexID>> SPHash;

При просмотре списка секций уличной сети, мы строим список элементов, содержащих идентификаторы исходной и финальной вершин, идентификатор ребра, и сопутствующую информацию, то есть реально граф в виде списка смежных вершин.

Исходную и финальную точку сегмента мы пробуем добавить в SPHash по вычисленному в п. 2 ключу. Если с таким ключом в контейнере теснее есть точки, то новую точку не добавляем, а возвращаем идентификатор теснее имеющейся (при условии что имеющаяся точка в контейнере на том же Z ярусе что и добавляемая).
Если по ключу в контейнере ничего нет, то вносим точку в контейнер и возвращаем идентификатор добавленной точки.

Правда точки, расстояние между которыми поменьше 1 метра, могут иметь различные ключи, следственно мы проверяем контейнер не только по вычисленному ключу, но и по 8-ми соседним:

std::vector<size_t> near;

size_t xPart = keyPartX(p.x);
size_t yPart = keyPartY(p.y);

near.clear();
merge(near, getKey(xPart, yPart));
merge(near, getKey(xPart   1, yPart));
merge(near, getKey(xPart - 1, yPart));
merge(near, getKey(xPart, yPart   1));
merge(near, getKey(xPart, yPart - 1));
merge(near, getKey(xPart   1, yPart   1));
merge(near, getKey(xPart   1, yPart - 1));
merge(near, getKey(xPart - 1, yPart   1));
merge(near, getKey(xPart - 1, yPart - 1));

merge() строит список идентификаторов ближайших точек в векторе near.
Получив список идентификаторов соседей (по сути кандидатов на слияние в одну вершину), мы сопоставляем точки, вычисляя точное евклидово расстояние между ними. И если оно поменьше заданного, то считаем, что точки идентичны и объединяем в одну вершину (на рисунке покрашены в один цвет), возвращая идентификатор подходящей вершины теснее имеющейся в ячейке с ключом getKey(xPart, yPart).
При старте эта обработка занимает около 1 секунды, что нас устроило.

4. В итоге получаем, что соседние точки ближе заданного порога получают один идентификатор.
Сейчас у нас есть список смежных вершин. Временная трудность приобретения такого списка линейно зависит от числа вершин, потому что всякую мы обрабатываем ровно 1 раз, а операции поиска и вставки в хэш-контейнер имеет асимптотически константную трудность.

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

Если бы мы разбили ломаную на составляющие ее отрезки и всякий отрезок считали бы ребром, то в графе взамен приблизительно 140 000 ребер было бы теснее приблизительно 600 000. Гораздо усилилось бы время поиска пути, в конце я покажу эту разницу в безусловных значениях.

Остался конечный штрих. Ограничения, либо запрещенные маневры.
Лимитация воспрещает какой-либо маневр, скажем поворот налево на перекрестке. Начально в данных представляет собой список секций, последовательное движение по которым запрещено.

Приведу пример:

Рис. 2

Красные стрелки показывают запрещенный маневр, числа обозначают идентификаторы секций. Реально в данных данный закроет выглядит как {e1, e4}.

С таким представлением запретов трудиться в процессе прокладки маршрута дюже трудно, следственно мы решили локально трансформировать граф так, Дабы запрещенный маневр был немыслим в графе чисто топологически, при этом все прочие разрешенные маневры остались допустимыми.

Для этого мы продублировали вершины, входящие в запрещенные маневр. И через эти дублированные вершины провесили ребра так, Дабы сделать разрешенные маневры, а для запрещенного маневра такой маршрут легко не создавать.

При клонировании вершины ее геометрическое местоположение остается бывшим (показанные на рисунке вершины v6 и v5 на самом деле геометрически в одном и том же месте и разнесены на рисунке для комфорта), для новой вершины, разумеется, выдается новейший идентификатор.

Проиллюстрирую сказанное на примере перекрестка с запрещенным левым поворотом выше:

Рис 3.

Видно, что на графе с измененной топологией осуществить левый поворот по запрещенному пути на перекрестке огромнее невозможно, при этом все разрешенные маневры остались допустимыми.

Ограничения из больше чем 2-х ребер обрабатываются по тому же тезису, но порождают огромнее новых вершин и ребер, на размер графа эти трансформации влияют, но не гораздо (рост числа ребер приблизительно на 5%). В наших данных порядка 5000 ограничений из 2-х секций и около 400 из 3).

Вот иллюстрация того, как трансформируется граф под действием ограничения из 3-х ребер:
Было:

Рис 4.

Стало:

Рис 5.

Нужно сказать, что реализация алгорифма трансформации графа стала самым трудным этапом каждой работы (на нее ушло около 30% времени) и именно там было наибольшее число багов. Отчасти это связано с не самой отличной проработкой конструкции хранения данных. Так что если что-то осталось непонятным — не ужасно, это подлинно было сложно, задавайте вопросы, постараюсь ответить.

Об инструментах.

И так сейчас у нас был граф представленный в комфортном виде с учетом всех ограничений, по которому дозволено было прокладывать маршруты. В качестве алгорифма решили испробовать типичный алгорифм Дейкстры, отличная реализация которого есть в библиотеке boost.
Здесь добавить особенно нечего, по boost::graph есть отличная документация и даже книги, мы взяли код одного из примеров и с небольшими изменениями применяли его у нас.

Дальнейшим этапом стала обработка запросов. Мы решили, что комфортно, если сервис сумеет прокладывать маршрут, имея только исходную и финальную точку, заданные координатами. А значит нужно стремительно обнаружить исходную и финальную вершину в графе, которые максимально близко расположены к соответствующим точкам запроса.
Для этого необходимо было стремительно уметь находить ближайшую к заданной пользователем точку на уличной сети (пользователь может захотеть маршрут от точки находящейся вне дорожно-уличной сети).

Здесь целесообразно припомнить о том, что секции дорожно-уличной сети в наших данных это ломаные, следственно нам нужно было обнаружить ближайшую к заданной точку на ломаной (это может быть точка лежащая на ломаной, либо ее исходная либо финальная вершина).
Ломаных достаточно много (140 000), а искать нужно стремительно. Искать перебором всех секций слишком медлительно. Здесь на поддержка пришла свежая версия библиотеки boost::geometry, где возникли пространственные индексы (boost::geometry::index) теснее с помощью такого объекта как ломаная линия (linestring).

С применением этого индекса мы стремительно находим несколько ближайших кандидатов, из них после этого точным алгорифмом определяется секция, особенно близко проходящий вблизи заданной точки.

Для чтения SHP файлов мы применяли библиотеку GDAL, для реформирования между географическими системами координат (мы трудимся в локальной системе города, так исторически сложилось), а пользователю комфортнее применять GPS (WGS84) координаты) взяли библиотеку proj4, а для задач реформирования кодировки текста iconv.

О деталях.

— маршрут к середине ребра
Напомню что наш граф — топологическое представление дорожной сети, геометрические детали для работы алгорифма Дейкстры неважны. Но геометрический аспект значим для пользователя. Припомним, что алгорифм Дейкстры строит кратчайшие маршруты от заданной вершины графа до всех остальных (включая желанную финальную вершину).
Значит исходную вершину мы обязаны определить, но поиск по индексу мы ведем среди ломаных, то есть реально среди ребер. Как осознать от какой вершины (в графе) необходимо прокладывать маршрут, чай промежуточных вершин сегмента там нет, а значит нужно предпочесть либо исходную, либо финальную вершину обнаруженного сегмента.


Рис 6.

Впрочем для пользователя такое решение не будет комфортным, представьте длиннющее шоссе, без поворотов и разворотов (а такое случается зачастую).

Источник: programmingmaster.ru
Оставить комментарий
БАЗА ЗНАНИЙ
СЛУЧАЙНАЯ СТАТЬЯ
СЛУЧАЙНЫЙ БЛОГ
СЛУЧАЙНЫЙ МОД
СЛУЧАЙНЫЙ СКИН
НОВЫЕ МОДЫ
НОВЫЕ СКИНЫ
НАКОПЛЕННЫЙ ОПЫТ
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB