Диссертация (Моделирование пространственных течений в газовых трактах с использованием адаптивных сеток), страница 5

Найдём наиболее близко расположенные точки pi и pj,принадлежащие контурам Гi и Г0 соответственно.- добавляем все точки контура Гi в контур Г0. При этом точки pi и pjбудут входить в список вершин по два раза, а последовательность вершинприобретает вид: ...; p i 1 ; p i ; p j ; p j 1 ;...; p j 1 ; p j ; p i ; p i 1 ;...Рисунок 2.3 - Преобразование заданной области в односвязную26Для построения первоначальной триангуляции используется алгоритмstep-by-step.

Основная идея заключается в следующем: контур задаётся какдвусвязный список точек (т.е. каждая точка знает о предыдущей и оследующей точке в цепочке). Произвольным образом строится первыйтреугольник(процедурарассмотренияданноготреугольникабудетрассмотрена далее). По построению одна грань нового треугольникапринадлежит контуру, а две оставшиеся – новые грани. Эти новые гранибудем называть «активными гранями». Далее, для каждой из активныхграней находим точку из контура, из которой она видна под максимальнымуглом и строим новый треугольник по активной грани и найденной точке.Для контура, состоящего из N точек затратность этого метода Nlog(N).Как видно, данный алгоритм легко распараллеливается.

Рассмотримраспараллеливание на примере построения первого треугольника (см.рисунок). Строим треугольник так, чтобы разделить первоначальный контурна две примерно одинаковые части. При его построении наш контур ABECDраспадается на два контура AB1C (активная грань B1D) и B2EC(активнаягрань B2C), для каждого из которых применяем алгоритм step-by-step. В ходеэтого алгоритма треугольники могут образовываться из активной грани иодной из соседних к ней граней (в этом случае просто происходитуменьшение точек в контуре), либо из активной грани с построением двухновых – в этом случае контур распадается на два независимых.27BAEDCB1B2A21DEC21Рисунок 2.4 - Алгоритм построения первоначальной триангуляцииТак же для построения первоначальной триангуляции используетсяалгоритм «ear clipping», описанный во многих источниках [31], [35].Полностью алгоритм триангуляции описан в [36].2.5.Элементарные операции над элементами неструктурированнойсеткиРассмотримнаборэлементарныхоперацийнадэлементамитриангуляции.Разбиение треугольникаРазбиение треугольника осуществляется добавлением нового узла.Существует два основных подхода для добавления новых узлов всуществующую триангуляцию: методы Бауэра-Уотсона и Лоусона [27].28При использовании метода Лоусона разбиение треугольника на трипроисходит вставкой новой вершины, лежащей внутри треугольника, споследующимсоединениемновойвершинысовсемивершинамитреугольника (рисунок 2.5).Рисунок 2.5 – Операция добавления узла в треугольную ячейку(МетодЛоусона)В методе Бауэра-Уотсона при добавлении нового узла средитреугольных ячеек, принадлежащих триангуляции, ищутся те, для которыхдобавляемая вершина принадлежит описанной окружности.

Из всехнайденных образуется выпуклый многоугольник, триангуляция которогоосуществляется объединением всех его вершин с добавляемой точкой. Приэтом построенная триангуляция удовлетворяет критерию Делоне. Реализацияданного подхода осложнена тем, что в связи с конечной вычислительнойточностью возможно возникновение ситуации, при которой будут найденыне все необходимые ячейки, в результате чего найденные ячейки не образуютодносвязную область [34].Существует несколько модификаций этогоподхода, призванных устранить этот недостаток. Одна из таких модификацийиспользуется в оригинальном алгоритме Рупперта [37], где происходитудаление самого треугольника и ближайших соседних треугольников, длякоторыхдобавляемыйузеллежитвнутриописаннойокружности,прилежащих к самому острому углу, а вставляемая вершина соединяется совсеми вершинами получившегося выпуклого многоугольника (рисунок 2.1.6).29Рисунок 2.6 – Операция добавления узла в триангуляцию (метод БауэраУотсона)В алгоритме Рупперта получается триангуляция с большимминимальным углом в треугольниках, однако метод Лоусона может бытьулучшен путём выполнения, для каждого из рёбер, образующих исходныйтреугольник, проверки возможность применения операции переворота ребра,описанной ниже.Выбор координат точки добавления новой вершины является довольносложной задачей.

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

