автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Структурная оптимизация модели триангуляции на основе многокритериальных оценок

ШАЛИТКИН АНДРЕЙ ВЛАДИМИРОВИЧ

СТРУКТУРНАЯ ОПТИМИЗАЦИЯ МОДЕЛИ ТРИАНГУЛЯЦИИ НА ОСНОВЕ МНОГОКРИТЕРИАЛЬНЫХ ОЦЕНОК

Специальность 05.13.17. — «Теоретические основы информатики»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 2 МАЙ 2011

Воронеж 2011

4845422

Работа выполнена в ГОУ ВПО «Воронежский государственный университет»

Научный руководитель: кандидат физико-математических наук, доцент

Тюкачев Николай Аркадьевич

Официальные оппоненты: доктор технических наук, профессор

Рындин Александр Алексеевич

кандидат технических наук, доктор географических наук, профессор Умывакин Василий Митрофанович

Ведущая организация: ГОУ ВПО «Тамбовский государственный технический университет»

Защита диссертации состоится «¿5» ЛЩЛ 2011 года в часов на заседании диссертационного совета Д 212.038.24 при Воронежском государственном университете по адресу: 394006, Воронеж, Университетская пл., 1, ауд. 226

С диссертацией можно ознакомиться в библиотеке Воронежского государственного университета.

Автореферат разослан « » IV//?-¿//¿1 201 < г.

Ученый секретарь

диссертационного совета

А. С. Чеботарев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В ряде систем предъявляются жесткие требования к объему памяти, необходимой для хранения модели, быстроте выполнения алгоритмов, затратам на поддержку кода, то есть простоте программной реализации алгоритмов анализа данных и их точности. В работах Abdul-Rahman A., Jones С., Frank А., Скворцова А.В. приводится описание всего нескольких структур данных без численного обоснования их оптимальности. Описанные выше требования рассмотрены лишь в работах Тюкачева Н.А., однако подробно описан только двухмерный случай. Таким образом, хотя модель сильно влияет на почти все вышеперечисленные характеристики, на практике она чаще всего определяется интуитивно.

Триангуляционную модель данных можно представить в виде частного случая Entity-Relationship (ER) модели, структура которой определяется набором сущностей и связями между этими сущностями, что позволяет рассматривать задачу определения модели данных, удовлетворяющей указанным требованиям, в контексте любой системы, использующей ER-представление, например СУБД.

С геометрической точки зрения структура триангуляции имеет множество характеристик, таких как размер, форма, равномерность сетки. Эти характеристики непосредственно влияют на точность результатов выполнения алгоритмов анализа данных. Существуют различные алгоритмы триангуляции, описанные в работах Скворцова А.В., Роджерса Д., Dwyer R., Lewis В., Baker В., Bern М., Mitchell S., Chew L., Ruppert J. Эти алгоритмы позволяют получить сетку с треугольниками, удовлетворяющими некоторым требованиям: критерий Делоне, размеры углов, отношения сторон, сумма длин ребер и т. д., однако используемые критерии при этом чаще всего являются локальными и не учитывают всех необходимых характеристик.

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

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

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

Задачи исследования.

Для достижения поставленной цели необходимо выполнение следующих

задач:

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

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

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

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

5. Разработка алгоритмов оптимизации геометрической структуры сетки триангуляции на основе описанного выше критерия.

Объектом исследования являются модели сеток триангуляции. Предметом исследования является структура данных и геометрическая структура модели триангуляции.

Методы исследования. При выполнении работы использовались элементы теории графов, методы оптимизации, вычислительной геометрии, дискретной математики, теории вероятностей и математической статистики, теории баз данных.

Научная новизна работы состоит в следующем:

1. Впервые сформулирована постановка задачи поиска оптимальной ЕЯ-модели для произвольного количества сущностей по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов. К данной задаче сводится задача поиска оптимальной структуры данных модели триангуляции.

2. Разработана методика решения задачи поиска оптимальной ЕЯ-модели, включающая автоматизированный поиск на основе генетического алгоритма, позволяющего найти приближенное решение за приемлемое время.

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

На защиту выносятся:

• постановка задачи поиска оптимальной ЕЯ-модели, к которой сводится задача оптимизации структуры данных модели триангуляции, по критериям требуемого для ее хранения объема памяти и скорости работы заданного набора алгоритмов, а также методика ее решения;

• Полученные структуры данных триангуляционной модели, оптимальные для использования с основными алгоритмами синтеза и анализа, используемыми в системах хранения и обработки пространственных данных;

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

Проведенные исследования соответствуют специальности 05.13.17 — «Теоретические основы информатики».

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

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

Результаты диссертационной работы внедрены в ООО «Центр менеджмента, оценки и консалтинга», а также Воронежском филиале ОАО «Туполев» - конструкторское бюро.

Апробация работы. Основные положения диссертационной работы были доложены на конференциях: «Информатика: проблемы, методология, технологии» (Воронеж, 2008), «Информатика: проблемы, методология, технологии» (Воронеж 2010), «Современные проблемы науки» (Тамбов, 2010), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов Воронежского государственного университета (Воронеж 2008-2011).

Публикации. Основное содержание диссертационной работы изложено в 10 работах, из них четыре статьи в журналах, реферируемых ВАК РФ.

