Введение. 
Триангуляция Делоне

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задачи:

• 1. Провести обзор существующих методов построения триангуляции Делоне и методов для улучшения качества полученной расчётной сетки.
• 2. Реализация алгоритма Sweep line для автоматического построения триангуляции Делоне в виде программы для ЭВМ.
• 3. Реализация метода Bubble mesh для возможности улучшения расчетной сетки после автоматического построения триангуляции Делоне в виде программы для ЭВМ.
• 4. Провести тестирование программ на различных количествах расчётных узлов и сравнить результаты.
• 5. Составить расчетные сетки и провести на них расчет пробных функций методом МКЭ.
• 6. Провести анализ полученных результатов.

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

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