Размещено на http://allbest.ru

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

КЕМЕРОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Математический факультет

Кафедра ЮНЕСКО по новым информационным технологиям

Курсовая работа

Триангуляция Делоне

студента 4 курса

Специальность

«Прикладная математика и информатика»

Научный руководитель:

Кемерово 2015



Оглавление

Введение

1. Общее описание

2. Критерии качества треугольных элементов

3. Алгоритмы построения триангуляции

4. Диаграмма Вороного

5. Алгоритм Sweep line

6. Alpha shapes

Список литературы



Введение

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

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

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

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

Среди наиболее известных можно выделить метод конечных элементов (МКЭ) [1].

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

Основоположником этого метода можно считать О. Зенкевича.

В его работах приводятся идеи построения общей теории МКЭ, и последовательно излагается его применение в задачах теории упругости, вязко - упругости, пластичности, нелинейной упругости, устойчивости и колебания пластин и оболочек и т.д.

Также большой вклад в развитие МКЭ внесли Дж. Коннор и К. Бреббиа. В их книге «Метод конечных элементов в механике жидкости» [1] показана возможность использования метода в области гидромеханики, в частности при исследовании потенциальных течений и фильтрации вязкой жидкости сквозь пористую среду, для решения задач о циркуляционных течениях в прибережных зонах и др.

Для расчёта задач с помощью МКЭ требуется разбить расчётную область на конечные элементы.

Чаще всего в плоском случае строятся треугольные элементы, а в пространстве - тетраэдры.

Подобная дискретизация называется триангуляцией Делоне.

Точность решения, полученная МКЭ, зависит от качества дискретизации расчетной области.

Очень долгое время распространению МКЭ мешало отсутствие алгоритмов автоматической генерации и разбиения области на «почти равносторонние» треугольники.

Цель: Реализовать комплекс программ для ЭВМ для эффективного построения триангуляции Делоне и улучшения полученной триангуляции методом Bubble mesh.

Задачи:

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

2. Реализация алгоритма Sweep line для автоматического построения триангуляции Делоне в виде программы для ЭВМ.

3. Реализация метода Bubble mesh для возможности улучшения расчетной сетки после автоматического построения триангуляции Делоне в виде программы для ЭВМ.

4. Провести тестирование программ на различных количествах расчётных узлов и сравнить результаты.

5. Составить расчетные сетки и провести на них расчет пробных функций методом МКЭ.

6. Провести анализ полученных результатов.

Постановка задачи: Пусть в области заданно расчетных узлов образующие множество точек , где - граничные точки , - внутренние точки .

Требуется построить триангуляцию Делоне по множеству точек и провести улучшение полученной сетки методом Bubble mesh для расчёта МКЭ.



1. Общее описание

Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Б.Н. Делоне [2]. Трудоёмкость этой задачи составляет . Существуют алгоритмы, достигающие этой оценки в среднем и худшем случаях. Кроме того, известны алгоритмы, позволяющие в ряде случаев достичь в среднем [3].

Введём несколько определений:

Определение 1. Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками (Рисунок 1.).

Рисунок 1. Пример триангуляции

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

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

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

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

Определение 6. Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне (Рисунок 2.).

Рисунок 2. Триангуляция Делоне

Определение 7. Говорят, что треугольник триангуляции удовлетворяет условию Делоне, если этому условию удовлетворяет триангуляция, составленная только из этого треугольника и трёх его соседей (если они существуют).

Многие алгоритмы построения триангуляции Делоне используют следующую теорему:

Теорема 1. Триангуляцию Делоне можно получить из любой другой триангуляции по той же системе точек, последовательно перестраивая пары соседних треугольников ДABC и ДBCD , не удовлетворяющих условию Делоне, в пары треугольников ДABD и ДACD (Рисунок 3.). Такая операция перестроения также часто называется флипом.

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

Рисунок 3. Перестроение треугольников, не удовлетворяющих условию Делоне

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

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

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

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

2. Критерии качества треугольных элементов

Для количественной оценки качества построенной триангуляции определим два типа критериев топологический и геометрически [7].