Структура и объем работы.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Материал изложен на 110 страницах, содержит 40 рисунков и 8 таблиц. Список литературы из 76 источников.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации, формулируются цели и задачи исследования, научная новизна и практическая значимость работы.

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

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

Во второй главе проведен анализ критериев оптимальности, необходимых для создания алгоритма автоматизированного поиска оптимальной структуры модели данных. Выводится интегральный критерий оптимальности сетки триангуляции.

Рассматриваются два критерия оптимальности модели данных: критерий мощности Р и критерий объема и. Первый показывает, насколько модель подходит для заданного набора алгоритмов в плане быстродействия этих алгоритмов. Второй критерий показывает, какой объем памяти необходимо затратить на хранение такой модели.

Модель данных для хранения пространственных данных может быть представлена как ЕЯ-модель. На рис. 1 показана такая ЕЯ-модель для трехмерного случая. Число связей на рисунке избыточно.

На практике используется подграф графа, изображенного на рис. 1.

Каждый алгоритм анализа данных выполняет определенный набор операций перехода между элементами модели данных, например, для СТГЫ модели это могут быть: определение инцидентных вершин, ребер, которым принадлежит точка, вершин треугольника и т. д. Для каждой такой операции ее быстродействие можно определить на основе длины пути по графу ЕЯ-модели от /-й вершины ву'-ю — Р„.

1

1 3 V

I1 •> 1 I N

(Точки) [»

Рис. 1. ЕЯ-модель для СТ1Ы с избыточным количеством связей

Такую операцию можно произвести, используя алгоритм Дейкстры поиска кратчайшего пути на графе с некоторыми изменениями:

• веса ребер и метки вершин не складываются, а умножаются;

• возможно движение против направления ребра в соответствии с формулой (1);

• если нужно найти путь от 1-й сущности к самой себе, то в случае, когда ребро (У) отсутствует, необходимо ввести виртуальную сущность, обладающую теми же свойствами (коэффициентом и связями), и в качестве результата взять путь до этой сущности.

Вес ребер при этом вычисляется по формуле: , существует ребро (У),

а к (1)

у , существует ребро (¡.¡), ребро (у) не существует,

где к[— возможное количество элементов типа ац— кратность ребра, связывающего ¡-ю и ^ю вершины. Коэффициенты к: и а:] считаются заданными и

для графа, показанного на рис. 1, вычисляются на основе следующего утверждения (доказательство показано в работах Тюкачева):

F = 2N-4, (2)

£ = ЗЛГ-6, (3)

где N— количество точек, Е — количество ребер и I7 — количество треугольников.

Результирующую формулу критерия мощности для заданного набора алгоритмов можно представить в виде сумм и произведений Я и к1.

Величина, определяющая критерий объема для хранения связи между сущностями /' и у, прямо пропорциональна количеству экземпляров г-й сущности и кратности соответствующего ребра:

М,/ (4)

Критерий объема для всей модели можно, соответственно, записать в следующем виде:

и= (5)

где Е - множество связей между сущностями.

Исходя из формул (3) и (4), можно заключить, что оба критерия можно будет записать в виде многочленов от одной переменной ТУ, что делает возможным использование аддитивной свертки. Таким образом, результирующая формула критерия оптимальности модели данных будет выглядеть следующим образом:

^ = + (6) где Л, и ¿2 — весовые коэффициенты, определяющие степень важности критериев, Я, + Л2 = 1.

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

1. Задан набор сущностей х1 е5,г' = 1,...,«. Каждая сущность ассоциируется с вершиной графа.

2. Для каждой сущности задано максимальное количество ее экземпляров к(х¡).

3. Для каждой сущности задан набор весов входящих ребер а' (*,-),у =1,...,и, определяющий количество экземпляров данной сущности, которое может быть связано с каждой сущностью, включая саму себя.

4. Функции к и а' можно записать в виде многочленов одной переменной Ы-

Оптимизируемой функцией является функция, заданная формулой (6).

С точки зрения оптимизации геометрической структуры триангуляционной сетки, необходимо определить требования, к ней предъявляемые:

1. Задана некоторая идеальная площадь треугольника. Площади всех треугольников должны к ней стремиться.

2. Форма всех треугольников должна быть как можно ближе к идеальной, то есть треугольник должен быть как можно ближе к равностороннему.

3. Сетка должна быть равномерной в смысле размера ячеек. Если сетка адаптивная, то равномерность должна быть обеспечена на близких участках.

В соответствие каждому требованию ставится критерий Ф*, где к — номер критерия, г — номер треугольника, Ф* — идеальное значение критерия и ф*

" — нормирующий коэффициент.

Для первого требования — квадрат площади треугольника, — величина, заданная во входных данных, Ф^.

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

Ф,2=(*,)2. (7)

где £,— расстояние между вершинами /-го треугольника, не принадлежащими совмещенной стороне.

Идеальная точка критерия Ф^, очевидно, равна 0, а в качества Ф2„ можно взять среднее значения длин сторон треугольников.

Для выражения последнего требования необходимо получить значение, которому равны площади максимального количества треугольников с точностью до заданной погрешности. Для этого строится ряд распределения площадей и выбирается значение с максимальным значением вероятности. Обозначим его как Бир,. Таким образом, для третьего критерия ф' — площадь треугольника, Ф3= ф] = Бор1.

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

й(Ф)=/7(Ф>;), с»)

