Отправной точкой всех алгоритмов этого класса является некая
триангуляция границы заданной области, причем не грубая, а наибо-
лее полно соответствующая требованиям задачи, поскольку в даль-
нейшем никаких изменений этой триангуляции не будет. Отметим,
что подобное требование к начальным данным может быть как по-
ложительной стороной метода, так и отрицательной. Если никаких
ограничений на границу области не накладывается, то это приводит
к необходимости ее отдельной триангуляции, что само по себе явля-
ется самостоятельной задачей. С другой стороны, если необходимо
обеспечить согласование триангуляции в сложной области, либо же
триангуляция поверхности задана изначально, то использование мето-
да исчерпывания будет самым удачным выбором. (В двумерном случае
под триангуляцией границы будем понимать разбиение линии границы
на отрезки необходимой длины.)
Триангуляция границы является тем самым фронтом, упоминае-
мым в английском названии. Например, в трехмерном случае, исполь-
зуя какой-либо треугольник из фронта, можно на его основе построить
тетраэдр, причем четвертой вершиной тетраэдра может быть либо дру-
гая вершина фронта, либо дополнительный узел, помещаемый внутрь
заданной области. При изъятии полученного тетраэдра из фронта мо-
жет быть удалено от одной (случай вставки дополнительного узла) до
четырех граней и одновременно добавлено от одной до трех новых гра-
ней. Таким образом, текущий фронт дискретизации постепенно про-
двигается в пространстве — откуда и само название “advancing front”.
Обновив данные о фронте, можно вновь изъять тетраэдр, снова обно-
вить фронт и так далее, пока вся область не окажется исчерпана [5–10].
Несмотря на кажущуюся простоту идеи, реализация алгоритма исчер-
пывания таит в себе ряд трудностей (особенно в трехмерном случае).
Рассмотрим пример простого алгоритма исчерпывания для триангуля-
ции двумерных областей.
Пусть задана некоторая область и триангуляция ее границы (рис. 1).
Тогда множество всех ребер границы
L
будет представлять собой
фронт (это множество может быть и не односвязным, как в приве-
денном примере), а концы отрезков фронта — множество граничных
узлов
G
. Алгоритм состоит из следующих шагов:
1. Поиск граничного узла
g
1
с наименьшим значением внутреннего
(по отношению к исчерпываемой области) угла.
2. Выбор
L
i
— длиннейшего из двух ребер, инцидентных
g
1
. (Вто-
рой конец этого ребра обозначим
g
2
.)
3. Формирование множества
B
граничных узлов, находящихся на
расстоянии не более
√
3
k
L
i
k
от узлов
g
1
и
g
2
. Для каждого узла
g
3
2
B
96
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2008. № 2