Топологический критерий основан на ближайших соседях точки из множества . В идеальном случае точка имеет для двумерной области 6 соседей, для трехмерной 12 соседей. Топологическую оценку получим с помощью формулы (1), где - общее количество точек в области, - степень или количество соседних точек с вязаных с внутренней точкой.

(1)

Геометрический критерий основан на разнице вписанной и описанной окружности вокруг расчетного треугольного элемента. Геометрическую оценку получим с помощью формулы (2), где - количество треугольников, - радиус вписанной окружности, - радиус описанной окружности.

(2)

3. Алгоритмы построения триангуляции

Для построения триангуляции существует большое количество алгоритмов. Они различаются между собой трудоёмкостью, сложностью реализации на ЭВМ, подходами к построению. Подробнее об алгоритмах можно узнать в книге А.В. Скворцова [3]. Рассмотрим некоторые алгоритмы.

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

Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков.

Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

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

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

Шаг 1. На первых трех исходных точках строим один треугольник.

Шаг 2. В цикле по для всех остальных точек выполняем шаги 3-5.

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

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

Шаг 5. Проводятся локальные проверки вновь полученных треугольников на соответствие условию Делоне и выполняются необходимые перестроения.

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

Цепной алгоритм один из первых эффективных алгоритмов построения триангуляции основан на процедуре регуляризации планарного графа и триангуляции монотонных многоугольников [5]. Трудоемкость этого алгоритма составляет , где - количество исходных отрезков. Рассмотрим алгоритм по шагам:

Шаг 1. Из множества исходных структурных отрезков формируем связанный планарный граф (Рисунок 4,а).

Шаг 2. Выполняется регуляризация графа, т.е. добавляются новые рёбра, не пересекающие другие, так что каждая вершина графа становится смежной хотя бы с одной вершиной выше неё и одной ниже. Регуляризация выполняется в два прохода с помощью вертикального плоского заметания [5]. В первом проходе снизу вверх последовательно находятся все вершины, из которых не выходят рёбра, ведущие вверх. Например, на (Рисунок 4,б) такой является вершина B. Проводя горизонтальную линию, обнаруживаем ближайшие пересекаемые ею слева и справа рёбра графа AD и EF. Затем в четырехугольнике DEHG находим самую низкую вершину и проводим в неё ребро из B. Аналогично выполняется второй проход сверху вниз (Рисунок 4,в). В результате работы этого шага каждая область планарного графа становится монотонным многоугольником.

Шаг 3. Каждую область графа необходимо разбить на треугольники. Для этого можно воспользоваться алгоритмом невыпуклого слияния двух триангуляций (Рисунок 4,г).

Рисунок 4. Схема работы цепного алгоритма триангуляции: а) - исходные отрезки; б - проход снизу вверх регуляризации графа; в) - проход сверху вниз; г) - триангуляция монотонных многоугольников

Для реализации цепного алгоритма лучше всего использовать структуры данных, в которых рёбра представляются в явном виде, например «Двойные рёбра» или «Узлы, рёбра и треугольники» [3].

Недостатком цепного алгоритма является то, что о форме получаемой триангуляции ничего заранее сказать нельзя. Это не оптимальная триангуляция, не жадная и не триангуляция Делоне с ограничениями. В цепном алгоритме могут получаться очень длинные вытянутые треугольники.

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

4. Диаграмма Вороного

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

Диаграмма Вороного конечного множества точек на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества , чем к любому другому элементу множества (Рисунок. 5,a) [5]. Совокупность многоугольников Вороного образует разбиение плоскости, представляющее векторную сеть.

Одним из главных свойств диаграммы Вороного является её двойственность триангуляции Делоне. А именно, соединив отрезками те исходные точки, чьи многоугольники Вороного соприкасаются хотя бы углами, мы получим триангуляцию Делоне (Рисунок. 5,б).

Диаграмма Вороного имеет много областей применения.

В качестве примера рассмотрим некоторые из них:

· Нахождение ближайшей точки для каждой. Отметим простой факт: если для точки ближайшей является точка , то эта точка имеет "своё" ребро в ячейке . Отсюда следует, что, чтобы найти для каждой точки ближайшую к ней, достаточно просмотреть рёбра её ячейки Вороного. Однако каждое ребро принадлежит ровно двум ячейкам, поэтому будет просмотрено ровно два раза, и вследствие линейности числа рёбер мы получаем решение данной задачи за .

· Нахождение выпуклой оболочки. Вспомним, что вершина принадлежит выпуклой оболочке тогда и только тогда, когда её ячейка Вороного бесконечна. Тогда найдём в диаграмме Вороного любое бесконечное ребро, и начнём двигаться в каком-либо фиксированном направлении (например, против часовой стрелки) по ячейке, содержащей это ребро, пока не дойдём до следующего бесконечного ребра. Тогда перейдём через это ребро в соседнюю ячейку и продолжим обход. В результате все просмотренные рёбра (кроме бесконечных) будут являться сторонами искомой выпуклой оболочки. Очевидно, время работы алгоритма .

· Нахождение Евклидова минимального остовного дерева. Требуется найти минимальное остовное дерево с вершинами в данных точках , соединяющее все эти точки. Если применять стандартные методы теории графов, то, т.к. граф в данном случае имеет рёбер, даже оптимальный алгоритм будет иметь не меньшую асимптотику. Рассмотрим граф, двойственный диаграмме Вороного, т.е. триангуляцию Делоне. Можно показать, что нахождение Евклидова минимального остова эквивалентно построению остова триангуляции Делоне. Действительно, в алгоритме Прима каждый раз ищется кратчайшее ребро между двумя множествами точек; если мы зафиксируем точку одного множества, то ближайшая к ней точка имеет ребро в ячейке Вороного, поэтому в триангуляции Делоне будет присутствовать ребро к ближайшей точке, что и требовалось доказать.

Триангуляция является планарным графом, т.е. имеет линейное число рёбер, поэтому к ней можно применить алгоритм Крускала и получить алгоритм с временем работы .

· Нахождение наибольшей пустой окружности. Требуется найти окружность наибольшего радиуса, не содержащую внутри никакую из точек (центр окружности должен лежать внутри выпуклой оболочки точек ). Заметим, что, т.к. функция наибольшего радиуса окружности в данной точке является строго монотонной внутри каждой ячейки Вороного, то она достигает своего максимума в одной из вершин диаграммы Вороного, либо в точке пересечения рёбер диаграммы и выпуклой оболочки (а число таких точек не более чем в два раза больше числа рёбер диаграммы). Таким образом, остаётся только перебрать указанные точки и для каждой найти ближайшую, т.е. решение за .

Рисунок 5. Диаграммы Вороного: а) - пример диаграммы; б) - двойственная диаграмме триангуляция Делоне

5. Алгоритм Sweep line

Алгоритм Sweep line был первоначально опубликован в 1986 году в работе «A sweepline algorithm for Voronoi diagrams» [6]. Данный алгоритм используется для автоматического построения диаграммы Вороного по конечному набору точек .

Алгоритм Sweep line основан на применении заметающей прямой. Заметающая прямая (ЗП) -- это вспомогательный объект, представляющий собой горизонтальную прямую линию. На каждом шаге алгоритма диаграмма Вороного построена для множества, состоящего из заметающей прямой и точек слева от неё. При этом граница между областью Вороного, прямой и областями точек состоит из отрезков парабол (3) (так как геометрическое место точек, равноудалённых от заданной точки и прямой -- это парабола). Прямая движется сверху вниз. Каждый раз, когда она проходит через очередную точку, эта точка добавляется к уже построенному участку диаграммы.

Если построить огибающую снизу всех парабол, то получится так называемая «береговая линия» (beach line). Эта кусочная кривая играет ключевую роль в алгоритме.