где р — метрика в пространстве Л3.

Для одного треугольника формула будет следующей:

Ф3-Ф3 ,

ф „

где Я,, , Л3 — положительные коэффициенты, определяющие важность каждого из критериев, Л, + ^ +Л3 =1, Ф'п — коэффициент нормирования для каждого критерия.

Для вычисления интегрального критерия для всей сетки триангуляции применяется тот же тип свертки, но, в силу положительности всех элементов под корнем, корень отбрасывается.

В отдельных задачах некоторые критерии могут не учитываться, поэтому для вычисления каждого критерия для всей сетки, учитывая аддитивность формулы (11), удобно пользоваться следующей формулой:

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

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

(10)

(П)

<р = <р{Х), X = [ХиХ2,..,Хм], X= [х,у,г].

а) б)

Рис. 2. Техники оптимизации сетки: а) флип; б) сдвиг точек

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

Ф1 =S2=-{\ABXAC I)2.

(13)

а "(Я, -ЛЖ- -А) -{В; -Ау)

ЛВхАС= b = (В, -А-)(С, -Ах)- ~(ВХ -АЖ -4)

с (Вх -ау) ~(ву -АУ)(СХ -Ах)

(14)

Изменение координат одной точки влияет только на критерии оптимальности тех треугольников, вершиной которых она является, поэтому учитывая аддитивные свойства интегрального критерия оптимальности, получим:

д(р _ у дф\

(15)

где м — множество индексов треугольников, имеющих X, в числе своих вершин.

После подстановки в выражений (13) и (14), получим следующую дХ1

формулу:

д£=1 дХ, 2

~Ь(Сг-В:) + с{Ву~Су) а{Вг-С2) + с{Сх-Вх) а(С},-Ву) + Ь(Вх-Сх)

Для вычисления второго критерия, формула (15) будет так же верна. Таким образом, так как критерий является дифференцируемым, то, при использовании техники со сдвигом точек для оптимизации сетки, можно воспользоваться градиентным методом.

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

• множество конфигураций X, которое представляет собой область определения целевой функции;

• порождающее семейство, С(х,Т), которое на основе текущей конфигурации х е X и заданной «температуры » Т, возвращает новую конфигурацию х;

• задать закон убывания «температур » Т(к), где к— номер шага;

• функцию вероятности принятия решения И(АЕ,Т), определяющую вероятность перехода к новой конфигурации при текущем значении «температуры » Т и разности значений целевой функции при новой и текущей конфигурации АЕ.

Множеством конфигураций в данном случае является множество триан-гуляций, возможных на заданном наборе точек, х — конкретная триангуляция. Функция Б{х,Т) задается следующей последовательностью действий.

1. Выбрать некоторое подмножество ребер на основе равномерного закона распределения.

2. Отфильтровать те ребра, для которых флип невозможен.

3. Если подмножество стало пустым, повторить действия 1 и 2.

4. Применить операцию флипа к выбранному подмножеству.

После вычисления нового х'=С(х,Т) система переходит в это состояния с вероятностью Ь(АЕ,Т), где АЕ = /(х')-/(х). Вероятность задается в соответствии с распределением Гиббса:

1, АЕ < О,

Ь(А£,Г) = - _АЕ

е т , Д£>0.

Исходя из принципа работы алгоритма имитации отжига, начальная вероятность перехода должна быть достаточно велика, то есть как можно ближе к 1, что достигается соответствующим выбором начальной «температуры »:

Г(0) = *,/(*„), (18)

где К, — некоторая константа.

Для задания закона убывания температур использовалась формула из Больцмановского отжига:

1п(1 + к)

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

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

В диссертации разработана методика решения этой задачи, которая состоит описанной ниже последовательности шагов:

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

2. Анализ выбранного набора алгоритмов и построение для них формул мощности, описанным во второй главе способом.

3. Задание коэффициентов, определяющих вес критериев мощности и объема.

4. Автоматизированный поиск оптимальной модели.

Для реализации автоматизированного поиска оптимальной модели нужно перебрать все вариации ЕЯ-моделей с одним и тем же набором сущностей и определить наиболее подходящий набор связей. Общее число таких моделей 2"', где п — число сущностей. Так, уже для 5 сущностей решение задачи требует достаточно много времени (около суток на используемом оборудовании).

В диссертации предлагается реализации автоматизированного поиска на основе генетического алгоритма, для реализации которого необходимо определить следующее:

• целевую функцию;

• стратегию создания начальной популяции;

• стратегию скрещивания;

• стратегию мутации;

• размер популяции и количество итераций.

Оптимальные значения вышеописанных параметров определяются экспериментом и приводятся в описании четвертой главы.

