Речной гидродинамики

Модели мелкой воды в задачах речной гидродинамики

---

может производиться различными способами. При этом точность интер-
поляции зависит от качества триангуляции: показано, что ошибка при ли-
нейной интерполяции уменьшается при увеличении минимального угла. 
Среди множества триангуляций существует выделенная, обладающая ря-
дом минимаксных свойств. Это – триангуляция, при которой достигается 
максимум минимального угла по всем треугольникам, и она называется 
триангуляцией Делоне, которая также неоднозначна (достаточно рассмо-
треть прямоугольник, в котором для триангуляции может быть проведена 
как одна, так и другая диагональ). Неоднозначность приводит к структуре 
соседей, которая может резко меняться при малом изменении координат 
узлов и тем самым приводить к резким изменениям (негладкости) резуль-
татов интерполяции.
Другим важным случаем разбиения пространства является разбиение на 
ячейки Дирихле или выпуклые многогранники области Дирихле. Ячейка 
Дирихле для данной узловой точки 
x
0
– это объединение точек простран-
ства, расстояние от которых до 
x
0 
меньше, чем до остальных узлов. Среди 
многочисленных свойств этих ячеек особо следует отметить единствен-
ность разбиения и непрерывную зависимость всех геометрических параме-
тров ячеек от координат узловых точек. Конструктивный способ построе-
ния таких ячеек, хотя и медленный для практических приложений (с числом 
операций 
O
(
N
2
), где 
N –
общее число точек), следующий. Если соединить 
точку 
x
0 
отрезками со всеми точками x
k
и из середин каждого отрезка прове-
сти в обе стороны перпендикуляр (или перпендикулярную 
n
-плоскость), то 
получившийся выпуклый многоугольник (многогранник) является ячейкой 
Дирихле. Ячейки Дирихле разбивают все пространство на выпуклые мно-
гоугольники (многогранники), в каждом из которых находится только один 
из узлов системы точек. Разбиение на ячейки Дирихле однозначно строится 
по триангуляции Делоне. При этом справедливо, хотя и неоднозначно, и 
обратное утверждение.
Примеры генераций ячеек Дирихле приведены на Рис. 4.4.1. Крестиками 
отмечены узлы, линиями – границы ячеек и границы области. Для построе-
ния разбиения в этой работе использован метод, аналогичный методу Бауэ-
ра, с некоторыми частными модификациями работы. Во-первых, все точки 
были заключены в объемлющий симплекс, чтобы избежать неограничен-
ных ячеек Дирихле. Во-вторых, для ускорения геометрического перебора и 
поиска использовался быстрый алгоритм 4-дерева (quadtree) или 8-дерева в 
3-мерном случае. Число операций у такого алгоритма разбиения составляет 
O
(
N
lg 
N
), где 
N
– число узлов.
Построение ячеек Дирихле естественным образом приводит к определе-
нию соседей для точки 
x
0
. Это те узлы, принадлежащие ячейкам Дирихле, 
которые имеют общую грань с ячейкой вокруг 
x
0
. Такое определение сосе-
дей позволяет сформулировать метод интерполяции Сибсона [Sibson, 1980, 
1981], в виде (4.4.1).