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

Приэтом границы расчётной области с заданной погрешностью совпадают сграницами построенных расчётных сеток.19Существуетмножествоалгоритмов,позволяющихпостроитьтриангуляцию Делоне как для набора точек [31], так и триангуляция сограничениями для произвольной односвязной расчётной области [28, 29].

Вслучае использования триангуляции для набора точек триангуляция впоследствии можно произвести процедуру восстановления границ [27] иполучить триангуляцию исходной расчётной области. В случае триангуляциис ограничениями в ряде случаев невозможно добиться выполнения условияДелоне без добавления дополнительных точек в триангуляцию [32]. В связи спроизвольностью добавления дополнительных точек итоговая триангуляцияможет обладать различными свойствами в зависимости от используемогоалгоритма добавления точек и преобразования триангуляции.Первый математически обоснованным алгоритмом для триангуляцииДелоне произвольного полигона был разработан в NASA Руппертом [37].

Вдальнейшем был предложен как ряд модификаций этого алгоритма, так иновые алгоритмы (например, 2-й алгоритм Chew [38-39]).Дляиспользованиятриангуляциивкачестверасчётнойсеткинеобходимо добавить дополнительные ограничения:- на минимальный угол элементов принадлежащих триангуляции;- на максимальный размер элементов;- на минимальный размер элементов.В данной главе рассматривается построение алгоритма триангуляциидля произвольной двумерной области, ограниченной кривыми Безье второгопорядка с вышеуказанными ограничениями, а так же обратный ему алгоритмуменьшения разрешающей способности сетки.202.1.Структуры данных для хранения триангуляцииНаиболее известные структуры данных для хранения триангуляциирассмотрены в работах А.В.

Скворцова [30-31]. В данной работе дляхранениятриангуляциииспользуетсяструктура«узлы,рёбраитреугольники» [30]. В этой структуре задаются все виды объектовтриангуляции: узлы, рёбра и треугольники. Узлы хранят указатели навходящие и исходящие рёбра, рёбра – указатели на начальный и конечныйузел и указатели на левую и правую ячейки, для ячейки хранятся указателина три образующих треугольник ребра.Задача построения триангуляции рассматривается в пространстве,представляющем из себя цилиндр   z , где  - двумерная расчётная областьс включенной границей, z – дополнительное измерение, позволяющееизменятьпространственноеразрешениетриангуляции.Вершинытриангуляции задаются за счёт координат x, y и параметра z>0, отвечающегоза локальные измельчения триангуляции.

В ряде случаев целесообразноразбить параметр z на две величины, отвечающие соответственно заадаптацию к геометрическим особенностям расчётной области и заадаптацию к параметрам течения. В этом пространстве вводятся операциидля определения геометрической и эффективной длины отрезка:- геометрическая длина отрезка, совпадающая с длиной вектора наплоскости: l geom ( pi , p j )  ( pix  p jx ) 2  ( piy  p jy ) 2 , i  j(2.2)- эффективная длина отрезка:l ( pi , p j ) piz  p jz2( pix  p jx ) 2  ( p jy  p jy ) 2 , i  j ,где pix , piy , piz - x, y и z координаты точки pi .21(2.3)2.2.Критерии качества сеткиКачествосеткиоказываетсильноевлияниенапогрешностьаппроксимации дифференциальных уравнений.

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

В данной работе качество сетки определяется по наборукритериев, используемых в работах Боровикова [27] и Shewchuk [29-30]:- отношение радиуса описанной окружности R к радиусу вписаннойокружности r:- значения минимального и максимального углов треугольника;- отношение радиуса описанной окружности к длине наименьшегоребратреугольника.Минимальноезначениедостигаетсядляравностороннего треугольника, для которого величина этого значениядостигает величины B  3 / 3 .Так же рассматривается критерии, оценивающие качество сетки вцелом.

Для такой оценки в качестве критериев используются:- значение минимального угла по всем ячейкам;- отношение максимального и минимального эффективных размероврёбер;22- отношение максимальной и минимальной площади треугольников,принадлежащих триангуляции.Ключевую роль в процессе построения сетки играет улучшениепараметров наихудшего элемента триангуляции, так как большая величинаошибки аппроксимации в худшей ячейке влияет на точность моделированиятечения во всей области.2.3.Аппроксимациякусочно-криволинейныхграницрасчётнойобласти кусочно-линейнымиДля проведения триангуляции расчётной области необходимо её задатькак односвязную замкнутую область. Данная область может быть заданаявно, как набор примитивов или неявно, как функция в пространстве R2,принимающая значение 1 внутри области, 0 на границе и -1 вне её.