В диссертации проанализированы алгоритмы синтеза и анализа сетки триангуляции. Был рассмотрен ряд алгоритмов триангуляции: фронтальный алгоритм, итеративный алгоритм, алгоритм слияний, пошаговый алгоритм; набор алгоритмов булевых операций: алгоритм Сазерленда - Ходжмана, алгоритм О'Рурка, алгоритмы Вейлера - Азертона, Леонова, Шутте, Маргалита - Кнотта, Линейно-Узловой алгоритм, триангуляционный и индексный алгоритмы. Для каждого алгоритма была выведена формула, отражающая мощность данного алгоритма. На рис. 3 показано соотношение между критериями оптимальности модели данных для некоторых алгоритмов обработки данных, для наглядности выбрано очень малое, по сравнению с реальных количеством точек триангуляции, значение и=10. Изображена нижняя граница областей.

80 ;................................................................................................................................................

1 1»-^--—-

0 ;------------------

О 10 20 50 40 50 60 70 £0

и

Рис. 3. Соотношение между критериями оптимальности модели, и — критерий объема, Р — критерий мощности

Сумма критериев мощности для некоторого набора алгоритмов является критерием мощности для системы, последовательно использующей алгоритмы из этого набора. Формула для системы, использующей проанализированные алгоритмы синтеза и анализа, будет выглядеть следующим образом:

Р ~ ■^0^02^01^10 + -^2^20 + К2Р22 + К2Р21+К2Рп + К{Рю + К2Р22.

Индексы имеют следующие значения: 0 — грани, 1 — ребра, 2 — точки, 3 — тела. Двойной индекс у обозначает операцию перехода по ЕЯ-модели от ¡-й сущности к _)'-й.

На рис. 4 представлена модель, полученная с помощью формулы (20).

Рис. 4. Оптимальная модель данных, Р=59>!, и=39Ы.

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

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

Архитектура основана на шаблоне проектирования МУС, что позволяет легко модифицировать приложение для изменения модели данных или добавления функциональности.

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

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

Таблица 1. Оптимальные параметры генетического алгоритма для задачи поиска оптимальной ЕЯ-модели, включающей пять сущностей

Параметр Значения

Размер пула 100

Размер элиты 30

Вероятность мутации элемента 0.1

Вероятность мутации гена 0.3

Селективная стратегия Турнирная

Полученные в диссертации результаты были использованы в ООО «Центр менеджмента, оценки и консалтинга» для вычисления оптимальной модели данных для ГИС «Автоматизированной системы массовой оценки недвижимости». Разработанный критерий оптимальности триангуляционной сетки применен в Воронежском филиале ОАО «Туполев» - конструкторское бюро в практике проектирования магистральных пассажирских самолетов при построении обводов фюзеляжа крыла оперения и иных агрегатов самолетов.

В заключении отражены основные результаты, полученные в данной работе:

Основные выводы и результаты исследования.

1. Задача оптимизации структуры данных модели триангуляции сведена к задаче поиска оптимальной ЕЯ-модели по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов.

2. Разработана методика решения описанной в предыдущем пункте задачи, включающая автоматизированный поиск оптимальной ЕЯ-модели на основе генетического алгоритма, применения которого позволяет решить поставленную задачу за приемлемое время. В силу общности самой задачи, методика может применяться не только для поиска оптимальной структуры данных модели триангуляции, но и для ряда других задач, в частности для оптимизации схем баз данных.

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК РФ:

1. Шалиткин А. В. Шаблон проектирования графического редактора / А. В. Шалиткин // Вестн. Воронеж, гос. ун-та. Сер. Системный анализ и информационные технологии. — 2010. — № 1. — С. 95-98.

2. Шалиткин А. В. Оптимальный выбор луча в задаче определения принадлежности точки многограннику / А. В. Шалиткин // Перспективы науки. — 2010. — № 7 (09). — С. 64-67.

3. Шалиткин А. В. Решение обобщенной задачи поиска оптимальной ЕЯ-модели на основе генетического алгоритма / А. В. Шалиткин, Н. А. Тюкачев, П. А. Цветков // Вестн. Воронеж, гос. техн. ун-та. — 2011. — Т. 7, № 3. — С. 204-207.

4. Шалиткин А. В. Применения алгоритма имитации отжига для оптимизации сетки триангуляции на основе интегральной оценки / А. В. Шалиткин, Н. А. Тюкачев // Вестн. Воронеж, гос. техн. ун-та. — 2011. — Т. 7, № 2. — С. 202-204.

Публикации в других изданиях:

5. Шалиткин А. В. Поиск оптимальной ЕЯ-модели для некоторых алгоритмов триангуляции / А. В. Шалиткин // Информатика : проблемы, методология, технологии : материалы X международной науч.-метод. конференции. / Воронеж, гос. ун-т. — Воронеж, 2010. — С. 339-342.

6. Шалиткин А. В. Практическое исследование интегральной оценки сетки триангуляции / А. В. Шалиткин // Исследование, разработка и

применение высоких технологий в промышленности : сб. трудов VII международной науч.-практ. конференции. / Воронеж, гос. техн. ун-т.

— Воронеж, 2009. — С. 150-152.

7. Шалиткин А. В. Схема данных конечно-элементной сетки / А. В. Шалиткин // Современные проблемы науки : материалы III международной науч.-практ. конференции. / Тамбов, гос. техн. ун-т. — Тамбов, 2010, —С. 35-39.