Точки пересечения «кусков парабол» (назовем их break point) лежат на границах полигонов диаграммы. Когда сходятся в одну точку два break point`а, то одна из «арок» (кусок одной из парабол) «схлопывается», т.е. две соседние к ней арки соединяются друг с другом. При этом образуется вершина полигона диаграммы.

Таким образом, задача сводится к нахождению и обработке двух событий -- добавления в список рассматриваемых центров новой точки (site event) и подозрение на наличие вершины (circle event).

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

(3)

где xf,yf- координаты фокуса параболы

L -- положение заметающей прямой

При программной реализации алгоритма используются следующие ключевые объекты: событие точки (site event) и событие круга (circle event).

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

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

· арка (часть параболы), этот узел должен хранить координаты фокуса параболы и ссылку на событие круга, если таковое имеется;

· break point, точка пересечения двух парабол;

· корень поддерева, его детьми являются узлы типа break point;

Главный цикл программы:

1. Инициализация данных;

2. Запускаем цикл до тех пор пока очередь не будет пуста (повтор 3-5);

3. Забираем из очереди первое событие (с наибольшим значением координаты Y);

4. Определяем какое это событие (site event или circle event);

5. Производим обработку события;

6. Финишировать все грани, ссылки на которые имеются в бинарном дереве;

Обработка «site event». Когда ЗП попадает на очередную точку, то в дерево добавляется новая парабола. Нужно заметить, что, изначально парабола представляет собой вертикально направленный луч. В месте пересечения этого луча с одной из парабол образуется сразу два break point`а.

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

Если арка содержит ссылку на существующее в очереди событие круга, то нужно удалить это событие из очереди и удалить ссылки на это событие из данной арки и ее соседей, арки справа и слева.

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

Если три фокуса не лежат на одной прямой, то можно построить общую для них окружность.

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

Обработка «circle event»: Каждое событие круга должно содержать ссылку на арку, которая будет удалена (схлопнется) при наступлении этого события. Для нахождения события круга рассматриваются тройки арок. В событии круга должна храниться ссылка на среднюю арку, т.е. на ту, у которой значение координаты X находится между соответствующими значениями двух других арок.

В этих соседних арках также должна храниться ссылка на то же событие круга, что и у средней. Обработка события круга будет заключаться в обновлении координат break point`ов, непосредственно ограничивающих удаляемую арку. Далее производится удаление арки и двух, связанных с ней break point`ов. После этого нужно перестроить дерево. В результате будет добавлен новый узел break point, а получившееся поддерево переместится на уровень выше.



6. Alpha shapes

Бывают случаи, что для расчётов требуются сетки с вырезами внутри или на границах, но при построении триангуляции все расчетные узлы соединяются ребрами (Рисунок 6). Для избежание подобных ситуаций требуется произвести очистку триангуляции, каким либо из алгоритмов.

Рисунок 6. Триангуляция Делоне с вырезом в центре: а) - Требуемая триангуляция;

б) - полученная после автоматического построения;

Алгоритм Alpha shapes позволяет провести очистку построенной триангуляции от лишних рёбер, что позволяет получить необходимую расчётную сетку. Данный алгоритм основывается на сравнении двух окружностей построенных из точек и , входящих в один треугольник, с радиусом , если две окружности пересекаются областями то между точками и остается ребро, в противном же случае ребро удаляется (Рисунок 7).

триангуляция геометрический гидродинамика



Рисунок 7. Ячейки диаграммы Вороного с построенной триангуляцией Делоне: а) ни одно ребро не удовлетворяет условию; б), в) - удалены некоторые ребра не удовлетворяющие условию; г) - все точки удовлетворяют условию;



Список литературы

1. Коннор, Дж. Метод конечных элементов в механике жидкости. Пер. с англ. / Дж. Коннор, Бреббиа К. - Л.: Судостроение, 1979. - 264с.

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

793-800.

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

4. Gilbert, P.N. New results on planar triangulations. Tech. Rep. ACT-15, Coord. Sci. Lab., University of Illinois at Urbana, July 1979.

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

6. Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313-322. 1986.

7. Shimada, K. Physically - Based Mesh Generation: Automated Triangulation of Surfaces and Volumes via Bubble Packing. [Текст]: дис.....канд. Doctor of Philosophy in Mechanical Engineering: защищена 14.05.93: утв. 10.07.93

Размещено на Allbest.ru

...