Триангуляция Делоне - Курсовая работа

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Кафедра ЮНЕСКО по новым информационным технологиямВ повседневной жизни постоянно приходится сталкиваться с течениями жидкостей, большинство из которых имеет природное (волны в океанах, морские приливы, течение рек) или техногенное происхождение (волны, возникающие при движении морских судов, различные технологические процессы и устройства, использующие систему водоснабжения). В связи с этим существует высокая потребность в моделировании движения жидкостей с целью лучшего понимания сложных явлений, понижения стоимости затрат на разработку и повышения качества технологий. Фактически единственным эффективным способом решения сложных систем нелинейных дифференциальных уравнений гидродинамики являются численные методы, реализуемые на быстродействующих (вычислительных) машинах. В его работах приводятся идеи построения общей теории МКЭ, и последовательно излагается его применение в задачах теории упругости, вязко - упругости, пластичности, нелинейной упругости, устойчивости и колебания пластин и оболочек и т.д. В их книге «Метод конечных элементов в механике жидкости» [1] показана возможность использования метода в области гидромеханики, в частности при исследовании потенциальных течений и фильтрации вязкой жидкости сквозь пористую среду, для решения задач о циркуляционных течениях в прибережных зонах и др.Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Б.Н. Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками (Рисунок 1.). Задачей построения триангуляции по заданному набору двумерных точек называется задача соединения заданных точек непересекающимися отрезками так, чтобы образовалась триангуляция. Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции. Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне (Рисунок 2.).Для количественной оценки качества построенной триангуляции определим два типа критериев топологический и геометрически [7]. В идеальном случае точка имеет для двумерной области 6 соседей, для трехмерной 12 соседей.Рассмотрим алгоритм по шагам: Шаг 1. Сложность данного алгоритма складывается из трудоемкости поиска треугольника, в который на очередном шаге добавляется точка, трудоемкости построения новых треугольников, а также трудоемкости соответствующих перестроений структуры триангуляции в результате неудовлетворительных проверок пар соседних треугольников полученной триангуляции на выполнение условия Делоне. Рассмотрим алгоритм по шагам: Шаг 1. Либо, если точка не попадает внутрь триангуляции, находится треугольник на границе триангуляции, ближайший к очередной точке. Если точка попала на ранее вставленный узел триангуляции, то такая точка обычно отбрасывается, иначе точка вставляется в триангуляцию в виде нового узла.Триангуляция Делоне впервые появилась в научном мире как граф, двойственный диаграмме Вороного - одной из базовых структур вычислительной геометрии. Диаграмма Вороного конечного множества точек на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества , чем к любому другому элементу множества (Рисунок. Отметим простой факт: если для точки ближайшей является точка , то эта точка имеет "свое" ребро в ячейке . Однако каждое ребро принадлежит ровно двум ячейкам, поэтому будет просмотрено ровно два раза, и вследствие линейности числа ребер мы получаем решение данной задачи за . Действительно, в алгоритме Прима каждый раз ищется кратчайшее ребро между двумя множествами точек; если мы зафиксируем точку одного множества, то ближайшая к ней точка имеет ребро в ячейке Вороного, поэтому в триангуляции Делоне будет присутствовать ребро к ближайшей точке, что и требовалось доказать.Когда сходятся в одну точку два break point`а, то одна из «арок» (кусок одной из парабол) «схлопывается», т.е. две соседние к ней арки соединяются друг с другом. Таким образом, задача сводится к нахождению и обработке двух событий - добавления в список рассматриваемых центров новой точки (site event) и подозрение на наличие вершины (circle event). Эти события помещаются в список, который сортируется по убыванию координаты Y, т.е. события имеющие больше значения координаты Y размещаются выше в очереди и обрабатываются раньше.

Оглавление

Введение

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

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

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

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

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

6. Alpha shapes

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