Створення, редагування й пошук найкоротших маршрутів по графу мережі

Граф доріг створюється по виділених об'єктах дорожньої мережі і являє собою користувальницьку карту з дугами й вузлами. На етапі побудови в семантичні характеристики дуг і вузлів записується інформація про зв'язність мережі й атрибути для рішення пошукових задач. Дуги можна створювати двох видів - із двостороннім й одностороннім рухом.

Засоби редагування графа доріг призначені для уточнення графа в місцях багаторівневих розв'язок і формування заборон поворотів. Користувач має можливість вручну видалити, додати вузли мережі, замінити дугу із двобічним рухом на дугу з однобічним рухом, провести розпаралелювання доріг, створити дуги й розвороти, сформувати на перехрестях заборони поворотів.

Пошук мінімального шляху між точками (населеними пунктами) здійснюється з урахуванням будь-яких характеристик, записаних у дуги мережі (тип доріг, швидкість руху, кількість проїзних частин). Найкоротший маршрут можна знайти або за мінімальною довжині шляху або за мінімальним часом проходження маршруту. При знаходженні мінімального шляху є можливість виключення деяких дуг, наприклад аварійних ділянок, з пошуку. Результати пошуку відображаються на карті у вигляді об'єкта - маршруту.

Особливості цифрового опису графа доріг

Граф доріг та дорожніх споруджень створюється у вигляді окремої користувальницької карти (шару) без розподілу на номенклатурні аркуші. Об'єкти, що описують граф доріг, становлять окремий шар у класифікаторі цифрових навігаційних планів міст. Граф доріг містить два основних типи об'єктів - дуги й вузли.

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

Вузли можуть послідовно з'єднувати дві дуги, що мають різні характеристики, або з'єднувати кілька дуг у місцях перехресть, розвилок і т.п. Якщо дороги фізично проходять над однією ділянкою місцевості на різних рівнях (тунель, естакада й т.п.), то в точці перетинання доріг на карті графа вузол повинен бути відсутнім. За допомогою набору однобічних і двобічних дуг і вузлів можна однозначно описати різні види перехресть, однорівневих і багаторівневих розв'язок. Якщо на перехресті доріг необхідно показати заборону повороту, то в цьому місці дороги можуть бути показані паралельними однобічними дугами, які мають вузли тільки з тими їхніми дугами, що перетинаються, на які дозволене перестроювання транспорту.

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

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

Приклад простих Т-образних перехресть

Приклад перетинання двох доріг на різних рівнях з повним набором з'їздів

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

Робота зі створення, редагування мережі та вирішення різних розрахункових задач здійснюється за допомогою режимів панелі "Граф доріг":
 

• Побудова мережі
• Створення вузла мережі
• Створення ребра мережі
• Зміна напрямку цифрування
• Зміна типу руху

• Видалення вузла з мережі
• Додання вузла в мережу
• Розпаралелювання доріг
• Створення з'їздів і розворотів
• Заборона повороту ліворуч на Т-образному перехресті
• Заборона повороту праворуч на Т-образному перехресті
• Формування заборони поворотів
  

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

• Шаг назад
• Вихід з задачі
  

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

