SUMMARY
The possibility for creation of web based application by applying Dijkstra’s Algorithm is described in the article. The main objective of the study is to show how GIS tools can help users of geographic information.
For the development of application of geo-information system (GIS) based on a web platform it is necessary to solve the following tasks:
• Analysis and structuring of output data, the stages for the creation of an appropriate database are described and transformation of data, ways to implement GIS are presented and models for visualization and interaction with spatial and attribute information to objects;
• Description of the application of GIS by using web platform.
РЕЗЮМЕ
В статията е разгледана възможността за създаване на уеб базирано приложение, като е използван алгоритъмът на Дейкстра. Основна цел на разработката е да се покаже как със средствата на ГИС може да се подпомогнат потребителите на географска информация.
За разработването на приложение на геоинформационната система (ГИС) чрез използване на уеб платформа е необходимо да се решат следните задачи:
• Анализ и структуриране на изходните данни, описание на етапите за изграждането на подходяща база данни и трансформация на данните, представени са начини за реализация на ГИС и модели за визуализация и интеракция с пространствена и атрибутна информация за обектите;
• Описание на приложението на ГИС чрез ползването на уеб платформа.
1. ВЪВЕДЕНИЕ
Управлението на пространствени данни включва процеса на набавянето, съхраняването и поддържането, анализирането и публикуването им. Много години това е извършвано, ползвайки аналогови източници на данни и ръчна обработка. Въвеждането на съвременните технологии води до увеличено използване на компютри и информационни технологии във всички аспекти на управление на пространствени данни. Технологиите, използвани в тази област, са географските информационни системи. ГИС се използват от множество различни дисциплини като инструменти за управление на пространствени данни в географска среда.
2. АЛГОРИТЪМ НА ДЕЙКСТРА
Алгоритъмът на Дейкстра (Dijkstra) е оптимизационна задача от теорията на графите. Той е един от най-комерсиалните алгоритми. Причините, поради които този алгоритъм е толкова известен, са няколко [2]:
• Той е доста понятен и някак естествен (в сравнение с други алгоритми за решаване на същия тип задачи);
• Лесно се имплементира на PC и прилага на лист;
• Дава добри резултати при имплементация на PC откъм време, с някои оптимизации естествено.
Решението на задачата за намиране на оптимален път в ГИС осигурява и показва върху карта път от А до Б при определени оптимални условия. Прилага се и като основна задача при управлението на трафика в населените места, оптимизиране на доставки, определяне област на обслужване и други. Определянето на оптимален път е свързано с минимизиране стойности на време за изминаване на път, разстояние, транспортен разход или друга характеристика, която е важна за една транспортна инфраструктура.
Намирането на оптимален път в градска среда зависи от множество фактори/условия – дължината вид/клас на уличните отсечки, възможността за преминаване през тях, вида на транспортното средство, скоростта на движение, броя светофари, ремонтни работи и т.н (фиг.1) [1].
Фиг. 1. Намиране на оптимален път [1]
Изследват се характеристиките на уличната/пътната мрежа, но практически задачата има смисъл, когато осигурява минимизиране на количествена характеристика път, време, цена и др. Входни данни за решаване на задачата са:
1. Транспортна мрежа – свързан граф.
2. Адреси – точки, които нямат общи геометрични характеристики с мрежата.
Предпоставки за разработване на приложение на ГИС за намиране на оптимален път:
• Улиците се представят чрез техните оси, като линейна мрежа от сегменти. Всеки сегмент в базата данни на ГИС е линия ‘LINESTRING’;
• Всеки сегмент има начало и край, които могат да не са свързани с друг сегмент или да съвпадат с начало или край на друг сегмент;
• Всеки сегмент има характеристика „тежест” P(u,v) – число, което определя минимизирането на пътя – дължина, време и др.
• Оптимален път е съвкупност от последователно свързани сегменти с начало i и край j и P(i,j) = minP(u,v)
• Минимален път между адреси А, B е оптималният път с начален сегмент най-близкия до А и краен сегмент - най-близкия до B.
ПРИЛАГАНЕ НА АЛГОРИТЪМ НА ДЕЙКСТРА ЗА СЪЗДАВАНЕ НА УЕБ БАЗИРАНО ПРИЛОЖЕНИЕ
Д-р инж. Кристина Микренска-Чернева, УАСГ, София
инж. Димитър Симеонов, Bright Marketing Research, София
31
ГКЗ 5-6 ' 2016