8. Шалиткин А. В. Триангуляция конечно-элементной сетки на основе оптимальных оценок / А. В. Шалиткин // Информатика: проблемы, методология, технологии : материалы X международной науч.-метод, конференции. / Воронеж, гос. ун-т. — Воронеж, 2010. — С. 335-338.

9. Шалиткин А. В. Триангуляция с вложенными многоугольниками / А. В. Шалиткин // Информатика: проблемы, методология, технологии : VIII международная науч.-метод, конференция. / Воронеж, гос. ун-т.

— Воронеж, 2008. — С. 361-364.

10. Шалиткин А. В. Интегральный критерий оптимальности конечно-элементной сетки. / А. В. Шалиткин // Вестн. Воронеж, гос. ун-та. Сер. Системный анализ и информационные технологии. — 2009. — № 1. — С. 28-30.

Подписано в печать 08.04.11. Формат 60*84 Усл. псч. л. I. Тираж 80 экз. Заказ 472.

Отпечатано с готового оригинал-макета в типографии Издательско-полиграф и чес кого центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Введение.

Глава 1. Обзор.

1.1. Модели представления пространственных данных.

1.2. Построение поверхностей.

1.3. Алгоритмы анализа данных.

1.4. Постановка задачи.

Глава 2. Критерии оптимальности.

2.1. Оптимальность Е11-модели.

2.2. Постановка обобщенной задачи поиска оптимальной модели.

2.3. Автоматизация процесса поиска оптимальной модели.

2.4. Интегральный критерий оптимальности сетки триангуляции

2.5. Выводы.

Глава 3. Анализ и построение алгоритмов.

3.1. Методика поиска оптимальной модели данных.

3.2. Исследование мощности алгоритмов синтеза.

3.3. Исследование мощности алгоритмов анализа.

3.4. Общий критерий оптимальности модели данных.

3.5. Оптимизация сетки на основе интегрального критерия.

3.6. Выводы.

Глава 4. Реализация и практическое исследование.

4.1. Шаблон графической системы.

4.2. Комплекс для тестирования алгоритмов оптимизации сетки.

4.3. Исследование интегрального критерия оптимальности сетки.

4.4. Детализация алгоритма оптимизации сетки триангуляции.

Триангуляционная?модель широко используется- в. различных системах работы с пространственными данными. Объекты описываются с помощью; поверхностей, которые, в свою очередь, являются'сетками триангуляции.

Детальное описание данной модели приводится в работах Abdul-Rahman А. [36], [37], Jones С. [52]. В работе Frank А. [50] показано представление структуры данных сетки триангуляции в виде ER-модели, в работе Worboys М. [74] освещаются аспекты применения ООП для хранения модели. В работе Скворцова A.B. [17] описано несколько наиболее часто используемых ER-моделей сетки триангуляции. В ряде работ Тюкачева H.A. [19], [20], [21], [23] описано применение триангуляционной модели в различных системах работы с трехмерными данными; В работе Тюкачева H.A. [22] впервые описаны критерии оптимальности модели данных двумерной триангуляционной сетки. В данной диссертации проведено более глубокое исследование критериев оптимальности модели данных, обобщение на произвольную ER-модель и разработана методика поиска оптимальной структуры ER-модели. Общая задача поиска оптимальной структуры ER-модели рассматривается в данной работе впервые.

Алгоритмы построения триангуляционной сетки с точки зрения геометрии рассмотрены в работах Роджерса Д. [14], Скворцова A.B. [17], [18], Ильмана В.М. [7], [8], Dwyer R. [50], Lewis В.[56]. Рассматриваемые в этих работах алгоритмы, как правило, позволяют строить сетку, удовлетворяющую критерию Делоне. В работах Baker В. [38], Bern М. [39], Mitchell S. [62], Chew L. [43], Ruppert J. [68] были предложены алгоритмы, позволяющие получать треугольники с дополнительными ограничениями, основанными на локальных критериях: отношение сторон треугольников, границы значений углов треугольников. В данной работе приводится описание интегрального критерия оптимизации сеткщ учитывающего несколько параметров оптимизации, а также алгоритмов постоптимизации сетки на его основе.

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

Триангуляционную модель данных можно представить в виде частного случая entity-relationship model (ER-модели), структура которой определяется набором сущностей и связями между этими сущностями, что позволяет рассматривать задачу определения модели данных, удовлетворяющей указанным требованиям, в контексте любой системы, использующей ER-представление, например СУБД.

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

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

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

Задачи исследования

Для достижения поставленной цели необходимо выполнение следующих задач:

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

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

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

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

5. Разработка алгоритмов оптимизации геометрической структуры сетки триангуляции на основе описанного выше критерия.

Объектом исследования являются модели сеток триангуляции. Предметом исследования являются структура данных и геометрическая структура модели триангуляции.

Методы исследования. При выполнении работы использовались элементы теории графов, оптимизации, вычислительной геометрии, теории вероятностей и математической статистики, теории баз данных, комбинаторики.

Научная новизна работы состоит в следующем:

1. Впервые сформулирована постановка задачи поиска оптимальной ЕИ-модели для произвольного количества сущностей по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов. К данной задаче сводится задача поиска оптимальной структуры данных модели триангуляции.

2. Разработана методика решения задачи поиска оптимальной ЕЯ-модели, включающая автоматизированный поиск на основе генетического алгоритма, позволяющего найти приближенное решение за приемлемое время.

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