Режим Побудова мережі виконує створення геометричної мережі дуг і вузлів з одночасною побудовою логічної мережі. Мережа будується по виділеним на карті лінійним об'єктам. Виділені точкові об'єкти при побудові будуть додані в мережу як вузли мережі. Виділені векторні об'єкти можуть бути оброблені як лінійні або як точкові. Для створення мережі використовуються класифікатори service.rsc, road10.rsc, road25.rsc, які містять наступні об'єкти: вузол мережі, дугу мережі, а також семантики, необхідні для подальшої роботи з мережею. Якщо у виділених лінійних об'єктів є семантика, що вказує на однобічний рух, то можна побудувати мережу з однобічним рухом. Даний режим дозволяє не створювати вузли на перетинанні об'єктів, які перебувають на різних рівнях (при цьому об'єкти не повинні мати загальних точок метрики).

У результаті побудови створюється користувальницька карта, що містить наступні типи об'єктів: вузол мережі й дуга мережі. Всі об'єкти створеної карти мають обов'язкову семантику "Номер мережі". Для вузлів обов'язковою характеристикою є посилання на об'єкт - дуга, якій належить вузол, для дуг обов'язкові семантики - номер першого й останнього вузлів для даної дуги й посилання на об'єкт карти. Користувач може змінити зовнішній вигляд створюваних об'єктів, вказавши новий класифікатор і вибравши з нього вид об'єктів вузлів і дуг. При успішному завершенні задачі створюється текстовий файл протоколу роботи. Ім'я файлу протоколу збігається з ім'ям користувальницької карти, але має розширення LOG.

Редагування графа доріг

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

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

Зміна напрямку цифрування. Щоб змінити напрямок цифрування у дуг мережі потрібно вибрати на карті об'єкт для редагування.

Зміна типу руху. Даний режим заміняє об'єкт ДУГА МЕРЕЖІ на об'єкт ДУГА МЕРЕЖІ ОДНОБІЧНА і навпаки.

Видалення вузла з мережі. Даний режим призначений для видалення вузла з побудованої мережі. Вузол для видалення повинен бути розташований на перетинанні чотирьох дуг. Після виконання даного режиму вузол на перетинанні доріг може бути вилучений або виключений з обробки, тобто загального вузла у всіх дуг не буде. Видалення вузлів рекомендується проводити на перетинанні автомобільних доріг з мостами, тунелями, шляхопроводами й ін.

Додавання вузла в мережу. Даний режим призначений для додавання вузла в мережу. Для виконання режиму необхідно відкрити користувальницьку карту з побудованою мережею й вказати два об'єкти - дуги, на перетинанні яких буде вставлений вузол. Режим додавання вузла являється зворотною задачею відносно режиму видалення вузла, а також здійснює дотягування однієї дуги до іншої, якщо відстань між ними менше 100 метрів на місцевості.

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

Створення з'їздів і розворотів. Даний режим призначений для додавання в мережу з'їздів і розворотів на перехрестях доріг. З'їзди й розвороти рекомендується виконувати на перехрестях, для яких проводилося розпаралелювання. При успішному виконанні режиму створюються об'єкти дуги однобічні, і видаляється загальний вузол. Застосовуються результати побудови при визначенні мінімальних маршрутів.

Формування заборон поворотів. При активізації режиму необхідно в карті вказати вузол графа мережі, що відповідає перехрестю (перетинанню доріг), що має заборонені напрямки проїзду. Формування заборон поворотів з однієї дороги на іншу забезпечується заповненням семантики Номер забороненої дуги в дузі графа мережі. Кожна дуга мережі відповідає ділянці дороги між вузлами мережі (перехрестями). Після вибору вузла мережі відкривається діалог, у верхній частині якого зображена схема перехрестя, що містить ділянку мережі доріг - обраний вузол, дуги мережі що прилягають, які відповідають ділянкам пересічних доріг, і номера дуг графа мережі. У нижній частині діалогу розташована таблиця заборони поворотів. У правому стовпці таблиці містяться номери доріг, з яких буде заборонений поворот. У верхньому рядку таблиці містяться номери доріг, на які буде заборонений поворот. Інші чарунки таблиці містять показники заборони повороту. Сірим кольором відзначені чарунки, у яких можна вказати заборону розвороту на обраному перехресті.

Контроль і розрахунки по графу

Режим Побудова мінімального маршруту призначений для визначення найкоротшої відстані між двома вузлами мережі. Для виконання режиму необхідно відкрити користувальницьку карту з побудованою мережею, тобто на карті повинні бути об'єкти вузли мережі з обов'язковими семантиками: номер мережі й посилання на дугу мережі, і дуги із семантиками: номер першого й останнього вузлів для даної дуги, посилання на об'єкт карти й номер мережі. Мінімальний маршрут може бути побудований по відстані й за часом, в останньому випадку дуга повинна мати семантику "Швидкість". Процес побудови здійснюється шляхом вказівки початкової й кінцевої точок маршруту, а також параметра побудови (довжина або час). Щоб установити критерії побудови мінімального маршруту по семантичних характеристиках необхідно заповнити таблицю "Фільтр по семантиці дуг". Для того щоб виключити з обробки деякі ділянки (наприклад, аварійні), потрібно виділити на карті дуги мережі й установити опцію Виключати виділені об'єкти з побудови.
У результаті роботи режиму на карті відображається об'єкт - мінімальний маршрут, обчислюється довжина шляху. У таблицю діалогу статистики записуються реальні об'єкти карти й протяжність маршруту по кожному об'єкту. Можна вибрати умовний знак і записати побудований шлях як об'єкт карти.

Побудова графа віддаленості. Граф віддаленості являє собою набір об'єктів, що перебувають у певних межах від зазначеного вузла мережі. Для побудови графа необхідно вказати вузол мережі й ввести числове значення (довжину в метрах).
У результаті роботи режиму на карті будуть виділені дуги, розташовані на відстані, яка менша заданої від зазначеного вузла.

Режим Побудова мінімального шляху між зазначеними точками призначений для визначення мінімального шляху між опорними точками, за умови, що кожну точку потрібно пройти один раз (точка старту й фінішу можуть збігатися). Для виконання режиму потрібно відкрити користувальницьку карту з побудованою мережею, тобто на карті повинні бути об'єкти вузли мережі з обов'язковими семантиками: номер мережі й посилання на дугу мережі, і дуги із семантиками: номер першого й останнього вузлів для даної дуги, посилання на об'єкт карти й номер мережі. Опорні точки вибираються з карти або з текстового файлу. Вибір з карти здійснюються натисканням лівої клавіші миші, завершується вибір точок подвійним натисканням лівої клавіші миші. Для вибору опорних точок з тестового файлу необхідно вказати ім'я файлу. Файл повинен містити список значень семантичної характеристики "Власна назва" (наприклад, список може складатися з назв населених пунктів). При виборі опорних точок з текстового файлу об'єкти вузли мережі повинні мати семантичну характеристику "Власна назва" (записується на етапі створення мережі). Мінімальний маршрут може бути побудований по відстані й за часом, в останньому випадку дуга повинна мати семантику "Швидкість", а також з урахуванням семантичних характеристик. Щоб установити критерії побудови мінімального маршруту по семантичних характеристиках необхідно заповнити таблицю "Фільтр по семантиці дуг. Для того, щоб виключити з обробки деякі ділянки (наприклад, аварійні), потрібно виділити на карті дуги мережі й установити опцію Виключати виділені об'єкти з побудови.
Результатом роботи є таблиця, у якій зазначений порядок обходу точок, довжина найкоротшого шляху між поточною точкою й наступною, довжина всього маршруту.

Експорт в інші формати

Граф доріг можна експортувати в різні обмінні формати:
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...)