В даннойработе используется явное задание геометрии в связи с простотойреализации, высокой скоростью работы и простотой проверки заданнойгеометрии на ошибки (не замкнутость, самопересечения, наличие излишнемелких деталей).Рассмотрим расчётную область, ограниченную замкнутой кривой,состоящей из квадратичных кривых Безье. Для построения расчётной сеткинеобходимо с заданной точностью аппроксимировать кривую Безье припомощи некоторого количества прямых отрезков.Уравнение квадратичной кривой Безье имеет вид:Bt   1  t  P0  2t 1  t P1  t 2 P2 , t  0,1.2(2.4)Данная кривая обладает следующими свойствами [35]: непрерывность заполнения сегмента между начальной и конечнойточками;23 кривая всегда располагается внутри фигуры, образованной линиями,соединяющими контрольные точки; прямая линия образуется при коллинеарном (на одной прямой)размещении управляющих точек; аффинныепреобразованиякривой(перенос,вращениеимасштабирование) может быть осуществлено путём применениясоответствующих трансформаций к опорным точкам.Кривая Безье, может быть аппроксимирована отрезком, соединяющимначальнуюиконечнуюточки.Верхняяграницаошибкитакойаппроксимации получается из свойства кривой Безье о расположении кривойвнутри фигуры, образованной линиями, соединяющих контрольные точки,как показано на рисунке 2.1.

Погрешность в таком случае получается какmax(abs(d1), abs(d2)).Рисунок 2.1 – Контроль точности аппроксимации кривой Безье отрезкамиДля уменьшения погрешности аппроксимации используется методПауля де Кастилии, позволяющий любую кривую Безье разбить на двекривых Безье того же порядка. Алгоритм построения этих кривыхпредставлен на рисунке 2.2.

Важным свойством такого разбиения являетсяуменьшение погрешности аппроксимации кривой при каждом разбиении.Таким образом, после некоторого количества делений заданной кривой Безьемы получаем набор кривых, при аппроксимации которых отрезкамипогрешность аппроксимации составит меньше заданной.24Рисунок 2.2 – Алгоритм Пауля де Кастилии разбиения кривой Безье на двекривых того же порядкаАлгоритм Пауля де Кастилии [35] (рисунок 2.2) применяется до техпор, пока погрешность аппроксимации границы отрезками, соединяющиминачальную и конечную точки кривых Безье, не станет меньше заданной.

Вдальнейшем, при необходимости разбиения на более мелкие части, каждая изновых кривых задаётся исходной кривой Безье и параметрическимизаданными на ней начальной и конечной точками.2.4.Алгоритм первоначальной триангуляции расчётной областиРассмотрим область, заданную кусочно-линейной внешней границей ивнутренними областями, также заданными кусочно-линейными границами.Преобразуем заданную границу расчётной области в односвязную.

Дляэтого найдём внешнюю границу области, т.е. границу, все точки которой непринадлежат внутренним областям:pi   j : pi   k  k , j  k .(2.5)Зададим внешнюю границу области в виде двухсвязного спискавершин так, чтобы вершины были заданы по часовой стрелке. Границывнутренних вырезаемых областей зададим в виде двухсвязного списка свершинами, следующими против часовой стрелки. Проверка направленияобхода контура осуществляется согласно следующему алгоритму:25- найдём нижнюю правую точку, принадлежащую кусочнолинейной границе расчётной области Г: p i  Г :p j  Г   p xj  p xi ; p yj  p iy.- построим векторы, соединяющие найденную нижнюю правуюточку контура Г со следующей точкой и с предыдущей точкой:r1 p xi  p xi 1p iy  p iy1; r2 p xi  p xi 1p iy  p iy1.- вычислим векторное произведение найденных векторов r1 и r2.Согласновыражениюдлямодулявекторногопроизведенияa, bsin      , свойствам функции sin(φ) и ограничениям, заданным наabугол φ, выбором точки p i , контур ориентирован по часовой стрелке,если sin(φ)>0, и против часовой стрелки, если sin(φ)<0.Алгоритм преобразования области в односвязную (рисунок 2.3):- найдём внутренний контур Гi, ближе всех расположенный квнешнему контуру Г0.