close

Вход

Забыли?

вход по аккаунту

?

Измельчение триангуляции при помощи разбиения ребра.

код для вставкиСкачать
УДК 518
Вестник СПбГУ. Сер. 1, 2009, вып. 2
ИЗМЕЛЬЧЕНИЕ ТРИАНГУЛЯЦИИ
ПРИ ПОМОЩИ РАЗБИЕНИЯ РЕБРА∗
Н. А. Лебединская1 , Д. М. Лебединский2
1. С.-Петербургский государственный университет,
канд. физ.-мат. наук, доцент, dlebed@pdmi.ras.ru
2. С.-Петербургский государственный университет,
канд. физ.-мат. наук, доцент, dlebed@pdmi.ras.ru
При аппроксимации функций при помощи сплайнов желательно, чтобы последовательность используемых триангуляций обладала двумя свойствами: во-первых, внутренние углы треугольников должны быть отделены от 0, поскольку близкие к 0 углы
ухудшают аппроксимирующие свойства (нужно делить на sin этих углов), и во-вторых,
пространство аппроксимирующих функций по более мелкой триангуляции должно содержать пространство, соответствующее более крупной (наличие кратномасштабного
разложения позволяет сильно экономить время при вычислении коэффициентов разложения аппроксимации интересующей нас функции по базису пространства аппроксимирующих функций).
Вопрос о построении хорошей с точки зрения углов триангуляции рассматривался
в литературе как для двумерного, так и для трехмерного случая (см. [1]). Однако цель
этой работы — исправление имеющейся триангуляции: по исходной трехмерной триангуляции строится новая, углы которой лежат в определенном диапазоне; полученная
триангуляция не является измельчением старой.
Данная статья посвящена построению более мелкой плоской триангуляции при помощи элементарной операции разбиения ребра. Предложенный подход позволяет получить триангуляцию, с одной стороны, с углами, не более чем в 9 раз меньшими,
чем углы исходной триангуляции, и с другой стороны, с наличием кратномасштабного
разложения в тех случаях, когда используются пространства кусочно-полиномиальных
функций заданной степени с заданным уровнем гладкости, например, аппроксимации
Зламала (см. [2]) или Женишека. Вложенность пространств аппроксимирующих функций в данном случае обеспечивается тем фактом, что полученная в результате триангуляция является измельчением исходной.
1. Измельчение триангуляции. Лемма 1. Если есть треугольник, внутренние
углы которого лежат в интервале (ε, π − ε), то все внутренние углы треугольников,
на которые он делится медианой, лежат в интервале (ε′ , π − ε′ ) при ε′ = ε/3.
Доказательство. Пусть есть треугольник ABC, углы которого лежат в интервале
(ε, π − ε), и D — середина AB.
Докажем сначала, что угол ACD больше ε′ . Рассмотрим угол ACD как функцию
ϕ от углов BAC и ACB. Очевидно, что если один из этих углов фиксирован, ϕ как
функция от оставшегося угла возрастает. Это означает, что минимальное значение ϕ
достигается, если
√ углы BAC и ACB оба равны ε. В этом случае cos ∠ACD = f (cos ε),
где f (x) = 3x/ 8x2 + 1 — возрастающая при x > 0 функция. Из разложения cos в
ряд и теоремы Лейбница о сходимости знакочередующихся рядов имеем 1 − x2 /2 +
∗ Работа выполнена при финансовой поддержке РФФИ (гранты № 07-01-00451 и 07-01-00269).
c Н. А. Лебединская, Д. М. Лебединский, 2009
59
x4 /24 ≥ cos x ≥ 1 − x2 /2 при 0 ≤ x ≤ π/2. Нам нужно доказать ∠ACD ≥ ε/3, что
следует из cos ∠ACD ≤ cos(ε/3), что, в свою очередь, следует из f (1 − ε2 /2 + ε4 /24) ≤
1 − ε2 /18. Подставляя определение f , возводя в квадрат, домножая на знаменатель
(который положителен), перенося все в правую часть и приводя подобные члены, это
неравенство превращаем в
7
181ε2
677ε4
5ε6
ε8
4
0≤ε
−
+
−
+
,
12
648
15552 1944 23328
что верно для 0 ≤ ε ≤ π/2, поскольку первый положительный корень многочлена в
скобках больше 2. Для этих вычислений была использована система компьютерной
алгебры MuPAD 2.5.3 для Linux; выданный ею первый положительный корень многочлена в скобках примерно равен 2, 055 . . .
Аналогично, ∠BCD ≥ ε′ . Также ∠CDB ≥ ∠CAB ≥ ε ≥ ε′ как внешний угол
соответствующего треугольника, и, аналогично, ∠ADC ≥ ε′ .
Теперь нужно оценить эти углы сверху. Имеем ∠ACD ≤ ∠ACB ≤ π − ε ≤ π − ε′ и,
аналогично, для ∠BCD. Далее ∠BDC = π − ∠DCB − ∠ABC ≤ π − ε′ − ε ≤ π − ε′ и,
аналогично, для ∠ADC.
Лемма 2. Если есть треугольник, внутренние углы которого лежат в интервале (ε, π − ε), то все внутренние углы элементарных треугольников, на которые он
делится прямыми, параллельными одной фиксированной медиане и сторонам, лежат
в интервале (ε′ , π − ε′ ) при ε′ = ε/3.
Доказательство. Эта лемма является очевидным следствием предыдущей.
Пусть T — триангуляция; ее измельчение T ′ называется ε-измельчением, если все
внутренние углы треугольников T ′ лежат в интервале (ε, π − ε).
Под спариванием триангуляции понимается такое разбиение некоторых из входящих в ее состав треугольников на пары соседних по ребру, что каждый треугольник
может входить не более, чем в одну пару, и без пары могут остаться только треугольники, имеющие в качестве стороны ребро на границе области.
Триангуляция T называется спариваемой, если у нее существует спаривание.
Спариваемое измельчение T ′ триангуляции T называется слабым, если каждый треугольник исходной триангуляции может разделяться только на 2 части медианой либо
на 4 части медианой и двумя средними линиями, каждое граничное ребро исходной
триангуляции может разделяться не более, чем на две части (посредине), и существует спаривание, в котором все треугольники, имеющие в качестве стороны половину
граничного ребра исходной триангуляции, не остаются без пары.
Лемма 3. Начиная с любой триангуляции T , внутренние углы треугольников которой лежат в интервале (ε, π − ε), при помощи операции расщепления ребра можно
построить ее слабое спариваемое ε/3-измельчение T ′ .
Доказательство. Доказательство проводится индукцией по числу треугольников
в исходной триангуляции T . База индукции (1 треугольник) очевидна.
Пусть теперь T — триангуляция из n > 1 треугольников. Рассмотрим один из треугольников T , имеющий в качестве стороны граничное ребро. Удалим его мысленно из
триангуляции и оставшуюся триангуляцию обозначим P . Она содержит меньшее количество треугольников, и по индукционному предположению мы можем для P построить P ′ , удовлетворяющую утверждению леммы. Опишем теперь, как из P ′ получить T ′ .
Для этого обозначим вершины удаленного треугольника A, B, C и рассмотрим случаи.
1. Треугольник ABC имел в качестве сторон три граничных ребра — добавляем его
(без пары) в P ′ и получаем T ′ , выполнение утверждения леммы очевидно.
60
2. Треугольник ABC имел в качестве сторон два граничных ребра, пусть их общая
вершина будет A.
2.1. Ребро BC (являющееся граничным для P ) не разделяется в P ′ . Тогда возможны
два случая.
2.1.1. Треугольник, содержащий ребро BC в P ′ , имеет там пару. Тогда треугольник
ABC (без пары) добавляется к P ′ , и получается T ′ .
2.1.2. Треугольник S, содержащий ребро BC в P ′ , не имеет там пары. Тогда треугольник ABC добавляется к P ′ , и образует пару с S, и получается T ′ .
2.2 Ребро BC (являющееся граничным для P ) разделяется в P ′ . Тогда, если через
D обозначить середину BC, к P ′ добавляются треугольники ABD и ACD, образующие
пару между собой.
3. Треугольник ABC имел в качестве сторон одно граничное ребро, пусть это будет AB. Обозначим середины AB, AC, BC через X, Y , Z. Также треугольник из P ,
содержащий AC, обозначим S1 , а содержащий BC — через S2 .
3.1 Ни одно из ребер AC, BC не разделяется в P ′ .
3.1.1 Оба треугольника S1 и S2 имеют пары в P ′ . Тогда треугольник ABC (без пары)
добавляется к P ′ , и получается T ′ .
3.1.2 Ровно один из S1 и S2 имеет пару в P ′ , пусть это будет S1 . Тогда треугольник
ABC добавляется к P ′ и образует пару с S2 , и получается T ′ .
3.1.3 Оба треугольника S1 и S2 не имеют пары в P ′ . Тогда треугольник ABC разделяется на AXC и XBC, которые добавляются к P ′ , образуя пары с S1 и S2 .
3.2 Ровно одно из ребер AC, BC разделяется в P ′ , пусть это будет AC. Тогда треугольник ABC делится на ABY и Y BC, которые добавляются к P ′ . Образование пар
в этом случае зависит от того, имеет ли пару S2 .
3.2.1 Если S2 имеет пару, треугольники ABY и Y BC образуют пару между собой.
3.2.2 Если S2 не имеет пары, треугольник Y BC образует пару с S2 , а ABY остается
без пары.
3.3 Оба ребра AC, BC разделяются в P ′ . В этом случае треугольник ABC делится
на AXY , Y XC, CXZ и ZXB, которые и добавляются к P ′ , причем первые два и
последние два образуют пары между собой.
Теорема. Начиная с любой триангуляции T , внутренние углы треугольников которой лежат в интервале (ε, π − ε), при помощи операции расщепления ребра можно построить ее измельчение T ′ со сколь угодно малым максимальным диаметром
треугольника такое, что внутренние углы треугольников T ′ лежат в интервале
(ε′ , π − ε′ ) при ε′ = ε/9
Доказательство. Сначала по лемме 3 строим T ′′ — измельчение T , внутренние
углы треугольников в котором лежат в интервале (ε/3, π − ε/3) и треугольники которого можно разбить на пары соседних так, чтобы без пары могли остаться только
треугольники, имеющие в качестве стороны ребро на границе области.
Затем строим T ′ — требуемое измельчение T ′′ — следующим образом. В каждом треугольнике S триангуляции T ′′ вводим барицентрические координаты, причем первая из
них соответствует либо общей стороне треугольников пары, содержащей S, либо (если
треугольник без пары) одному из граничных ребер-сторон S.
Далее укажем порядок, в котором добавляются новые узлы (указываются барицентрические координаты нового узла; на какое ребро он добавляется, очевидно). Узел с
указанными барицентрическими координатами добавляется во все треугольники T ′′ .
61
Добавление узлов делится на циклы с номерами 1, 2, . . . Количество циклов определяется требованием достаточной малости максимального диаметра треугольника полученной триангуляции.
Первый цикл (n = 1) состоит в добавлении узла (0, 1/2, 1/2).
.
Последующие циклы (n > 1 — номер цикла) делятся на четные (n..2) и нечетные.
На четных циклах определим kn = 2n/2−1 . Добавляются узлы с барицентрическими
координатами
2kn − 2j + 1 i − 1 2j − i
,
,
2kn
2kn 2kn
и
2kn − 2j + 1 2j − i i − 1
,
,
2kn
2kn 2kn
при 1 ≤ i ≤ j ≤ kn .
На нечетных циклах определим kn = 2(n−1)/2−1 . Добавляются узлы с барицентрическими координатами
4kn − 4j − 2i + 4 2j + 2i − 3 2j − 1
,
,
4kn
4kn
4kn
и
4kn − 4j − 2i + 4 2j − 1 2j + 2i − 3
,
,
4kn
4kn
4kn
при 1 ≤ j ≤ kn , 1 ≤ i ≤ 2kn − 2j + 2.
Тот факт, что углы полученной в итоге триангуляции лежат в требуемом интервале,
обеспечивается леммой 2.
Литература
1. John Yung San Li. Nonobtuse meshes with guaranteed angle bounds, Master of Science
Thesis, Simon Fraser University, 2004.
2. Лебединская Н. А., Лебединский Д. М. Кратномасштабное разложение для аппроксимации Зламала // Вестн. С.-Петерб. ун-та. Сер. 1. Вып. 1. 2009. С. 18–22.
Статья поступила в редакцию 12 марта 2008 г.
62
Документ
Категория
Без категории
Просмотров
5
Размер файла
218 Кб
Теги
триангуляции, помощь, разбиение, ребра, измельчение
1/--страниц
Пожаловаться на содержимое документа