Данная операция эффективна в том случае, если важноточное задание размера элементов, так как при данной операции на каждомшаге размер рёбер изменяется всего в два раза. Улучшение триангуляциидостигается последующей проверкой внешних рёбер, образующих исходныйчетырёхугольник, на возможность операции переворота ребра.Рисунок 2.7 – Добавление узла, лежащего вблизи существующего ребратриангуляцииОперация переворота ребраОперация переворота ребра (перестановки диагонали, edge flip)представляетсобойперестановкудиагоналивчетырёхугольнике,образованном двумя соседними ячейками. Операция возможна только длявыпуклого четырёхугольника.ДаннаяРисунок 2.8 – Операция переворота ребраоперация способна улучшить триангуляцию,еслиминимальный угол в образующихся треугольниках больше минимальногоугла в исходных.

При помощи рекурсивного запуска данной процедуры длявсех рёбер, принадлежащих триангуляции, и всех вновь образующихся рёберпроизвольная триангуляция преобразуется в триангуляцию Делоне.31Проверка выпуклости треугольника равнозначна проверке пересеченияего диагоналей. Данная проверка производится за счёт вычисления площадейобразующих треугольников, вычисленных с учётом знака:axsa, b, c   bxcxayazbybz .cycz(2.6)Диагонали пересекаются в случае:sa, b, c   0, sa, b, d   0, sa, b, c   sa, b, d   0, еслиsc, d , a   0, sc, d , b   0sc, d , a   sc, d , b   0max a x , bx   min c x , d x max c x , d x   min a x , bx  max a , b   min c , d yyyymax c y , d y   min a y , by (2.7)(2.8)Удаление ребраДанная операция удаляет ребро и обе соседние ячейки. Онаневозможна, если начальная и конечная точки ребра принадлежат границе.Также необходимо проверять образованные ячейки на самопересечение.Рисунок 2.9 – Операция удаление ребраУдаление узлов, в которых сходятся 4 ребраВ ряде случаев в ходе триангуляции образуются узлы, в которыхсходятся по четыре ребра.

Если треугольники, одной из вершин которыхявляется этот узел, имеют размер близкий к требуемому, качество32триангуляции можно повысить удалением этого узла и последующимразбиении полученного четырёхугольника на два путём проведениядиагонали.2.6.Рисунок 2.10 – Удаление узла, в котором сходятся четыре ребратриангуляцииАлгоритмы преобразования триангуляции для увеличенияразрешающей способности сеткиДанный алгоритм позволяет преобразовать заданную триангуляцию ктриангуляции с ограничениями на размер рёбер и на минимальный угол.Предлагаемый алгоритм основан на алгоритме Paul Chew [38]. Основнымиотличиями алгоритма являются изменение сортировки ячеек, позволяющееограничивать максимальный и минимальный размер ячеек, а так жеиспользование алгоритма Лоусона для уменьшения влияния ошибококругления [27].В качестве параметров данного алгоритма используются:Lmin - минимальная допустимая длина ребра в триангуляции;Lmax - максимально допустимая эффективная длина ребра в триангуляции; min - требуемый минимальный угол между рёбрами;N – число треугольников в триангуляции.Все треугольники, принадлежащие триангуляции, сортируются повеличине эффективного размера33leffgeom0, l max Lminl max , l max  Lmaxl , l / R  2 * sin( )min max min(2.9)гдеgeom- длина самого длинного ребра в треугольнике;l maxl max - эффективная длина самого длинного ребра в треугольнике;l min - эффективная длина самого короткого ребра в треугольнике;Ra bc4 p( p  a)( p  b)( p  c)- формула Герона для определения радиусаописанной вокруг треугольника окружности, гдеpabc- полупериметр.2Такимобразом,вотсортированномвидесначаланаходятсятреугольники, длина самого длинного ребра которых больше заданногомаксимального размера, но длина самого короткого ребра большеминимально допустимой длины.

Затемминимальныйуголмеждурёбрами-треугольники, у которыхменьшезаданногоминимальнодопустимого, но длина самого короткого ребра больше минимальнодопустимойдлины.Далее–треугольники,удовлетворяющиевсемпоставленным условиям. Поскольку нам необходим доступ только к первомуэлементу, отсортированные элементы можно хранить в виде дерева. Вданнойработеиспользовалосьстандартноекрасно-чёрноедерево,позволяющее выполнять операции добавления и удаления элементов сосложностью log(n).Алгоритм состоим из следующей последовательности действий(рисунок 2.1.10):341. Если число треугольников в триангуляции больше максимальнодопустимого – требуемая триангуляция построена.2. Берём первый треугольник из списка.3.