при исследовании взаимоотношения точек и базового отрезка возникают

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

Инкрементный алгоритм.

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

Схема алгоритма следующая:

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

2. Полученная триангуляция превращается в триангуляцию Делоне. Для этого:

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

• имеющих эту точку в качестве общей вершины;

• для каждого из треугольников гнезда (последовательным обхождением

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

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

Флипом называется операция переброски диагонали выпуклого четырехугольника, т.е. если у четырехугольника ABCD разбитого диагональю BD на два треугольника, удалить эту диагональ и заменить ее на AC, то получится другая триангуляция четырехугольника (рис.6-Д).

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

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

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

из трех точек;

для каждой комбинации находится описанная окружность и координаты

ее центра;

если внутри окружности текущей комбинации не находится ни одной

точки из оставшихся то эта комбинация есть треугольник – часть триангуляции Делоне.

К достоинствам этого алгоритма можно отнести:

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

замедляет процесс построений;

непосредственное построение триангуляции Делоне, без каких – либо

предварительных построений;

простота всех вычислений и преобразований;

в итоге триангуляционная сетка представлена множеством

треугольников, а не отдельных линий.

Заканчивая рассмотрение алгоритмов Делоне приведём названия наиболее используемых из них:

Radial sweep algorithm.

Recursive split algorithm (Алгоритм последовательного разбиения).

Divide-and-conquer algorithm (Алгоритм деления-и-включения).

Step-by-step algorithm.

Modified hierarchical algorithm (Модифицированный иерархический алгоритм)

Incremental algorithm.

Incremental delete-and-build algorithm.

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

На самом деле их значительно больше. Наиболее полный обзор алгоритмов триангуляции Делоне приведён в работе А.В. Скворцова. «Обзор алгоритмов построения триангуляции Делоне» в сборнике «Вычислительные методы и программирование», том. 3, 2002 год.

9.9. Алгоритм Рапперта и его модификации.

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

Этот алгоритм довольно новый, он был опубликован в 1994 году. Его разработал Джим Рапперт еще будучи студентом в рамках проекта, поддерживаемым NASA. Алгоритм адаптирован для метода конечных элементов и перечисленные выше требования, предъявляемые к конечно-элементным сеткам удовлетворяются автоматически. К его преимуществам можно отнести и то, что алгоритм легко параметризируется и управляется.

Если говорить точнее, этот алгоритм не является алгоритмом генерации, а лишь алгоритмом улучшения качеств сетки (refinement). В нашем случае входными данными для него будут являться геометрия конструкции в виде замкнутых полигонов и первичное разбиение конструкции на треугольники. В этом пункте, при описании алгоритма, будем считать, что первоначальное разбиение уже создано. Более подробно на генерации первоначального разбиения мы остановимся ниже (см. п. 5).

9.9.1.Терминология и алгоритм.

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

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

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

Сегмент (segment) — это отрезок, соединяющий две соседние точки лежащие на границе области разбиения, другими словами этот отрезок принадлежит контурам области.

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

Включенная точка (encroached point) — любая вершина текущей сетки, которая находится внутри окружности, радиусом которой является любой сегмент.

"Неправильный треугольник" (bad triangle) — это треугольник неудовлетворяющий глобальным условиям, которые накладываются на генерируемую сетку.

Вытянутый треугольник (skinny triangle) — треугольник, имеющий одну сторону, намного отличающуюся от других двух. То есть треугольник слишком вытянут вдоль некоторой прямой. На критериях "вытянутости" мы остановимся ниже.

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

a) разбиение неправильного треугольника с введением нового узла

При разбиении неправильного треугольника происходит следующее:

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

В эту точку добавляется новый узел.

Удаляется треугольник, подлежащий разбиению и прилегающие и добавляются новые, как показано на рисунке 7-Р.

b) разбиение сегмента, принадлежащего границе области разбиения с введением нового узла.

Вторая базовая процедура состоит в следующем:

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

Удаляется треугольник, которому принадлежал первоначальный сегмент и добавляются два новых треугольника (см. рис. 8-Р).

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

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

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

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

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

Производится поиск включенной (encroached) точки перебором всех точек и сегментов (только сегментов, но не граней).

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

Производится поиск треугольника с минимальным углом.

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

Производится поиск треугольника максимальной площадью.

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

Все условия удовлетворены. Конец работы алгоритма

Автор в своей работе приводит строгие математические доказательства, гарантирующие правильную работу алгоритма при минимальном угле α < 20°.

9.9.2. Модификация алгоритма Рапперта

В работе для Journal of Algorithms раскрыт только лишь чисто математический аспект проблемы, хотя вероятней всего алгоритм разрабатывался для решения прикладных задач и для генерации конечно-элементной сетки в том числе. К тому же, и математическая сторона была раскрыта не полностью, а только лишь с точки зрения сходимости и некоторых особенностей. Ряд самых неочевидных подводных камней не поднимается на обсуждение. Видимо это объясняется тем, что это проект NASA и, вероятно, имеет какую-то степень закрытости.

В том варианте, в котором он был предложен автором, алгоритм не обладал хорошей сходимостью и устойчивостью. Опытным путем было установлено, что углы α > 25° были недоступны для него. Для повышения качества работы алгоритма, помимо двух вышеперечисленных процедур была введена еще одна — процедура поворота диагонали. К сожалению, автор опустил этот момент и не упомянул о нем, несмотря на то что, ее роль в работе алгоритма очень высока. Эта процедура, на самом деле, неявно присутствует в оригинальном алгоритме Рапперта (см.рис. 7-Р, 8-Р), но все же эту процедуру лучше выделить в отдельную и остановиться на ней подробно. Это упрощает и понимание работы алгоритма, и его программирование. На рисунках видно, что помимо непосредственного добавления новых треугольников, производятся и еще некоторые операции. Эти операции есть ничто иное, как смена диагонали.

Суть ее заключается в следующем. Два треугольника, имеющие общую грань, образуют четырехугольник, разделенный диагональю. Внутри такого образования диагональ имеет два возможных положения. На рисунке 9-Р показаны эти положения — отрезки ac и bd.

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

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

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