На защиту выносятся:

• постановка задачи поиска оптимальной ЕЛ-модели, к которой сводится задача оптимизации структуры данных модели триангуляции, по критериям требуемого для ее хранения объема памяти и скорости работы заданного набора алгоритмов, а также методика ее решения;

• полученные структуры данных триангуляционной модели, оптимальные для использования с основными алгоритмами синтеза и анализа, используемыми в системах хранения и обработки пространственных данных;

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

Проведенные исследования соответствуют специальности 05.13.17 -«Теоретические основы информатики».

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

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

Результаты диссертационной работы внедрены в ООО «Центр менеджмента, оценки и консалтинга», а также воронежском филиале ОАО «Туполев» - конструкторское бюро.

Апробация работы. Основные положения диссертационной работы были доложены на конференциях: «Информатика: проблемы, методология, технологии» (Воронеж, 2008), «Информатика: проблемы, методология, технологии» (Воронеж, 2010), «Современные проблемы науки» (Тамбов, 2010), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов Воронежского государственного университета (Воронеж, 2008-2011).

Публикации. Основное содержание диссертационной работы изложено в 10 работах, из них 4 статьи в журналах, реферируемых ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Материал изложен на 110 страницах, содержит 40 рисунков и 8 таблиц. Список литературы из 76 источников. —

4.8. Выводы

В главе 4 описывается архитектура ПО, разработанного для проведения практических исследований, а также приводятся результаты этих исследований.

Так, для проверки алгоритмов оптимизации сетки был разработан комплекс приложений, позволяющий тестировать различные алгоритмы триангуляции, оптимизации и анализа для двумерного и трехмерного случаев. Кроме того, в силу частоты применения графических решений в ряде приложений, общая архитектура описана как шаблон проектирования. За основу взят МУС-шаблон, который обеспечивает «слабую связность» между элементами системы, что позволяет улучшить расширяемость системы, упростить поддержку кода.

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

Для автоматизации поиска оптимальной ЕК.-модели было реализовано

Заключение

В диссертации проведены исследования в соответствии с целью и поставленными задачами. Достигнуты следующие результаты, имеющие научное и практическое значение:

1. Задача оптимизации структуры данных модели триангуляции сведена к задаче поиска оптимальной ER-модели по критериям требуемого для ее хранения объема памяти и скорости выполнения заданного набора алгоритмов.

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

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

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

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

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

1. Азарнова T.B. Методы оптимизации: Элементы теории, алгоритмы и примеры / Т.В. Азарнова, И.Л. Кашира, Г.Д.' Чернышова. - Воронеж: Изд-во ВГУ, 2000. - 101 с.

2. Алейников С.М. Алгоритмы построения пространственных гранично-элементных сеток. / Алейников С.М., Бахтин A.A., Ткжачев H.A. // Мат. per. науч.-мет. конф. Информатика: проблемы, методология, технологии. Воронеж: ВГУ, 2004. - Вып. 4. - С. 48-52.

3. Грэй П. Логика, алгебра и базы данных / Пер. с англ. М.: Машиностроение. - 1989. - 359 с.

4. Делоне Б.Н. О пустоте сферы Текст. / Изв. АН СССР. ОМЕН, 1934.-№4.-С. 793-800.

5. Дубровин Б.А. Современная геометрия: методы и приложения Текст.: учеб. пособие для студ. физ.-мат. спец. ун-тов / Б.А. Дубровин, С.П. Новиков, А.Т. Фоменко. М.: Наука, 1979. - 759 с.

6. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек / Алгоритмы и программы, ВИЭМС. Вып. 10(88). -М.: 1985.-С. 3-35.

7. Ильман В.М. Экстремальные свойства триангуляции Делоне / Алгоритмы и программы, ВИЭМС. Вып. 10(88). М.: 1985. - С. 57-66.

8. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. СПб.: БХВ-Петербург, 2003. - 1104 с.

9. Коннолли Т. Базы данных проектироване реализация и сопровождение / Т. Коннолли, К. Бегг, А. Страчан. М.: Вильяме, 2001. -1120 с.

10. Ласло М. Вычислительная геометрия и компьютерная графика наS

11. С++ Текст. / Ласло М. М.: Изд-во «БИНОМ», 1997. - 304 с.

12. Лотов A.B., Поспелова И.И. многокритериальные задачи принятия решений: Учебное пособие. М:: Макс Пресс, 2008. - 197с.

13. Препарата Ф. Вычислительная геометрия: введение / Ф. Препарата, М. Шеймос. М.: Мир, 1989. - 478 с.

14. Численное моделирование. Фронтальные алгоритмы построения треугольной сетки. Электронный ресурс. // URL: http://ps300.narod.ru/fr3d/mesh.htm.(Дата обращения: 01.07.10.)

15. Роджерс, Д. Алгоритмические основы машинной графики Текст. / Пер. с англ. М.: Мир, 1989. - 512 с.

16. Скворцов A.B. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции / A.B. Скворцов. Томск: Изд-во Том. ун-та, 2002. - С. 116-123.

