Соединение узлов

Чрезвычайно популярный подход к проблеме построения сетки состоит в соединении узлов. Популярность этого подхода объясняется простотой его концепции. Метод делится на две основные фазы: создание узлов (рис. 8.8, о) и построение элементов (рис. 8.8, б).

Соединение узлов

Создание узлов

В опубликованных работах, посвященных задаче создания узлов, можно найти следующие методы.        

Метод Кавендиша [29]. По этому методу работа начинается с задания граничных узлов вручную. Затем программа осуществляет автоматическое создание в утренних узлов с учетом требований к плотности ячеек. Объект делится на участки, размер которых соответствует размеру элементов. В участке i создается квадратная сетка масштаба r (i). Одиночная сетка, построенная в предположении, что плотность конечной сетки должна быть постоянной, изображе на рис. 8.9. В каждом квадрате сетки случайным образом создается один внутренний узел. Это может быть реализовано выбором двух случайных чисел от 0 до 1 и расчетом координат точки по соответствующим осям квадратной ячейки. Если узел попадает внутрь объекта, а расстояние от него до граничных и автоматически созданных на предыдущих шагах алгоритма узлов оказывается большим r (i), этот узел считается принятым. В противном слу- чае случайным образом выбирается следующий узел, который проходит ту же проверку. Если за фиксированное количество попыток (например, пять) при- нять узел не удается, квадратная ячейка сетки просто пропускается и программа переходит к следующей ячнейке. Этот метод может быть расширен до трех измерении простым переходом от плоской квадратной сетки к пространственной кубической.   1                     1

Соединение узлов

□ Метод Шимады [141]. Этот метод требует представления внутренней области оОъекта заполненной пузырьками (рис. 8.10). Центральные точки пузырьков становятся узлами. Размер пузырька определяется температурным распределением, соответствующим заданной плотности сетки. Положения пузырьков определяются условиями равновесия с учетом всех сил реакции, действующих между ними.

 

Соединение узлов

Построение элементов

На этом этапе осуществляется соединение узлов, в результате чего получаются элементы, которые не должны перекрываться, но должны покрывать всю площадь объекта. Мы рассмотрим метод Ли, который может давать четырехугольные элементы. Однако наиболее популярным методом соединения узлов является метод триангуляции Делоне. В нижеследующем рассмотрении мы будем учитывать только те элементы, у которых узлы находятся в вершинах. Если задача требует использования элементов с промежуточными узлами, их легко можно построить по элементам с узлами в вершинах. Поэтому мы не будем исследовать промежуточные узлы во всех описываемых ниже методах.

□   Метод Ли [98]. Согласно этому методу, на объект накладывается квадратная сетка, размер ячеек которой соответствует ожидаемому размеру элементов. Затем узлы, полученные на предыдущем этапе, связываются с ячейками этой сетки. Ячейки и соответствующие им узлы перебираются по столбцам слева направо и сверху вниз. Внутри ячейки узлы упорядочиваются по возрастанию абсцисс. Узлы с одинаковыми абсциссами сортируются но возрастанию ординат. Узлы перебираются последовательно, причем из соседних узлов выбираются такие, с которыми данный узел образует «хороший» четырехугольник. Если же четырехугольник оказывается «плохим», вместо него формируется треугольник.

□    Триангуляция Делоне [155]. Это, пожалуй, наиболее популярный метод формирования треугольников путем соединения узлов, поскольку он максимизирует сумму наименьших углов во всех формируемых треугольниках. Иначе говоря, данный метод триангуляции ориентирован на то, чтобы по возможности избегать формирования узких треугольников.

Триангуляция Делоне обычно начинается с диаграммы Вороного или полигонов Дирихле [57]. Диаграмма Вороного ( Voronoi diagram) множества N точек Рi (i= 1, 2,.... N) сос тоит из N многоугольников (многогранников, если задача решается в трех измерениях) Vt, центры которых находятся в точках Рi причем многоугольники эти представляют собой геометрическое место точек, для которых данный узел i является ближайшим. Математическая запись этого утверждения относительно многоугольника Vi выглядит следующим образом:

Соединение узлов

Многоугольник (многогранник) Vi является выпуклым. Он ограничивается прямыми (плоскостями), проходящими через середины отрезков, соединяющих узел Pj с его соседями, и перпендикулярными этим отрезкам. Такое разбиение двумерного или трехмерного пространства называется полигонами Дирихле (Dmchlet tesselation). Каждый многоугольник (многогранник) Вороного связан с одним определенным узлом. Построив диаграмму Вороного, мы можем перейти к созданию треугольных (тетраэдрических) элементов, соединяя точки соседних многоугольников (многогранников) Вороного. Диаграмму Вороного и результат триангуляции для десяти узлов на плоскости демонстрирует рис. 8.11.

Соединение узлов

Триангуляция Делоне может производиться непосредственно на наборе точек (узлов) с использованием алгоритма двухмерной триангуляции Ватсона f 155] без предварительного построения диаграммы Вороного. Согласно этому алгоритму, три точки, не лежащие на одной прямой, объединяются в треугольник, если окружность, проведенная через эти точки (описанная окружность для будущего треугольника), не захватывает никаких других точек. Алгоритм реализуется следующим образом. Сначала строится треугольник Т0, внутри которого находятся все узлы. Вершинами этого треугольника могут быть и точки, не являющиеся узлами. Затем осуществляется перебор узлов из полного их множества, и для каждого узла ищутся треугольники, такие, что описанная вокруг них окружность захватывает данный узел. Эти л реугольники (называемые пересеченными) в дальнейшем не рассматриваются. На рис. 8.12, б они обозначены знаком X. Затем вмес то них строятся новые треугольники, образуемые соединением добавленного узла с вершинами пересеченных треугольников (рис. 8.12, в).

Соединение узлов

На заключительном этапе удаляются треугольники, полученные соединением узлов с дополнительными точками, введенными на первом этапе для построения треугольника Т0. Эта процедура легко обобщается на трехмерное пространство путем перехода к использованию описанных сфер для четырех узлов вместо окружностей для трех узлов [30]. Однако в трехмерном случае триангуляция Делоне может давать очень узкие тетраэдры, тогда как в двухмерном случае алгоритм обеспечивает в некотором смысле оптимальную триангуляцию данного набора точек.

Смотрите также