Диссертация (1149346), страница 8
Текст из файла (страница 8)
Прификсированных (i, j) ∈ Z2 введем обозначенияdefo = r2i+1,2j+1 ,defz = r2i+2,2j+2 ,defx = r2i,2j ,defw = r2i+2,2j ,z 0 = r2i−2,2j−2 ,defy = r2i,2j+2 ,y 0 = r2i,2j−2 ,defo 0 = r2i+1,2j−1 .defdefПрямоугольник с вершинами x, y, z, w назовем исходным прямоугольником.В соответствии с рассматриваемым алгоритмом триангуляция исходного прямоугольника преобразуетсяx oy oz ox oследующим образомy z x y z ==>,x z www(14.1)а триангуляция симметричного относительно прямой xw прямоугольника преобразуется по правилуxo0y0y0 o0 z0z0 o0 wxo0 w==> x y0 z0 .0x z w (14.2)В дальнейшем рассматриваются также соответствующие преобразования прямоугольников, симметричных упомянутым относительно прямой yy 0 .ПрямоугольникиRi,j = {(x, y) | (2i − 2)h 0 ≤ x ≤ (2i + 2)h 0 ,def(2i − 2)h 00 ≤ y ≤ (2i + 2)h 00 },65рассматриваемые для всех (i, j) ∈ Z2 , заполняют всю плоскость.
Очевидно, что[Ri,j =Πi 0 ,j 0 .i 0 =i−1,i;j 0 =j−1,jДля (i, j) ∈ Z2 каждый прямоугольник Πi,j триангулирован согласно таблицеr2i,2j+2 r2i+1,2j+1 r2i,2jrr2i+2,2j r2i+1,2j+1 2i,2j∀(i, j) ∈ Z2 .(14.3), r2i+2,2j+2 r2i+2,2j r2i+1,2j+1 r2i+2,2j+2 r2i,2j+2 r2i+1,2j+1 Рассмотрим укрупнение вида (14.1) — (14.2) соответствующего подразделенияпрямоугольника Ri,j и покажем, что результат изоморфен подразделению (14.3);тем самым будет установлено, что структура локального укрупнения подразделения в подобласти совпадает со структурой исходного подразделения.
Будет показано, что в области, где произведено укрупнение, возможно использование предлагаемого алгоритма для дальнейшего локального укрупнения. Отсюда видно, чтоможно получить цепочку вложенных пространств с локальным укрупнением триангуляции и сгенерировать вэйвлетный пакет.Для удобства введем обозначенияa1 = r2i−2,2j−2 , a2 = r2i+2,2j−2 , a3 = r2i+2,2j+2 , a4 = r2i−2,2j+2 ,b1 = r2i,2j−2 , b2 = r2i+2,2j , b3 = r2i,2j+2 , b4 = r2i−2,2j ,c1 = r2i−1,2j−1 , c2 = r2i+1,2j−1 , c3 = r2i+1,2j+1 , c4 = r2i−1,2j+1 , o = r2i,2j .Рассмотрим преобразование, описываемое соотношениями (14.4) – (14.7) (см.дальше):a1 c1 b1b1 c1 ob4 c1 ob4 c1 a1==>66a b o 1 1, o a1 b4 (14.4)a2 c2 b1a2 c2 b2b2 c2 ob1 c2 oa3 c3 b3b3 c3 ob2 c3 ob2 c3 a3a4 c4 b4b4 c4 ob3 c4 ob3 c4 a4==>a b o 2 2, o b1 a2 (14.5)==>o b a 23 , a3 o b3 (14.6)==>a o b3 4 a4 o b4(14.7).Итак, в результате получаем триангуляцию a a a a a a a a T 1 1 2 2 3 3 4 4 b1 b4 b2 b1 b2 b3 b3 b4 .o o o o o o o o (14.8)Выделим фрагмент исходной триангуляции топологически изоморфный результату, полученному применением преобразования (14.4) — (14.7): b b b b b b b b T 1 4 2 1 3 2 4 3 c1 c1 c2 c2 c3 c3 c4 c4 .o o o o o o o o (14.9)Из формул (14.8) — (14.9) видно, что установлено следующее утверждение.Теорема 31: Исходное и укрупненное подразделения изоморфны; изоморфизм,сохраняющий величины углов треугольников, определяется отображениемo −→ o,ai −→ bi ,bi −→ ci+1 ,67i = 1, 2, 3,b4 −→ c1 .(14.10)Замечание 2: Другой изоморфизм, который, однако, не сохраняет величиныуглов, может быть задан соотношениямиo −→ o,ai −→ bi ,bi −→ ci ,i = 1, 2, 3, 4.ЗаключениеВ данной главе рассматрен вопрос построения адаптивных локально укрупняемых сеток узлов, ассоциированных с двумерной триангулированной плоскостью,а также выполнено построение пространств сплайн-всплесковых разложений, ассоциированных с этими сетками.
Выведены формулы реконструкции и декомпозиции, калибровочные соотношения. Рассмотрены вопросы построения сплайнвсплемковых разложений для частного случая курантовских аппроксимаций.68Глава 3Реализация алгоритма укрупнениятриангуляцииОбзор главыВ данной главе дано описание выполненной автором реализации алгоритма (ввиде комплекса компьютерных программ), предложенного в предыдущей главе.Приведены результаты тестирования программы на модельных примерах.3.1.ОбозначенияОпределение: триангуляция называется правильной, если никакая вершинане лежит внутри какого-либо ребра.В дальнейшем мы всегда будем подразумевать, что рассматриваемая триангуляция является правильной.Следует обратить внимание на то, что в общем случае триангуляция можетбыть и криволинейной. Подобные случаи могут возникать, например, при цифровом моделировании геологических или астрономических объектов.
Данный случайне будет рассматриваться здесь всвязи со сложностью задания входных данных.Тем не менее, рассматриваемый алгоритм допускает работу с криволинейнымитриангуляциями. Необходимым условием остается правильность обрабатываемойтриангуляции, а также ее изоморфизм той триангуляции, которая представленнойв этой работе.Задание триангуляции предлагается осуществлять с помощью двух таблиц: таблицы инциденций треугольник-вершина T , и соответствующей ей таблицы инци69денций вершина-координаты V .При наличии N вершин таблица V будет представлять собой матрицу размераN × 3. Каждую строку данной матрицы будем рассматривать как координатынекоторой точки v в трехмерном пространстве. Таблица V может содержать какцелые, так и вещественные числа.
Обозначим координаты точки через (x, y, z),при этом для определенности будем говорить, что x и y — координаты точкина двумерной плоскости, а z — значение аппроксимируемой функции в даннойточке. Порядковый номер строки назовем индексом вершины и обозначим черезvidx (vertex index). В дальнейшем мы будем работать не с самими вершинами (тоесть массивами векторов вида (xi , yi , zi )), а с их индексами. Это сделано для того,чтобы избавиться от необходимости работать с координатами узлов, которые, вобщем случае, могут быть не целыми числами, что привело бы к увеличениюобъема необходимых вычислений и снизило бы точность вычислений.Таблица вершин имеет следующий вид:vidxxyz0x0y0z01x1y1z1............,N − 2 xN −2 yN −2 zN −2N − 1 xN −1 yN −1 zN −1в данной таблице vidx — порядковый номер элемента (индекс вершины), а x, y иz — соответствующие координаты вершины.В качестве таблицы инциденций треугольников мы будем рассматривать списоквсех треугольников, заданных в триангуляции.
В предположении, что общее количество треугольников равно K, таблица инциденций T будет представлять собойматрицу размера K × 3, где i-я строка состоит из трех целых чисел (vi0 , vi1 , vi2 )— индексов вершин, составляющих вершины i-го треугольника. Номер строки вэтой таблице назовем индексом треугольника.Таблица T будет выглядеть следующим образом:70tidxv0v1v20v0,0y0,1z0,21v1,0y1,1z1,2............K − 2 xK−2,0 yK−2,1zK−2,2K − 1 xK−1,0 yK−1,1 zK−1,2 .При этом, в общем случае, порядок строк не играет роли и никак не отражаетвзаимное расположение треугольников на плоскости. Также не имеет значенияпорядок задания вершин.3.2.Изменение таблицы инциденцийНа плоскости R2 рассмотрим правильную (возможно, криволинейную) триангуляцию T0 , заданную на прямоугольной сетке узлов, которая характеризуетсяследующей таблицей инциденций:r2i,2j+2 r2i,2j rr2i+2,2j2i,2j r2i+2,2j+2 r2i+2,2j r2i+2,2j+2 r2i,2j+2r2i+1,2j+1r2i+1,2j+1r2i+1,2j+1r2i+1,2j+1∀(i, j) ∈ Z2 .Определение: Множество вершин, используемых в триангуляции, назовемее нульмерным остовом.Определение:Всякую прямолинейную триангуляцию, нульмерный остовкоторой содержится в множестве вида {(ih, jh)k(i, j) ∈ Z2 }, где h – некотороефиксированное число, назовем стандартной триангуляцией.Укрупнение триангуляции будем проводить объединением двух треугольниковисходной триангуляции, имеющих общее ребро.
Для этого предлагается заменитьдва треугольника исходной триангуляции треугольником, получающимся их объединением. Эквивалентное преобразование таблицы инциденций состоит в том,что из нее исключаются строки, соответствующие объединяемым треугольникам,и добавляются строки, соответствующие результату такого объединения – укруп71ненному треугольнику 1 . При этом необходимо выбирать пары объединяемых треугольников таким образом, чтобы результат их объединения также являлся треугольником. Порядок строк в таблице инциденций не играет роли, поэтому удаление и добавление строк можно осуществлять в любых местах таблицы;для заданияукрупнения достаточно перечислить выбрасываемые и добавляемые строки. Будем задавать преобразование таблицы инциденций указанием двух строк заменяемых треугольников (в левой от стрелки части формулы); например, отображениеx y z 0 0 0 → kx2 y2 z2 k x1 y1 z1 означает, что треугольники kx0 y0 z0 k и kx1 y1 z1 k заменяются треугольником kx2 y2 z2 k.3.3.Укрупнение триангуляцииРассмотрим следующие отображения:r2i+2,2jr2i+1,2j+1 r2i,2j r 2i+2,2j r2i+2,2j+2 r2i+1,2j+1lεij : r2i+2,2j+2 r2i,2j+2r2i+1,2j+1 r2i,2j+2 r2i,2jr2i+1,2j+1→ rr2i+2,2j r2i,2j+22i,2j r2i+2,2j+2 r2i+2,2j r2i,2j+2,∀(i, j) ∈ Z2 (i + j) mod 2 ≡ 0,иεrij : r2i+2,2jr 2i+2,2j+2 r2i,2j+2 r2i,2jr2i+2,2j+2 r2i+1,2j+1r2i,2j+2r2i+1,2j+1r2i,2jr2i+1,2j+1r2i+2,2jr2i+1,2j+1→r 2i,2j r2i+2,2j+2 r2i+2,2j r2i,2j r2i+2,2j+2 r2i,2j+2,∀(i, j) ∈ Z2 (i + j + 1) mod 2 ≡ 01 Следует отметить, что объединение двух треугольников не всегда является треугольником.
В общем случае необходимо проводить проверку того, что результат укрупнения также является треугольником. При проведении укрупнения построенным в даннойработе алгоритмом таких ситуаций не возникает, поэтому такая проверка не требуется.72Триангуляция T1 , полученная с помощью данного отображения, будет иметьследующий вид: rr2i+2,2j r2i,2j+22i,2j r2i+2,2j+2 r2i+2,2j r2i,2j+2r 2i,2j r2i+2,2j+2 r2i+2,2j r2i,2j r2i+2,2j+2 r2i,2j+2,,(i + j) ≡ 0 mod 2 ∀(i, j) ∈ Z2 ,(i + j + 1) ≡ 0 mod 2 ∀(i, j) ∈ Z2 .Замечание 1: Триангуляция T1 топологически изоморфна исходной триангуляции T0 .Замечание 2: Для стандартных триангуляций переход от триангуляции T0к триангуляции T1 может быть осуществлен поворотом плоскости на угол π4 и√масштабированием ее с коэффициентом 2 относительно начала координат.3.4.Алгоритм укрупнения в данной областиРассмотрим прямоугольную областьD = {(x, y),|x| ≤ M,|y| ≤ N },где M и N — натуральные числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
