Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,118

RECURSIVE ALGORITHM SYNC API-REQUESTS TO THE YANDEX.MAPS GIS

Mokhov V.A. 1 Kubil V.N. 1 Kuznetsova A.V. 1 Georgitsa I.V. 1
1 South-Russian State Politechnical University (Novocherkassk Technical Institute) named after M.I. Platov
В работе отражена тенденция ориентации современных ИТ-вендоров в направлении развития сервисов геоинформационных систем (ГИС). Выполнен анализ популярных российских картографических сервисов. Рассмотрены особенности выполнения сценариев на языке JavaScript и основные идеи рекурсивного программирования. Поставлена задача построения алгоритма для формирования оптимального автомобильного маршрута через заданные опорные точки на электронной карте – задача коммивояжёра. Выявлена и показана проблема синхронизации, возникающая при выполнении множественных асинхронных клиентских запросов к ГИС-сервису Яндекс.Карты через интерфейс JS API 2.0 при вычислении маршрутов между каждой парой опорных точек. Выполнен анализ причин указанной проблемы и предложено соответствующее алгоритмическое решение на основе механизма простой программной рекурсии при обращении к асинхронному сервису JavaScript. Описан алгоритм получения матрицы расстояний для множества опорных точек и представлены результаты его работы на конкретном примере. Предложенное решение обеспечивает гарантированное получение промежуточных результатов от ГИС-сервиса до их последующей обработки и может быть успешно заимствовано для использования в проектах на основе других геоинформационных систем.
The article is devoted to modern trends in the orientation of IT vendors in the direction of development of services of geographic information systems (GIS). The Russian popular mapping services were analyzed. The features of the scripting language JavaScript and the basic ideas of recursive programming were reviewed. The task of constructing an algorithm to generate the optimal driving route through a predetermined reference points on an electronic map – traveling salesman problem – was formulate. Synchronization problem which occurs when performing multiple asynchronous client requests to the GIS service interface Yandex.Maps JS API 2.0 in calculating the routes between each pair of control points was identified and shown. The problem’s causes were the analyzed. The appropriate algorithmic solution based on a mechanism of simple programming recursion for handling an asynchronous service JavaScript was suggested. An algorithm for obtaining distance matrix for the set of control points and the algorithm’s results on a concrete example were described. The proposed solution provides guaranteed receipt of the interim results of the GIS service prior to further processing. This solution can be successfully borrowed for use in projects based on other geographic information systems.
geographic information systems
Web-programming
synchronization
asynchronous functions
recursion
JavaScript
API
traveling salesman problem
the distance matrix
1. Buchatskij P.Ju., Buchatskaja V.V. Vestnik Adygejskogo gosudarstvennogo universiteta. Serija 4: Estestvenno-matematicheskie i tehnicheskie nauki, 2014, no. 4 (147), pp. 154–159.
2. K’jaer O.Ju. Ocherjodnost’ sobytij i sinhronizacija v JavaScript, Available at: http://javascript.ru/tutorial/events/timing, (accessed 17 August 2015).
3. Mironova Ju.N. Mezhdunarodnyj zhurnal prikladnyh i fundamental’nyh issledovanij, 2014, no. 8, pp. 155–156.
4. Mohov, V.A., Borodulina E.R. Rostov-na-Donu: «Izvestija JuFU. Tehnicheskie nauki», 2014, no.4, pp. 230–234.
5. Geograficheskaja informacionnaja sistema (GIS-Association), Available at: http://www.gisa.ru/13058.html (accessed 17 August 2015).
6. Sovremennyj uchebnik JavaScript: Porjadok obrabotki sobytij (JAVASCRIPT.RU), Available at: https://learn.javascript.ru/events-and-timing-depth, (accessed 17 August 2015).
7. Rekursija (Russian Collegiate fund), Available at: http://www.russika.ru/ef.php?s=4585, (accessed 17 August 2015).
8. Strukov V.B. Trudy Vseross. nauchno-tehn. internet-konf. Kadastr nedvizhimosti i monitoring prirodnyh resursov (Proc. Russ. Sci.-Tech. Internet-Conf. Real Estate Cadastre and monitoring of natural resources) Available at: http://kadastr.org/conf/2010/pub/infoteh/vybor-webgis-zem-uch.htm, (accessed 17 August 2015).
9. Strukov V.B. Trudy Vseross. nauchno-tehn. internet-konf. Kadastr nedvizhimosti i monitoring prirodnyh resursov (Proc. Russ. Sci.-Tech. Internet-Conf. Real Estate Cadastre and monitoring of natural resources) Available at: http://kadastr.org/conf/2012/pub/infoteh/yandex-api-webgis.htm, (accessed 17 August 2015).
10. JavaScript API: (Yandex Maps) Available at: https://tech.yandex.ru/maps/jsapi/, (accessed 17 August 2015).
11. JavaScript API: (Yandex Maps) Available at: https://tech.yandex.ru/maps/, (accessed 17 August 2015).

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

