www.gisinfo.ru     |    panorama@gisinfo.ru   |    рус | eng | блг   


Граф дорог

 

Создание, редактирование и поиск кратчайших маршрутов по графу сети

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

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

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

Граф дорог создается по выделенным объектам дорожной сети и представляет собой пользовательскую карту с дугами и узлами. На этапе построения в семантические характеристики дуг и узлов записывается информация о связности сети и атрибуты для решения поисковых задач. Дуги можно создавать двух видов – с двусторонним и односторонним движением.

Средства редактирования графа дорог предназначены для уточнения графа в местах многоуровневых развязок и формирования запретов поворотов. Пользователь имеет возможность вручную удалить, добавить узлы сети, заменить дугу с двусторонним движением на дугу с односторонним движением, провести распараллеливание дорог, создать дуги и развороты, сформировать на перекрестках запреты поворотов.

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

Особенности цифрового описания графа дорог

Граф дорог и дорожных сооружений создается в виде отдельной пользовательской карты (слоя) без деления на номенклатурные листы. Объекты, описывающие граф дорог, составляют отдельный слой в классификаторе цифровых навигационных планов городов. Граф дорог содержит два основных типа объектов – дуги и узлы.

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

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

Для упрощения описания запретов поворотов на перекрестках может применяться повторяемая семантика 32821. Дуга, имеющая запреты на переход в другие дуги (запреты поворотов) должна иметь список семантик с кодом 32821, содержащих номера дуг, на которые запрещен переход. Запреты разворотов описываются семантикой 32822.

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


Пример простых Т-образных перекрестков


Пример пересечения двух дорог на разных уровнях с полным набором съездов

Панель задачи "Граф дорог"

  • Построение сети
  • Создание узла сети
  • Создание дуги сети
  • Изменение направления цифрования
  • Изменение типа движения

 

  • Удаление узла из сети
  • Добавление узла в сеть
  • Распараллеливание дорог
  • Создание съездов и разворотов
  • Запрет левого поворота на Т-образном перекрестке
  • Запрет правого поворота на Т-образном перекрестке
  • Формирование запретов поворотов

 

  • Построение минимального маршрута
  • Построение графа удаленности
  • Минимальный путь между точками
  • Минимальный путь между точками (выбор точек из файла)

 

  • Шаг назад
  • Выход из задачи

Автоматизированное создание графа дорог

Режим Построение сети выполняет создание геометрической сети дуг и узлов с одновременным построением логической сети. Сеть строится по выделенным на карте линейным объектам. Выделенные точечные объекты при построении будут добавлены в сеть как злы сети. Выделенные векторные объекты могут быть обработаны как линейные или как точечные. Для создания сети используются классификаторы service.rsc, road10.rsc, road25.rsc которые содержат объекты: узел сети, дугу сети, а также семантики, необходимые для дальнейшей работы с сетью. Если у выделенных линейных объектов имеется семантика, которая указывает на одностороннее движение, то можно построить сеть с односторонним движением. Данный режим позволяет не создавать узлы на пересечении объектов, которые находятся на разных уровнях (при этом объекты не должны иметь общих точек метрики).

В результате построения создается пользовательская карта, содержащая следующие типы объектов: узел сети и дуга сети. Все объекты созданной карты имеют обязательную семантику “Номер сети”. Для узлов обязательной характеристикой является ссылка на объект- дуга, которой принадлежит узел, для дуг обязательные семантики – номер первого и последнего узлов для данной дуги и ссылка на объект карты. Пользователь может изменить внешний вид создаваемых объектов, указав, новый классификатор и выбрав из него вид объектов узлов и дуг. При успешном завершении задачи создается текстовый файл протокола работы. Имя файла протокола совпадает с именем пользовательской карты, но имеет расширение LOG.

Редактирование графа дорог

Создание узла сети. Для создания узла сети нужно выбрать дугу сети и указать на ней точку, где предполагается создать новый узел. Семантические характеристики для новых объектов заносятся автоматически.

Создание дуги сети. Для создания дуги нужно выбрать узел сети и создавать линию – дугу сети. Если завершить создание дуги на уже существующем узле, то в семантику дуги Номер конечного узла запишется номер данного узла. При отсутствии в пределах одного метра на карте узла сети, в последней точке дуги будет создан новый узел сети.

Изменение направления цифрования. Чтобы изменить направление цифрования у дуг сети нужно выбрать на карте объект для редактирования.

Изменение типа движения. Данный режим заменяет объект ДУГА СЕТИ на объект ДУГА СЕТИ ОДНОСТОРОННЯЯ и наоборот.

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

Добавление узла в сеть. Данный режим предназначен для добавления узла в сеть. Для выполнения режима необходимо открыть пользовательскую карту с построенной сетью и указать два объекта – дуги, на пересечении которых будет вставлен узел. Режим добавления узла является обратной задачей к режиму удаления узла, а также осуществляет дотягивание одной дуги к другой, если расстояние между ними менее 100 метров на местности.

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

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

