Графо-аналитические операции

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

Рассмотрим общую схему решения задач на графах при помощи ГИС. Поскольку каждая дуга графа представляет собой определенный пространственный объект, следовательно, каждой дуге графа может быть поставлено в соответствие некоторое число - одна из характеристик объекта, например его длина, расход воды, качество дорожного покрытия и т.д. Операция присваивания таких чисел дугам графа называется операцией взвешивания графа, а ее результаты можно условно назвать "таблицей взвешивания графа". Возможно, для решения некоторых задач потребуется построение нескольких таких таблиц, содержащих значения различных характеристик. Далее для решения задач на графах необходимо определить аналитическое представление графа. Одним из способов такого представления является упоминаемая выше топологическая таблица цифровой карты, которая содержит все сведения о дугах и узлах.

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

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

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