Исследование методов визуализации данных о покрытии географической зоны телекоммуникационными сервисами Максим Логунов, 717 группа Научный руководитель - Максим Антоненко, к.ф.-м.н.
Описание проблемы Обозначение доступности сервиса цветом или пиктограммой хорошо лишь при высокой детализации. На низкой детализации наглядность данных теряется.
Задача Визуализировать данные о доступности проводного телекоммуникационного сервиса. Входные данные: координаты зданий и сведения о присутствии сервиса в них. Выходные данные: изображение или данные в формате, пригодном для использования в существующих ГИС. Проблема: существуют лишь примитивные способы визуализации проводного сервиса
Исследуемые методы построение ячеек Вороного расчет скалярного поля плотности покрытия, построение изолиний этого поля
Алгоритм «Скалярное поле» 1. разбиение области на зоны и установление принадлежности зданий этим зонам; 2. построение на его основе скалярного поля; 3. построение изолиний нужного уровня плотности.
Сравнительное тестирование производительности Подход «Скалярное поле» оказался на порядок быстрее традиционного подхода с построением ячеек Вороного. Линейная шкала Логарифмическая шкала
Теоретическая оценка вычислительной сложности N кол-во зданий. построение ячеек Вороного: лучшие реализации ~ O(N log N) «Скалярное поле»: m кол-во домов в ячейке; p кол-во ячеек. ~ O(mp) + O(p) ~ O(mp) ~ O(N)
Представление результата Ячейки Вороного «Скалярное поле»
Выводы Были предложены и исследованы два метода решения поставленной задачи. Создано действующее приложение по визуализации зон покрытия. Осуществлена интеграция с ГИС Google Maps.
Планируемые работы Проверка работы алгоритма на реальных данных. Создание алгоритма анализа визуализируемой области. Коррекция поведения алгоритма на больших масштабах рассматриваемых областей покрытия.
Спасибо за внимание!