ВВЕДЕНИЕ 4
ГЛАВА 1 АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 6
1.1 Основные понятия предметной области 6
1.2 Методы иерархического разбиения пространства 8
1.2.1 kD-деревья 9
1.2.2 BSP-деревья 11
1.2.3 Interval Tree 12
1.2.4 R-деревья 13
1.2.5 Дерево квадрантов 15
1.3 Обзор алгоритмов кластеризации данных 17
1.3.1 Меры расстояний 18
1.3.2 Алгоритмы иерархической кластеризации 20
1.3.3 Объединение кластеров 21
1.4 Выбор инструментальных средств разработки 23
ГЛАВА 2 ПРОЕКТИРОВАНИЕ ВЕБ-ПРИЛОЖЕНИЯ 28
2.2 Проектирование структуры веб-приложения 28
2.3 Проектирование базы данных 29
2.4 Определение требований к алгоритму 31
ГЛАВА 3 РАЗРАБОТКА ВЕБ-ПРИЛОЖЕНИЯ 33
3.1 Разработка алгоритма поиска и анализа свойств объектов на местности 33
3.2 Разработка информационного обеспечения 36
3.3 Разработка веб-приложения 37
ГЛАВА 4 ИНТЕГРАЦИЯ И ТЕСТИРОВАНИЕ ПО 44
4.1 Интеграция ПО в геоинформационную систему «Активист» 44
4.2 Тестирование алгоритма поиска и анализа свойств объектов на
местности 46
ЗАКЛЮЧЕНИЕ 50
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 50
ПРИЛОЖЕНИЯ 53
Трудно представить себе современный мир без интерактивных географических карт на компьютерах и мобильных устройствах в наши дни. В настоящее время навигация и нахождение нужных мест на карте стали намного проще благодаря развитию различных геоинформационных систем.
Однако удобство использование интерактивных карт на компьютерах и мобильных устройствах целиком и полностью зависит от правильного отображения нужных данных на экране пользователя. Перерисовка десятков тысяч объектов при навигации в пользовательском интерфейсе системе занимает длительное время. Распространенным решением проблемы отображения географических объектов является их предварительная кластеризация с целью отображения мест скопления объектов, а не отдельных объектов.
Поэтому все еще остается актуальной задачей анализа и обобщения картографических данных с целью донесения до конечного пользователя той информации, в которой он нуждается.
Актуальность темы выпускной квалификационной работы заключается в необходимости оптимизации производительности отображения географических объектов в картографических приложениях для совершенствования пользовательского опыта взаимодействия.
Цель данной выпускной квалификационной работы заключается в оптимизации производительности отображения большого количества объектов на интерактивной карте в веб-приложении используя разработанный алгоритм.
Для выполнения поставленной цели необходимо решить следующие задачи:
1. Проанализировать предметную область.
2. Спроектировать веб-приложение, определить функциональные
требования к алгоритму.
3. Разработать веб-приложение и алгоритм.
4. Интегрировать и протестировать полученный алгоритм.
В главе «Анализ предметной области» будут описаны основные понятия предметной области, проведен обзорный анализ методов иерархического разбиения двухмерного пространства, а также обзор алгоритмов кластеризации данных. Кроме того, будет проведен выбор инструментальных средств разработки.
В главе «Проектирование веб-приложения» будет описано проектирование основных составных частей веб-приложения и алгоритма.
В главе «Разработка веб-приложения» будет описана последовательность основных этапов разработки веб-приложения и алгоритма.
В главе «Интеграция и тестирование ПО» будут приведены данные тестирования алгоритма, а также описаны результаты интеграции разработанного алгоритма в систему.
В заключении сделан вывод о степени достижения поставленных целей и задач.
Данная выпускная квалификационная работа содержит 52 страницы, 20 рисунков, 6 формул, 10 листингов и 2 приложения.
В ходе выполнения выпускной квалификационной работы были спроектированы и разработаны веб-приложение и алгоритм поиска и анализа свойств объектов на местности. В результате чего были решены следующие задачи:
1. Исследованы существующие методы иерархического разбиения пространства и алгоритмы кластеризации данных.
2. Спроектированы база данных и веб-приложение.
3. Определены функциональные требования к алгоритму.
4. Разработано веб-приложение и реализован алгоритм.
5. Проведена интеграция и тестирование реализованного алгоритма.
В первой главе были рассмотрены основные методы иерархического разбиения пространства. Также был произведен обзор алгоритмов кластеризации данных и произведен выбор инструментальных средств разработки.
Во второй главе спроектировано веб-приложение, база данных для хранения объектов, определены функциональные требования к алгоритму.
В третье главе разработано веб-приложение, реализована база данных, и разработан алгоритм поиска и анализа свойств объектов на местности.
В четвертой главе была проведена интеграция алгоритма в геоинформационную систему «Активист». Проведено тестирование алгоритма и замеры производительности на разных объемах данных. Алгоритм показал заметный прирост в производительности приложения и улучшил пользовательский опыт взаимодействия с системой, о чем имеется акт апробации.
