Диссертация (1149786), страница 6
Текст из файла (страница 6)
В первом варианте новая триангуляция будет содержать треугольникиp0 0 p0 000px +4,y +4 x ,yx +4,y(13), px0 ,y0 px0 +4,y0 +4 px0 ,y0 +4 а во втором варианте новые треугольники будут такими:p0 0px0 +4,y0 px0 ,y0 +4 x ,y. px0 ,y0 +4 px0 +4,y0 px0 +4,y0 +4 (14)29На рис. 2 показаны оба варианта укрупнения триангуляции. Кружками обозначены центральные узлы базовых элементов, принимающих ненулевые значенияна изображенных треугольниках.=⇒илиf1 или Tf2Рис. 2: Переход от T к Tf1 и Tf2 соответственно.Варианты укрупненной триангуляции обозначим TПри переходе к новой триангуляции будем сохранять нумерацию всех неудаляемых вершин. Старые и новые вершины обозначимdeft1 = te1 = px0 ,y0 ,deft4 = te4 = px0 ,y0 +2 ,deft7 = te7 = px0 ,y0 +4 ,deft10 = px0 +1,y0 +1 ,deft13 = px0 +3,y0 +3 .deft2 = te2 = px0 +2,y0 ,deft5 = te5 = px0 +2,y0 +2 ,deft8 = te8 = px0 +2,y0 +4 ,deft11 = px0 +3,y0 +1 ,deft3 = te3 = px0 +4,y0 ,deft6 = te6 = px0 +4,y0 +2 ,deft9 = te9 = px0 +4,y0 +4 ,deft12 = px0 +1,y0 +3 ,Новый базисный элемент будем обозначать ωej , а центральный узел этогоэлемента через tej .Для первого варианта укрупнения триангуляции, как указано в (13), треугольники, получающиеся в результате укрупнения, обозначимdef eT1 = te1 te3 te9 ,def eT2 = te1 te9 te7 .Заметим, что элемент ωej совпадает с ωj на всех треугольниках триангуляцииe 1 , кроме Te1 и Te 2.TЛемма 1.
Для базисных элементов укрупненной триангуляции ωe1 и ωe9 наe1 и Te 2 справедливы следующие калибровочные соотношения:треугольниках Tωe1 (t) = ω1 (t) + 3 · ω10 (t) − ω11 (t) − ω12 (t) − ω13 (t) / 8,(15)30ωe9 (t) = ω9 (t) + 3 · ω13 (t) − ω10 (t) − ω11 (t) − ω12 (t) / 8.(16)Доказательство. Элемент Зламала ωe1 в указанной области представляет собой фрагменты параболических цилиндров:e 1, (x − x0 − 2) · (x − x0 − 4) / 8, t ∈ Tωe1 (t) = (y − y 0 − 2) · (y − y 0 − 4) / 8, t ∈ Te 2.Аналогично, для элемента ωe9 имеем:e 1, (y − y 0 ) · (y − y 0 − 2) / 8, t ∈ Tωe9 (t) = (x − x0 ) · (x − x0 − 2) / 8, t ∈ Te 2.Раскладывая ωe1 и ωe9 по общей формуле (11), получаем необходимые соотношения.Лемма 2. Для базисных элементов укрупненной триангуляции ωe2 и ωe6 наe 1 имеют место следующие калибровочные соотношения:треугольнике Tωe2 (t) = ω2 (t) +1· ω11 (t),2(17)1· ω11 (t).(18)2Для элементов ωe4 и ωe8 аналогичные соотношения справедливы на треугольe 2:нике T1ωe4 (t) = ω4 (t) + · ω12 (t),(19)21(20)ωe8 (t) = ω8 (t) + · ω12 (t).2Доказательство.
Каждый из четырех рассматриваемых элементов Зламала на соответствующем треугольнике представляет собой седловую поверхность второго порядка:ωe6 (t) = ω6 (t) +e 1,ωe2 (t) = −(x − x0 − 4) · (x − x0 − y + y 0 ) / 4, t ∈ Tωe4 (t) =e 1,(y − y 0 − 4) · (x − x0 − y + y 0 ) / 4, t ∈ Tωe6 (t) =(y − y 0 ) · (x − x0 − y + y 0 ) / 4,e 2,t∈Tωe8 (t) = −(x − x0 ) · (x − x0 − y + y 0 ) / 4,e 2.t∈T31Разложим все четыре элемента по формуле (11) и получим искомые калибровочные соотношения.Лемма 3.
Базисные элементы укрупненной триангуляции ωe3 и ωe7 , опредеe1 и Te 2 соответственно, не меняются в процесселенные на треугольниках Tукрупнения. Поэтому калибровочные соотношения для них имеют вид:ωe3 (t) = ω3 (t),(21)ωe7 (t) = ω7 (t).(22)Доказательство. Оба элемента представляют собой параболические цилиндры:ωe3 (t) = (x − x0 − y + y 0 ) · (x − x0 − y + y 0 − 2) / 8,ωe7 (t) = (x − x0 − y + y 0 ) · (x − x0 − y + y 0 + 2) / 8.Раскладывая ωe3 и ωe7 по формуле (11), убеждаемся, что имеют место соотношения (21) и (22).Лемма 4. Для базисного элемента укрупненной триангуляции ωe5 , определенe1 и Te 2 , калибровочное соотношение имеет видного на обоих треугольниках Tωe5 (t) = ω5 (t) + 3 · ω10 (t) + ω11 (t) + ω12 (t) + 3 · ω13 (t) / 4.(23)e1 и Te 2 элемент Зламала ωДоказательство.
На каждом треугольнике Te5представляет собой седловую поверхность:e 1, −(y − y 0 ) · (x − x0 − 4) / 4, t ∈ Tωe5 (t) = −(x − x0 ) · (y − y 0 − 4) / 4, t ∈ Te 2.Раскладывая ωe5 по общей формуле (11), получаем требуемое калибровочноесоотношение (23).Результаты доказанных лемм объединяются следующим образом.Теорема 1.
Пусть триангуляция T была укрупнена первым способом, какf1 . Тогда матрица переходауказано в (13), так что новая триангуляция есть T32к укрупненной триангуляции есть123P1 T =456789123456781000000000100000000010000000001000000000100000000010000000001000000000109101112130 3/8 −1/8 −1/8 −1/800 1/20000000000 1/200 3/4 1/4 1/4 3/4 00 1/20000000000 1/201 −1/8 −1/8 −1/8 3/8Доказательство. Достаточно сослаться на результаты лемм 1, 2, 3 и 4.Собирая вместе коэффициенты из калибровочных соотношений (15)–(23), получаем матрицу P1 .Для второго способа разбиения, как указано в (14), справедлив аналогичный набор утверждений. Треугольники, получающиеся в результате такогоукрупнения обозначимdef eeeeT3 = t1 t3 t7 ,def eeeeT4 = t3 t9 t7 .Лемма 5.
Для базисных элементов укрупненной триангуляции ωe3 и ωe7 наe3 и Te 4 справедливы следующие калибровочные соотношения:треугольниках Tωe3 (t) = ω3 (t) + 3 · ω11 (t) − ω10 (t) − ω12 (t) − ω13 (t) / 8,(24)(25)ωe7 (t) = ω7 (t) + 3 · ω12 (t) − ω10 (t) − ω11 (t) − ω13 (t) / 8.Доказательство. Вполне аналогично доказательству леммы 1. ЭлементЗламала ωe3 в указанной области представляет собой фрагменты параболических цилиндров:e 3,(x − x0 ) · (x − x0 − 2) / 8, t ∈ Tωe3 (t) = (y − y 0 − 2) · (y − y 0 − 4) / 8, t ∈ Te 4.33Аналогично, для элемента ωe7 находимe 3,(y − y 0 ) · (y − y 0 − 2) / 8, t ∈ Tωe7 (t) = (x − x0 − 2) · (x − x0 − 4) / 8, t ∈ Te 4.Раскладывая выражения полученные для ωe3 и ωe7 по общей формуле (11), получаем необходимые соотношения.Лемма 6.
Для базисных элементов укрупненной триангуляции ωe2 и ωe4 наe 3 имеют место следующие калибровочные соотношения:треугольнике Tωe2 (t) = ω2 (t) +1· ω10 (t),2(26)1· ω10 (t).(27)2Для элементов ωe6 и ωe8 аналогичные соотношения справедливы на треугольe 4:нике T1ωe6 (t) = ω6 (t) + · ω13 (t),(28)21ωe8 (t) = ω8 (t) + · ω13 (t).(29)2ωe4 (t) = ω4 (t) +Доказательство.
Так же, как в лемме 2, каждый из четырех рассматриваемых элементов Зламала на соответствующем треугольнике представляетсобой седловую поверхность второго порядка:ωe2 (t) = −(x − x0 ) · (x − x0 + y − y 0 − 4) / 4,e 3,t∈Tωe4 (t) = −(y − y 0 ) · (x − x0 + y − y 0 − 4) / 4,e 3,t∈Te 4,ωe6 (t) = −(y − y 0 − 4) · (x − x0 + y − y 0 − 4) / 4, t ∈ Te 4.ωe8 (t) = −(x − x0 − 4) · (x − x0 + y − y 0 − 4) / 4, t ∈ TРазложим все четыре элемента по формуле (11) и получим искомые калибровочные соотношения.Лемма 7. Базисные элементы укрупненной триангуляции ωe1 и ωe9 , опредеe3 и Te 4 соответственно, не меняются в процесселенные на треугольниках T34укрупнения. Поэтому калибровочные соотношения для них имеют вид:ωe1 (t) = ω1 (t),(30)ωe9 (t) = ω9 (t).(31)Доказательство. Аналогично тому, как это было сделано в доказательстве леммы 3, оба элемента представляют собой параболические цилиндры:ωe1 (t) = (x − x0 + y − y 0 − 2) · (x − x0 + y − y 0 − 4) / 8,ωe9 (t) = (x − x0 + y − y 0 − 4) · (x − x0 + y − y 0 − 6) / 8.Раскладывая ωe1 и ωe9 по формуле (11), убеждаемся, что имеют место соотношения (30) и (31).Лемма 8.
Для базисного элемента укрупненной триангуляции ωe5 , определенe3 и Te 4 , калибровочное соотношение имеет видного на обоих треугольниках Tωe5 (t) = ω5 (t) + ω10 (t) + 3 · ω11 (t) + 3 · ω12 (t) + ω13 (t) / 4.(32)Доказательство. Рассуждая также, как при доказательстве леммы 4,e3 и Te 4 элемент Зламала ωвидим, что на каждом треугольнике Te5 представляетсобой седловую поверхность:e 3,(x − x0 ) · (y − y 0 ) / 4, t ∈ Tωe5 (t) = (x − x0 − 4) · (y − y 0 − 4) / 4, t ∈ Te 4.Раскладывая ωe5 по общей формуле (11), получаем требуемое калибровочноесоотношение (32).Результаты лемм (5–8) объединяются в следующее утверждение.Теорема 2.
Пусть триангуляция T была укрупнена вторым способом, какf2 . Тогда матрица переходауказано в (14), так что новая триангуляция есть T35к укрупненной триангуляции есть123P2 T =45678912345678100000000010000000001000000000100000000010000000001000000000100000000010910111213000000 1/20000 −1/8 3/8 −1/8 −1/8 0 1/20000 1/4 3/4 3/4 1/4 0000 1/2 0 −1/8 −1/8 3/8 −1/8 0000 1/2 10000Доказательство.
Вполне аналогично доказательству теоремы 1. Ссылаясь на результаты лемм 5, 6, 7, 8, и собирая вместе коэффициенты из калибровочных соотношений (24)–(32), получаем матрицу P2 .1.5Процедура мультишагового укрупнениятриангуляцииМожно заметить, что при соблюдении определенной процедуры выбора укрупняемых треугольников, получаемая в результате триангуляция допускает ещедальнейшее укрупнение.Так как мы имеем дело с триангуляцией задаваемой способом (Q), возможно определить правило выбора узлов, формирующих интересующее насмножество, основываясь на их декартовых координатах. В дальнейшем изложении, на приведенный ниже набор условий, будем ссылаться как на правило(R).Правило (R) Итак, узел t является отобранным по правилу в том случае,если его координаты удовлетворяют одному из двух условий: либо координатаx узла t кратна четырем, а координата y нечетная, либо наоборот, координатаx нечетной, а координата y кратна четырем.В качестве примера рассмотрим следующую таблицу инциденций, опре-36=⇒Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