Указанные сервисы впоследствии стали быстро дополняться пространственными базами данных, графическими редакторами, множественными инструментами для пространственно-координатного анализа данных и т.п., постепенно трансформируясь в геоинформационные системы [5].

Важно отметить, что выделяется достаточно большое количество классификационных признаков для ГИС [9], среди которых часто оперируют такими, как территориальный охват, предметная область информационного моделирования, масштабность охвата территории и т.п. В данной работе предлагается к рассмотрению несколько аспектов, связанных с разработкой новых геоинформационных проектов на основе бесплатного интерфейса JS API 2.0, предоставляемого ГИС Яндекс.Карты [10]. Однако решение, показанное в задаче с API конкретной ГИС, может быть успешно заимствовано для использования в проектах для других геоинформационных систем (вне зависимости от их принадлежности к какой-либо конкретной категории по приведенным выше признакам).

Целью работы является реализация механизма синхронизации множественных клиентских запросов к ГИС-сервису Яндекс.Карты через интерфейс JS API 2.0 на основе простой программной рекурсии.

Материалы и методы исследования

На сегодняшний день в России популярными картографическими сервисами принято считать Яндекс.Карты, Google Maps и OpenStreetMap [9]. Наиболее существенные характеристики для указанных ГИС представлены в таблице.

Каждая из рассмотренных систем поддерживает набор компонентов для размещения интерактивных карт на веб и их отображения в браузере. Интерфейсный набор функций API позволяет размещать на картах различные объекты, выполнять поиск адресов, прокладку маршрутов, построение собственных схем и иные операции. При этом указанный интерфейс требует поддержки JavaScript [11].

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

Суть недостатка проявляется в проблеме возникновения ошибок выполнения команд сценария на JavaScript, связанной с очерёдностью исполнения команд в JavaScript-приложениях. Ошибки, не дававшие о себе знать при разработке, неожиданно начинают приводить к проблемам для конечного пользователя. Причём основной причиной этих ошибок являются не авторские просчёты программиста, а выполнение JavaScript-приложения на старом компьютере или использование медленного соединения. Важно то, что эти проблемы могут проявляться случайным образом и их сложно воспроизвести [2].

Помимо сказанного современные браузеры позволяют порождать подпроцессы Web Workers, которые, исполняют задачи JavaScript параллельно и могут отправлять и принимать сообщения, не блокируя при этом другие процессы [6]. Тем самым части веб приложения обрабатываются параллельно, не дожидаясь возврата результатов первоначально вызванных функций.

В программировании для организации множественных циклов без явных повторений частей программы широко применяется приём рекурсии – вызова функции из неё же самой (с изменяемыми значениями входных параметров). Если такой вызов выполняется указанной функцией непосредственно, то такой вид рекурсии называется простым, а если через другие функции – сложным (или косвенным). При этом количество вложенных вызовов функции называется глубиной рекурсии [7].

