Описание препроцессора (стр. 6 )

Алгоритм разработан в 1989 году, его создателем является Paul Bourke.  Изначально алгоритм был разработан триангуляции топографического рельефа по имеющейся информации о его высоте в различных подобластях. Подробное описание алгоритма можно найти по адресу: http:///papers/triangulate/ . Ниже приведено упрощенное описание алгоритма.

На любом этапе процесса триангуляции имеется уже существующая сетка и некоторая точка, которую необходимо добавить. Процесс начинает с создание супертреугольника: искусственного треугольника, включающего в себя все точки набора. В конце процесса триангуляции, все треугольники, границы которых лежат на ребрах супертреугольника, должны быть удалены.

Добавление новой точки к существующей сетке

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

Образование «включающего» многоугольника

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

Создание новых треугольников.

Добавление новой точки приводит к увеличению числа треугольников в сетке на два. Таким образом, количество треугольников в два раза превышает количество опорных точек. (Это утверждение включает в себя также супертреугольник. По завершении процесса триангуляции некоторые треугольники будут удалены и количество треугольников станет меньше удвоенное количество опорных точек).

Примеры работы алгоритма

Ниже приведены примеры триангуляции исходной модели с использованием описанных алгоритмов. На практике оказалось, что результат триангуляции в бьльшей степени зависит от выбранного метода генерации точек, нежели от выбранного алгоритма триангуляции. В связи с этим для примеров использован алгоритм S-hull.

Пример 1. Хаотическая генерация. Параметры:

Количество точек на зону: 100;

Минимальное расстояние между точками: 0.5;

Ограничение попыток добавления новой точки: 1000.

Пример 1.

Пример 2. Прямоугольная регулярная структура точек.

Пример 2.

Пример 3. Равноугольная регулярная структура точек.

Пример 3.

Пример 4. В этом примере будет продемонстрирован алгоритм хаотической генерации с распределением плотности. Основные параметры совпадают с параметрами примера 1. Заданы дополнительные параметры:

Плотность 50 для зон 1, 4, 5, 8. В этих зон минимальное расстояние между точками увеличено до 1.0;

Плотность 80 для подобласти в центральной части пластины с радиусом 5. Минимальное расстояние между точками: 0.8.

Пример 4.

Ниже приведена форма настроек метода и пример выделения подобласти:

Настройки генерации точек для триангуляции по Делоне.

Модуль оптимизации сетки.

В препроцессоре доступны 2 метода оптимизации сетки и мощный внешний модуль для оптимизации с использованием методов Рапперта, который будет описан отдельно. Рассмотрим «резидентные» методы оптимизации.

Метод увеличения минимального угла в КЭ

Примечание: Звездой узла будем называть совокупность конечных элементов, одним из узлов которых является данный узел.

определить граничные и внутренние узлы (выделить внутренние узлы) организовать перебор внутренних узлов для текущего внутреннего узла определить звезду. организовать перебор элементов звезды. определить минимальный угол и минимальную сторону в каждом из элементов и  выбрать из них минимальный угол(назовем 1-й угол) и соответствующую ему сторону. на основе полученной минимальной стороны определить шаг и направление сдвига.

6а. изменить координату текущего внутреннего узла на шаг.

определить минимальный угол(назовем 2-й угол) и сторону звезды при новом положении узла. если 2-й угол больше 1-го, то запомнить новое положение текущего узла,  присвоить значение 2-го угла 1-му углу и повторить пункты 6а,7; иначе если 2-й угол не больше 1-го, то изменить направление сдвига и выполнить пункты 6а,7. по завершении перебора всех узлов если была изменена координата хотя бы одного узла и число проходов меньше 100 (можно задать любое другое число) сделать еще один проход, то есть выполнить пункты 2-9.

Пример работы алгоритма:

Перед оптимизацией. Минимальный угол: 24,69

После оптимизации. Минимальный угол: 36,95

Регуляризация

Идея метода заключается в позиционировании каждого узла по центру тяжести многоугольника, образованного его звездой.

Данный алгоритм реализует изменение координат узла относительно многоугольника, который образуют элементы, в составе которых встречается искомый узел.

Координаты находятся по формуле центра масс выпуклого многоугольника:

Формула достаточно громоздка и для получения результата необходимы существенные затраты машинного времени.

Алгоритм выполняется в цикле для всех узлов до тех пор, пока минимальное перемещение узла не станет меньше заданного достаточно малого или пока количество итераций не достигнет 1000.

Пример работы алгоритма:

Перед оптимизацией.	После оптимизации. Отмечается увеличение КЭ, форма которых близка к равностороннему треугольнику.

Внешний модуль – подсистема Рапперта. Основные понятия

При описании своего алгоритма Рапперт вводит свою терминологию, которой будем придерживаться и мы.

Элемент по смыслу совпадает с конечным элементом. Это элементарная часть пространства на множество которых мы хотим разбить более сложную область этого пространства. В нашем случае элементом является треугольник.

Узел (node) — точка в которой сходятся грани и соприкасаются несколько элементов. В отличие от вершин элементов узел общий для всех соприкасающихся в одной точке элементов.

Сегмент (segment) — это отрезок, соединяющий две соседние точки лежащие на границе области разбиения, другими словами этот отрезок принадлежит контурам области.

Грань (edge) — это отрезок по которому граничат два соприкасающихся треугольника. Используя предыдущее определение можно сказать, что все множество отрезков, соединяющих вершины элементов, в любой момент работы алгоритма складывается из сегментов и граней.

Включенная точка (encroached point) — любая вершина текущей сетки, которая находится внутри окружности, радиусом которой является любой сегмент.

"Неправильный треугольник" (bad triangle) — это треугольник неудовлетворяющий глобальным условиям, которые накладываются на генерируемую сетку.

Вытянутый треугольник (skinny triangle) — треугольник, имеющий одну сторону, намного отличающуюся от других двух. То есть треугольник слишком вытянут вдоль некоторой прямой. На критериях "вытянутости" мы остановимся ниже.

Базовые процедуры алгоритма

Алгоритм опирается на две базовые процедуры: a) разбиение неправильного треугольника с введением нового узла и b) разбиение сегмента, принадлежащего границе области разбиения с введением нового узла.

При разбиении треугольника происходит следующее:

Вычисляются координаты центра окружности, описанной вокруг треугольника, подлежащего разбиению. В эту точку добавляется новый узел. Удаляется треугольник, подлежащий разбиению и прилегающие и добавляются новые.

Разбиение «неправильного» треугольника

Вторая базовая процедура состоит в следующем:

Если в окружность, диаметром которой является сегмент, принадлежащий границе области разбиения, попадает точка, не принадлежащая этому сегменту, то сегмент делится на две части. Удаляется треугольник, которому принадлежал первоначальный сегмент, и добавляются два новых треугольника

Разбиение "неправильного" сегмента посередине и добавление двух новых треугольников

Принцип работы

Принцип работы алгоритма состоит в цикле определения "неправильных" треугольников, т. е. треугольников, не удовлетворяющих определенному критерию, и произведение над ним одной из базовых процедур. В оригинальном алгоритме, предложенным Джимом Раппертом используется один критерий — минимальный угол в треугольниках сетки. В каждом треугольнике сетки определяется минимальный угол и, затем, сравниваются минимальные углы для всех треугольников с целью нахождения минимального угла сетки. Другими словами, минимальный угол в сетке равен минимально возможному углу, образованному двумя сегментами, либо двумя гранями, либо сегментом и гранью, имеющими общий узел.