17. Скворцов A.B. Линейно-узловой алгоритм построения оверлеев двух полигонов // Вестник Томского гос. ун-та. 2002. - № 273. - С.99-103.

18. Скворцов A.B. Триангуляция Делоне и её применение / A.B. Скворцов. Томск: Изд-во Том. ун-та, 2002. - 128 с.

19. Скворцов A.B. Алгоритмы построения и анализа триангуляции. / Скворцов A.B., Мирза Н.С. Томск: Изд-во Томск, ун-та, 2006. - 168 с.

20. Тюкачев H.A. Автоматическое построение слоев геологического разреза. / Вестник ВГУ. Серия: Системный анализ и информационные технологии. 2006. - №1. - С. 141-144.

21. Тюкачев H.A. Определение принадлежности точки многоугольнику общего вида методом трассировки луча / Вестник ВГТУ. 2009. - № 4. - С. 94-98.

22. Тюкачев H.A. Оверлей многогранников / Вестник ВГТУ. 2009. - № 6.-С. 131-137.

23. Тюкачев H.A. Выбор ER-модели для описания поверхности трехмерных тел / Вестник ВГТУ. 2009. - № 4. - С. 14-24.

24. Тюкачев H.A. Разработка алгоритмов вычислительной геометрии и их реализация в трехмерной геоинформационной системе / Тюкачев H.A. -Воронеж: Изд. ВГТУ, 2009. 244 с.

25. Тюкачев H.A. Компьютерная графика и мультимедиа. / H.A. Тюкачев, И.В. Илларионов, В.Г. Хлебостроев// Воронеж: Изд. ВГТУ, 2008. -794 с.

26. Ченцов О.В. Обзор алгоритмов построения оверлеев многоугольников. / О.В. Ченцов, A.B. Скворцов // Вестник ТГУ. 2003. - № 280. - С. 338-345.

27. Шалиткин A.B. Интегральный критерий оптимальности конечно-элементной сетки. / Вестник ВГТУ. Серия: Системный анализ и информационные технологии. 2009. - С.28-30.

28. Шалиткин A.B. Оптимальный выбор луча в задаче определения принадлежности точки многограннику // Тамбов: Перспективы науки, 2010. - С.64-67.

29. Шалиткин A.B. Поиск оптимальной' ER-модели для некоторых алгоритмов триангуляции. / Информатика: проблемы, методология, технологии: материалы X международной науч.-метод. Конференции. // Вестник ВГТУ. 2010. - С. 339-342.

30. Шалиткин А.В. Шаблон проектирования графического редактора. / Вестник ВГТУ. Серия: Системный анализ и информационные технологии. -2010.-С. 95-98.

31. Шалиткин А. В. Решение обобщенной задачи поиска оптимальной ER-модели на основе генетического алгоритма / А.В. Шалиткин, Н.А. Тюкачев, П.А. Цветков // Вестник ВГТУ. 2011. - С. 204-207

32. Шалиткин А.В. Применения алгоритма имитации отжига для оптимизации сетки триангуляции на основе интегральной оценки / А.В. Шалиткин, Н.А. Тюкачев // Вестник ВГТУ. 2011. - С. 202-204.

33. A. Abdul-Rahman Spatial Data Modeling for 3D GIS. / A.Abdul-Rahman, M.Pilouk Berlin: Springer, 2008. - 290 p.

34. A. Abdul-Rahman. Triangular irregular network in digital terrain relief modelling. // M. Sc. Thesis, ITC, Enschede, The Netherlands. 1992. - 80 p.

35. B. Baker Nonobtuse triangulation of polygons. / B. Baker, E. Grosse,

36. C.S. Rafferty. // Disc. And Comput. Geom. 1988. - № 3. - 168 p.

37. Bern M. Mesh generation and optimal 'triangulation. / Bern M., Eppstein

38. D. // World Scientific. 1992. - P. 23-90.

39. Bric, V. 3D vector data structures and modelling of simple objects in GIS. / M. Sc. Thesis, ITC, Enschede, The Netherland. 1993. - 107 p.

40. Censor, Y. "Pareto Optimality in Multiobjective Problems " Appl. Math. Optimiz. 1977. - Vol. 4. - P. 41-59.

41. P. Chen Entity-Relationship Approach to Information. Modeling and Analysis / Proceedings of the Second International Conference on the Entity-Relationship Approach. North-Holland. -1983. - P. 19-28.

42. L. Chew. Guaranteed-quality triangular meshes. / Technical Report TR89983. Cornell University, Computer Science Department, 1989.

43. Dereli T. A hybrid simulated annealing algorithm for 2D packing problems. / Dereli Т., Da§ G.S. // Proceedings of 5th International Symposium on Intelligent Manufacturing Systems. -2006. P. 959-966.

44. Dong F. Three-dimensional models and applications in subsurface modeling. / Department of Geomatics Engineering Reports No. 20093. -University of Calgary, 1996. 93 p.

45. Dowsland K.A. Some experiments with simulated annealing techniques for packing problems. / European Journal of Operational Research. 1993. - Vol. 68.-P. 389-399.

46. Dwyer R.A. A fast divide-and-conquer algorithm for constructing Delaunay triangulations. / Algorithmica 1987. - Vol. 2. - p. 137-151.