Характеристики популярных российских ГИС

ГИС

Характеристики

Краткая характеристика

Преимущества

Режим использования

Официальный веб-сервер

Яндекс.Карты

Ведущий сервис России с ежемесячным обновлением собственных карт

– большее количество планов и панорам российских городов, чем на Google;

– ведущий сервис пробок в России;

– панорамы с воздуха;

– привязка веб-камер

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

maps.yandex.ru

Google Maps

Ведущий мировой сервис. Развивается в сотрудничестве с NASA

– самая большая база качественных фотографий земной поверхности;

– большая база планов городов мира;

– наличие 3D-фотографий поверхности с эффектом объема;

– самая большая база панорам;

– одна из самых удобных форм вставки на сайт и API

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

maps.google.com

Open StreetMap

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

– самая большая база планов городов мира

Регулируется свободной лицензией CC-BY-SA 2.0

openstreetmap.org

Результаты исследования и их обсуждение

В рамках решения некоммерческих задач в ЮРГПУ(НПИ) имени М.И. Платова авторами было разработано веб-ГИС приложение, основанное на использовании инструментария API Яндекс.Карты.

Общий алгоритм работы приложения ориентирован на построение оптимального автомобильного маршрута через заданные опорные точки на карте. Его схема представлена на рис. 1.

pic_9.tif

Рис. 1. Схема общего алгоритма работы приложения для построения автомобильных маршрутов

Для решения задачи формирования маршрута в приложении последовательно выполняются следующие задачи:

1) запуск приложения в браузере;

2) инициализация карты (загрузка Яндекс.Карты в область, определённую для экранной формы);

3) ввод исходных данных (пользователь расставляет на карте отметки, соответствующие опорным пунктам для построения маршрута);

4) построение матрицы расстояний (приложение, посредством API-запросов к ГИС-серверу Яндекс.Карты, определяет длины маршрутов между каждой парой точек и записывает эти данные в матрицу расстояний);

5) расчёт маршрута (на основании матрицы расстояний из п. 4 находится кратчайший маршрут для обхода опорных точек, указанных пользователем);

6) отображение маршрута и его описания на экране (выполняется средствами API Яндекс.Карты на основании результатов, полученных в п. 5).

Вопросы визуализации, ввода и вывода данных посредством API ГИС Яндекс.Карты являются тривиальными и весьма проработанными [1, 8], и в данной публикации детально не рассматриваются. Расчёт оптимального маршрута выполняется на основе оптимизированного муравьиного алгоритма для решения задачи коммивояжёра [4].

Основной интерес представляет реализация алгоритма получения матрицы расстояний. При его создании возникла проблема синхронизации: для построения маршрута и получения информации о нём отправляется запрос на сервер Яндекса с помощью функции ymaps.route() [10]:

pic_10.wmf

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

pic_11.tif

Рис. 2. Проблема синхронизации

pic_12.tif

Рис. 3. Схема рекурсивного алгоритма

pic_13.tif

Рис. 4. Результат работы приложения

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

Решение описанной проблемы удалось получить за счёт рекурсивной организации алгоритма множественных вызовов к ГИС-серверу. Схема полученного алгоритма представлена на рис. 3.

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

Вариант результата работы ГИС-приложения, созданного авторами на основе использования описанного рекурсивного алгоритма, представлен на рис. 4.

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

Заключение

Предложенный способ рекурсивной организации алгоритма для выполнения асинхронных запросов к ГИС-серверу Яндекс.Карты на основе интерфейса JS API 2.0 показал очевидную стабильность в работе и может быть успешно заимствован для использования в других ГИС-проектах.

Рецензенты:

Петраков В.А., д.т.н., профессор, заведующий кафедрой «Системный анализ и управление», Южный федеральный университет, г. Ростов-на-Дону;

Привалов А.Н., д.т.н., профессор, Тульский государственный педагогический университет имени Л.Н. Толстого, г. Тула.