Формирование запретов поворотов. При активизации режима необходимо в карте указать узел графа сети, соответствующий перекрестку (пересечению дорог), имеющему запрещенные направления проезда. Формирование запретов поворотов с одной дороги на другую обеспечивается заполнением семантики Номер запрещенной дуги в дуге графа сети. Каждая дуга сети соответствует участку дороги между узлами сети (перекрестками). После выбора узла сети открывается диалог, в верхней части которого изображена схема перекрестка, содержащая участок сети дорог – выбранный узел, прилегающие дуги сети, соответствующие участкам пересекающихся дорог и номера дуг графа сети. В нижней части диалога расположена таблица запрета поворотов. В правом столбце таблицы содержатся номера дорог, с которых будет запрещен поворот. В верхней строке таблицы содержатся номера дорог, на которые будет запрещен поворот. Остальные ячейки таблицы содержат указатели запрета поворота. Серым цветом отмечены ячейки, в которых можно указать запрет разворота на выбранном перекрестке.

Контроль и расчеты по графу

Качество создаваемых цифровых навигационных карт и планов городов обеспечивается качеством создания графа дорог, и сбора данных об объектах сервиса и дорожных знаках, которые дополняют описание графа дорог справочной информацией.

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

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

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

В качестве исходных данных могут использоваться цифровые топографические карты. Для обеспечения точности графа дорог предварительно должно быть выполнено обновление объектов дорожной сети и дорожных сооружений. При обновлении объектов дорожной сети и дорожных сооружений должен быть выполнен контроль топологии объектов в точках примыкания.

Если граф создается с использованием треков, записанных на GPS-приемниках, то после сбора всех данных на навигационной карте (плане) выполняется контроль топологии элементов графа (треков) в точках примыкания.

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

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

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

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

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


Режим Построение минимального маршрута предназначен для определения кратчайшего расстояния между двумя узлами сети. Для выполнения режима необходимо открыть пользовательскую карту с построенной сетью, т.е. на карте должны быть объекты узлы сети с обязательными семантиками: номер сети и ссылка на дугу сети, и дуги с семантиками: номер первого и последнего узлов для данной дуги, ссылка на объект карты и номер сети. Минимальный маршрут может быть построен по расстоянию и по времени, в последнем случае дуга должна иметь семантику “Скорость”. Процесс построения осуществляется путем указания начальной и конечной точек маршрута, а также параметра построения (длина или время). Чтобы установить критерии построения минимального маршрута по семантическим характеристикам необходимо заполнить таблицу "Фильтр по семантике дуг". Для того чтобы исключить из обработки некоторые участки (например, аварийные), нужно выделить на карте дуги сети и установить опцию Исключать выделенные объекты из построения.
В результате работы режима на карте отображается объект - минимальный маршрут, вычисляется длина пути. В таблицу диалога статистики записываются реальные объекты карты и протяженность маршрута по каждому объекту. Можно выбрать условный знак и записать построенный путь как объект карты.

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

Режим Построение минимального пути между указанными точками предназначен для определения минимального пути между опорными точками, при условии, что каждую точку нужно пройти один раз (точка старта и финиша могут совпадать). Для выполнения режима нужно открыть пользовательскую карту с построенной сетью, т.е. на карте должны быть объекты узлы сети с обязательными семантиками: номер сети и ссылка на дугу сети, и дуги с семантиками: номер первого и последнего узлов для данной дуги, ссылка на объект карты и номер сети. Опорные точки выбираются из карты либо из текстового файла. Выбор из карты осуществляются нажатием левой клавиши мыши, завершается выбор точек двойным нажатием левой клавиши мыши. Для выбора опорных точек из тестового файла необходимо указать имя файла. Файл должен содержать список значений семантической характеристики «Собственное название» (например, список может состоять из названий населенных пунктов). При выборе опорных точек из текстового файла объекты узлы сети должны иметь семантическую характеристику «Собственное название» (записывается на этапе создания сети). Минимальный маршрут может быть построен по расстоянию и по времени, в последнем случае дуга должна иметь семантику “Скорость”, а также с учетом семантических характеристик. Чтобы установить критерии построения минимального маршрута по семантическим характеристикам необходимо заполнить таблицу «Фильтр по семантике дуг. Для того чтобы исключить из обработки некоторые участки (например, аварийные), нужно выделить на карте дуги сети и установить опцию Исключать выделенные объекты из построения.
Результатом работы является таблица, в которой указан порядок обхода точек, длина кратчайшего пути между текущей точкой и следующей, протяженность всего маршрута.

Экспорт в другие форматы

Граф дорог можно экспортировать в различные обменные форматы:

  • SXF (SXF,TXF,DIR)
  • Google Earth (KML)
  • AutoCAD (DXF)
  • ArcView (SHP)
  • MapInfo (MIF)
  • S57 (030, 000)
  • GPS/Польский формат (MP)
  • GDF (начиная с версии 10.4.1)
  • Базы данных (DBF,TXT)
  • Матрицы высот (TXT…)
  • Растры (BMP,TIF, JPEG,EMF,EPS…)

 

Продукты | Технологии | Классификаторы | Проекты | Скачать | Цены | Форум | Статьи | Обучение | Контакты
В начало Написать разработчикам Поиск на сайте