Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Министерство транспорта Российской Федерации

Федерального агентство железнодорожного транспорта

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Дальневосточный государственный университет путей сообщения»

Естественно - научный институт

Кафедра «Вычислительная техника и компьютерная графика»

К ЗАЩИТЕ ДОПУСТИТЬ

Заведующий кафедрой

­­­_______ Ю. В. Пономарчук

«___»_________20__г.

ТРИАНГУЛЯЦИЯ СО СГУЩЕНИЕМ ОБЛАСТЕЙ С ВХОДЯЩИМ УГЛОМ

Выпускная квалификационная работа

ВКР.09.03.01.ИВТ.04.00.943-ПЗ

Студент 943 гр. _________________________________ А.В. Егорчатов

Руководитель

д.ф.-м.н., профессор______________________________ В.А. Рукавишников

Нормоконтроль

к.т.н., доцент____________________________________ Е. В. Буняева

Х абаровск 2016

СОДЕРЖАНИЕ

Введение 3

1 Обзор предметной области 5

1.1 Основные понятия при использовании сеток 5

1.2 Триангуляция и существующие алгоритмы триангуляции Делоне 8

1.2.1 Итеративные алгоритмы построения триангуляции Делоне 12

1.2.2 Алгоритм слияния «Разделяй в властвуй» 16

1.2.3 Алгоритм прямого построения пошаговый алгоритм 18

1.2.4 Двухпроходные алгоритмы построения триангуляции
Делоне 20

2 Описание алгоритма двумерной триангуляции 25

2.1 Алгоритм расположения линий уровня 25

2.2 Алгоритм расположения узлов на линиях уровня 29

2.3 Алгоритм соединения узлов 30

3 Реализация алгоритма двумерной триангуляции 33

3.1 Описание используемых переменных 33

3.2 Реализация алгоритма расположения линий уровня 35

3.3 Вычисление значений углов 37

3.4 Реализация алгоритма соединения узлов 39

Заключение 41

Список использованных источников 42

Приложение А Реализация алгоритма плоской триангуляции 45

ВВЕДЕНИЕ

При решении современных научных и инженерных задач широко применяется математическое моделирование. Существуют готовые системы автоматизации инженерных расчетов (CAE – Computer-aided engineering) для анализа и моделирования физических процессов на ЭВМ. Большинство современных комплексов CAE состоит из набора необходимых библиотек, для графического интерфейса, визуализации, построения расчетных сеток, дискретизации дифференциальных уравнений и решения систем линейных и нелинейных уравнений. Соответственно, процесс моделирования физических процессов, как правило, сводится к трем основным операциям:

– построение расчетных сеток;

– дискретизация дифференциального уравнения;

– решение системы алгебраических уравнений.

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

Целью ВКР является написание программы, реализующей триангуляцию со сгущением исследуемой области с заданным углом. Программа будет реализована на языке С++. С++ считается языком программирования промежуточного уровня, т.е. он позволяет создавать как высокоуровневые приложения, так и низкоуровневые библиотеки, работающие с аппаратными средствами. С++ представляет собой оптимальную комбинацию, являясь языком высокого уровня, он позволяет любому создавать сложные приложения, сохраняя разработчику возможность обеспечить им максимальную производительность за счет подробного контроля над использованием ресурсов и их доступностью [1-9].

В качестве компилятора был выбран Qt. Qt – это полный инструментарий для программирования, который состоит из отдельных модулей, главным из которых является поддержка двух- и трехмерной графики, фактически являясь стандартом для платформонезависимого программирования на OpenGL [10-13]. Благодаря этому модулю, Qt является наиболее подходящей платформой для реализации поставленной задачи.

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

1 ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

1.1 Основные понятия при использовании сеток

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

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

Принято разделять сетки на регулярные [14, 15] (структурированные) (рисунок 1) и нерегулярные (неструктурированные) (рисунок 2).

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

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

– степенная сетка. Математически расположение линий уровня на такой сетке задается следующим образом:

,

где , .

Для данного примера , (рисунок 3);

Рисунок 3 – Степенная сетка

– геометрическая сетка. Принцип расположения линий уровня на такой сетке выглядит так:

,

где , , .

В приведенном ниже примере , (рисунок 4);

Рисунок 4 – Геометрическая сетка

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

,

где , , , .

В данном примере , (рисунок 5).

Рисунок 5 – Радикальная сетка

1.2 Триангуляция и существующие алгоритмы триангуляции Делоне

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

Рисунок 6 – Поверхность, заданная однозначной функцией

Рисунок 7 – Поверхность, заданная неоднозначной функцией

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

Рисунок 8 – Триангуляция на плоскости

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

В триангуляции можно выделить три вида объектов:

– узел (точка, вершина) (рисунок 9);

– ребро (отрезок) (рисунок 10);

– треугольник (рисунок 11).

Рисунок 9 – Узел	Рисунок 10 – Отрезок
Рисунок 11 – Треугольник

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов ВКР