47. Gamma E. Design Patterns: Elements of Reusable Object-Oriented Software. / E.Gamma, R. Helm, R. Johnson, and J. Vlissides.// Boston: Addison Wesley Professional, 1994. - 395 p.

48. Evans F. Optimizing triangle strips for fast rendering. / Evans F., Skiena S., Varshney A. // Proc. IEEE Visualization. 1996. - P. 319-326.

49. Frank A.U. Cell graphs: a provable correct method for the storage of geometry. / Frank A.U., Kuhn W. // Proc. of the Second International Symposium on Spatial Data Handling. 1986. - P. 411-436.

50. GRAPP электронный толковый словарь по теории графов и ее применению в информатике. Электронный ресурс. // - URL: http://pco.iis.nsk.su/grapp. (Дата обращения: 05.09.2009)

51. Jones С.В. Data structures for three-dimensional spatial information systems in geology. / International Journal of Geographical Information Systems. -1989.-Vol.3.-P. 15-31.

52. Kampke T. Simulated, annealing: Use of a new tool in bin-packing. / Journal Annals of Operational Research. 1988. - Vol. 16. - P. 327-332:

53. Kirkpatrick S. Optimization by simulated annealing./ Kirkpatrick S., Gelatt C.D., VecchiM.P. // Science. 1983. - Vol. 220, No. 4598. - P. 671-680.

54. Lai K.K. Developing a simulated; annealing algorithm for the cutting stock problem. / Lai K.K., Chan, J.W.M. // Computers & Industrial Engineering. -1997.-Vol. 32.-P. 115-127

55. Lewis B.A. Triangulation of planar regions with applications. / Lewis B.A., Robinson J.S. // Computer Journal. 1978. - Vol; 21 - P. 324-332.

56. Maguire D.J. Functionality of GISs. / Maguire D.J., Dangermond J. // Geographical Information Systems. 1991. - Vol. 1. - P. 319-335.

57. Margalit A. An algorithm for computing the union, intersection or difference of two polygons / Margalit A., Knott G.D. // Computers & Graphics. -1989.-Vol.13.-P. 167-183.

58. Melanie M. An Introduction to Genetic Algorithms. / Cambridge: "A Bradford Book" The MIT Press, 1999. - 158p.

59. Midtb®, T. Spatial modelling by Delaunay networks of two and three dimensions: Thesis . Dr. Ing. Science / Midtb0, T. Norway: Norwegian Institute of Technology, University of Tronheim, 1993. - 147 p.

60. Mirante A. The radial sweep algorithm for constructing trianguled irregular networks. / Mirante A., Weingarten N. // IEEE Computer Graphics and Applications. 1982. - Vol. 2. - P. 11-21.

61. Mitchell S.S. Quality mesh generation in three dimensions. / Mitchell S.S and Vavasis S.A. // In Proceedings of the Eighth Annual Symposium on Computational Geometry. 1992. - P. 93-111

62. Pilouk M. Integrated Modelling for 3D GIS: Thesis . Dr. Physics Science / Pilouk M. ITC Publication, 1996: - No. 40. - 200 p.

63. Puppo E. Variable resolution triangulations / Computational Geometry Theory and Applications 1998. - Vol 11. - P. 219-238.

64. Raper J. The 3-dimensional geoscientific mapping and modelling' system: a conceptual design. / In: Raper, J (Ed.) London: Taylor & Francis, 1989.-P. 11-20.

65. Raper J. Three-dimensional GIS. / Raper. J. and Kelk. B. // In: Geographical information systems: principles and applications. D J. Maguire; M. Goodchild and D.W. Rhind (eds.) London: Longman, 1991. - P. 299-317

66. Rothlauf F. Representations for Geneticand Evolutionary Algorithms. // Berlin: Springer, 2006. - 325 p.

67. Ruppert J. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. / Submission to Journal of Algorithms. 1994. - Vol. 18. - P. 548-585.

68. Sloan S.W. A fast algorithm for constructing Delaunay triangulations in the plane. / Advanced Engineering Software 1987. - Vol 9. - P. 34-55.

69. Sutherland I.E. Reentrant polygon clipping / Sutherland I.E., Hodgman

70. G.W. // CACM. 1983. - Vol 26. - P. 868-877.

71. Watson D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. / Computer Journal. 1981'. - Vol 24. - P. 167172.

72. Weiler K. Polygon comparison using graph representation / Computer Graphics. 1980. - Vol 14. - P. 10-18.

73. Weiler K. Hidden surface removing using polygon area sorting / Weiler K., Atherton P. // Computer Graphics. 1977. - Vol 10. - P. 214-222.

74. Worboys M.F. Object-oriented data modelling for spatial databases. / Worboys M.F., Hearnshaw H.M., Maguire D.J. // International Journal of Geographical Information Systems. London: Taylor & Francis, 1990. - Vol. 4. -P. 369-383.

75. Youngman C. Spatial data structures for modeling subsurface features. / In: Raper, JF (Ed.). Three Dimensional Applications in Geographic Information Systems. London: Taylor & Francis, 1989. - P. 129-136.

76. Zadeh L.A., "Optimality and Nonscalar-valued Performance Criteria," // IEEE Trans. Automat. Contr. 1963. - Vol 8. - P. 1.