Введение к работе
Триангуляционная модель широко используется в различных системах хранения и обработки пространственных данных: географических информационных системах, трехмерных графических редакторах, системах моделирования, видеомонтажа и т. д. Объекты описываются с помощью поверхностей, которые в свою очередь являются сетками триангуляции.
В ряде систем предъявляются жесткие требования к объему памяти, необходимой для хранения модели, быстроте выполнения алгоритмов, затратам на поддержку кода, то есть простоте программной реализации алгоритмов анализа данных и их точности. В работах Abdul-Rahman A., Jones С, Frank А., Скворцова А.В. приводится описание всего нескольких структур данных без численного обоснования их оптимальности. Описанные выше требования рассмотрены лишь в работах Тюкачева Н.А., однако подробно описан только двухмерный случай. Таким образом, хотя модель сильно влияет на почти все вышеперечисленные характеристики, на практике она чаще всего определяется интуитивно.
Триангуляционную модель данных можно представить в виде частного случая Entity-Relationship (ER) модели, структура которой определяется набором сущностей и связями между этими сущностями, что позволяет рассматривать задачу определения модели данных, удовлетворяющей указанным требованиям, в контексте любой системы, использующей ER-представление, например СУБД.
С геометрической точки зрения структура триангуляции имеет множество характеристик, таких как размер, форма, равномерность сетки. Эти характеристики непосредственно влияют на точность результатов выполнения алгоритмов анализа данных. Существуют различные алгоритмы триангуляции, описанные в работах Скворцова А.В., Роджерса Д., Dwyer R., Lewis В., Baker В., Bern М., Mitchell S., Chew L., Ruppert J. Эти алгоритмы позволяют получить сетку с треугольниками, удовлетворяющими некоторым требованиям: критерий Делоне, размеры углов, отношения сторон, сумма длин ребер и т. д., однако используемые критерии при этом чаще всего являются локальными и не учитывают всех необходимых характеристик.
Таким образом, научная и практическая проблема при создании систем обработки и хранения пространственных данных заключается в сложности учета всех характеристик модели триангуляции, что позволило бы выбрать подходящую структуру данных, а также учитывающую вышеописанные требования геометрическую структуру триангуляции. Для баз данных часто возникает необходимость в их реструктуризации с целью удаления уже не используемых
сущностей и связей, что также представляет проблему при большом размере базы.
Целью работы является разработка математического и программного обеспечения, позволяющего проводить структурную оптимизацию модели триангуляции на основе многокритериальных оценок для обеспечения экономии памяти, скорости и точности выполнения алгоритмов анализа в системах хранения и обработки пространственных данных.
Задачи исследования.
Для достижения поставленной цели необходимо выполнение следующих задач:
Построение критерия оптимальности структуры данных триангуляционной модели, учитывающего объем памяти, необходимый для хранения модели, и скорость выполнения заданного набора алгоритмов.
Разработка методики, позволяющей проводить автоматизированный поиск оптимальной структуры данных по описанному в предыдущем пункте критерию.
Получение оптимальных структур данных триангуляционной модели для использования совместно с основными алгоритмами синтеза и анализа, применяемыми в системах хранения и обработки пространственных данных.
Построение критерия, позволяющего оптимизировать геометрическую структуру сетки триангуляции на основе ее интегральных свойств.
Разработка алгоритмов оптимизации геометрической структуры сетки триангуляции на основе описанного выше критерия.
Объектом исследования являются модели сеток триангуляции. Предметом исследования является структура данных и геометрическая структура модели триангуляции.
Методы исследования. При выполнении работы использовались элементы теории графов, методы оптимизации, вычислительной геометрии, дискретной математики, теории вероятностей и математической статистики, теории баз данных.
Научная новизна работы состоит в следующем:
Впервые сформулирована постановка задачи поиска оптимальной ER-модели для произвольного количества сущностей по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов. К данной задаче сводится задача поиска оптимальной структуры данных модели триангуляции.
Разработана методика решения задачи поиска оптимальной ER-модели, включающая автоматизированный поиск на основе генетического алгоритма, позволяющего найти приближенное решение за приемлемое время.
3. Предложен критерий, позволяющей проводить оптимизацию интегральных свойств геометрической структуры триангуляционной сетки. На защиту выносятся:
постановка задачи поиска оптимальной ER-модели, к которой сводится задача оптимизации структуры данных модели триангуляции, по критериям требуемого для ее хранения объема памяти и скорости работы заданного набора алгоритмов, а также методика ее решения;
полученные структуры данных триангуляционной модели, оптимальные для использования с основными алгоритмами синтеза и анализа, используемыми в системах хранения и обработки пространственных данных;
критерий, позволяющий проводить оптимизацию интегральных свойств геометрической структуры сетки триангуляции и аспекты его применения.
Проведенные исследования соответствуют специальности 05.13.17 — «Теоретические основы информатики».
Практическая значимость состоит в возможности получения структуры данных модели триангуляции, оптимальной с точки зрения быстродействия алгоритмов анализа данных, и потребляемого объема памяти. Кроме того, описанная методика позволяет проводить оптимизацию при рефакторинге баз данных.
Использование разработанного критерия оптимальности сетки триангуляции позволяют улучшить качество результатов работы алгоритмов анализа данных в системах, использующих триангуляционную модель.
Результаты диссертационной работы внедрены в ООО «Центр менеджмента, оценки и консалтинга», а также Воронежском филиале ОАО «Туполев» - конструкторское бюро.
Апробация работы. Основные положения диссертационной работы были доложены на конференциях: «Информатика: проблемы, методология, технологии» (Воронеж, 2008), «Информатика: проблемы, методология, технологии» (Воронеж 2010), «Современные проблемы науки» (Тамбов, 2010), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов Воронежского государственного университета (Воронеж 2008-2011).
Публикации. Основное содержание диссертационной работы изложено в 10 работах, из них четыре статьи в журналах, реферируемых ВАК РФ.
Структура и объем работы.
Диссертация состоит из введения, четырех глав, заключения и списка литературы. Материал изложен на ПО страницах, содержит 40 рисунков и 8 таблиц. Список литературы из 76 источников.
