Rappert (1013965), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

В своей работе алгоритм оперирует одним из подмножеств, описанных на предыдущем этапе³.

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

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

1. Первичные:

• Минимальный угол исходного элемента

• Максимальная площадь исходного элемента

2. Вторичные:

• Минимальный угол создаваемых элементов

• Позиционирование узлов сетки после создания нового узла⁵

• Минимальная площадь создаваемых элементов (для сегментов)

В оригинальном описании приводиться один критерий – минимальный угол. Но в результате анализа стало ясно, что их не достаточно и были выработаны остальные критерии. Считаю, что следует отметить наличие и других критериев, позволяющих улучшить результаты и генерацию сетки алгоритмом Рапперта, но большая их часть носит эмпирический характер.

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

Сам алгоритм был разбит на две базовые независимые процедуры: разбиение сегментов и треугольников (закладка «Первичные ограничения»). Оригинальный расчет по алгоритму Рапперта можно получить, запустив эти процедуры в данной последовательности без всяких проверок.

Однако есть риск возникновения нулевых по площади элементов, генерации нулевых треугольников и зацикливания при разбиении острых узлов. Это все известные минусы «чистого» алгоритма Рапперта. Для преодоления узких мест алгоритма в процедуру разбиения треугольников введены проверки на минимальный угол и максимальную площадь. В том случае, если какой-либо угол в треугольнике не меньше заданного или площадь треугольника больше максимальной площади, то данный треугольник пройдет проверку на применение процедуры разбиения.

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

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

Результат разбиения также может быть подвергнуть проверке по максимальной площади и по минимальному углу созданных элементов, как при разбиении сегментов, так и при разбиении треугольников. Данная проверка задается на закладке «Вторичные ограничения». Задание данных ограничений существенно улучшает характер разбиения, как сегментов, так и треугольников.

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

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

В данной версии модуля решены следующие задачи:

• Определение, с использованием координат узлов, вхождения узла в многоугольник

• Определение, с использованием координат узлов, вхождения узла в элемент

• Определение, с использованием координат узлов, углов, площадей элементов, многоугольников

• Определение, с использованием координат узлов, попадания узла в форму пластины

• Определение смежных узлов, элементов, конкурирующих диагоналей

• Определение «неправильных» сегментов

• Определение «неправильных» треугольников

• Определение критериев выборки и отсеивания узлов, элементов, диагоналей

• Определение наиболее оптимальных (экспертно) параметров по умолчанию и рассчитываемых относительно текущей сетки.

3.3.5.1. Описание алгоритма «Смена диагонали»

Данный алгоритм выполняет смену «не оптимальной» диагонали на «оптимальную» внутри одного кластера, образованного смежными элементами. «Оптимальной» диагональю считается диагональ меньшей длины, «не оптимальной» другая (большая по длине) диагональ кластера.

Описание процедуры ChangeDiagLines(), реализующей смену диагонали, представлено в приложении 4.

Проверка отдельного элемента осуществляется исходя из следующего алгоритма (упрощенная форма алгоритма, описанного в приложении 4):

1. Проверка все ли стороны элемента выбраны, если да то шаг 6, иначе шаг 2.

2. Выделение кластера (выделение стороны элемента и нахождение смежного ей элемента)

1. Если смежного элемента нет, то переход к шагу 1, иначе переходим к шагу 4

2. Проверка необходимости и смена диагоналей в кластере

3. Переход к следующей стороне элемента, шаг 1

4. Обработка элемента окончена

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

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

С лучай мнимой диагонали достаточно сложен для проверки. В данной реализации (подробное описание см. в приложении 4) делается сравнение сумм площадей образующих элементов и сумм новых и элементов. Так же проверяется случай образования нулевого элемента. Погрешность вычислений принята достаточной для сетки 0.1 единице измерений масштаба.

Для новых элементов кластера реализована возможность осуществления лишь одного вида проверки, задаваемой пользователем. А именно, проверка всех углов элементов, после изменения диагонали. Каждый новый угол элемента кластера должен быть не меньше значения указанного пользователем. Так же есть возможность расчета и использования, в качестве заданного пользователем, максимального угла всех элементов конечно-элементной сетки.

Процедура позиционирования определяется пользователем. После каждой смены диагонали вся конечно-элементная сетка проходит процедуру позиционирования узлов.

В отличие от процедур разбиения, которые будут описаны ниже, процедура смены диагонали не осуществляет повторной проверки всех элементов в случае замены диагонали, а переходит к проверке следующей. Данный подход выбран из соображений экономии времени и вычислительной мощности ЭВМ, а также основан на подходе к обработке элементов. Стороны элементов динамично меняются, при изменении диагонали, и это приводит к модификации последовательности узлов, образующих элемент, и расположения этих узлов. Результат всего этого представляется достаточно интересным.

3.3.5.2. Описание алгоритма «Разбиение сегмента»

Данный алгоритм имеет ряд ограничений, накладываемых как на начальный сегмент⁷, для которого проверяется условие разбиения, так и на образуемые в результате возможного разбиения сегмента элементы⁸. Последние регулируют характер сетки, поскольку ограничивают углы создаваемых элементов и их площадь (закладка «Вторичные ограничения»). Данная проверка позволяет избежать зацикливания процедуры разбиения, поскольку неизвестно количество узлов, которое может после разбиения и позиционирования попасть под условия разбиения для новых сегментов.

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

Площадь нового элемента не должна превышать 1.

Алгоритм (его упрощенная схема) представлена ниже:

1. Проверка сегмента (очередной стороны) элемента

2. Если не было изменений, то 1, иначе 3

3. Окончание проверка сегмента

Шаг 1 включает следующие операции:

• определение смежного элемента к данному сегменту;

• проверку необходимости и соблюдений условий разбиения;

• проверку безусловных и пользовательских ограничений на новые создаваемые элементы;

• процедура разбиения элементов.

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

Приведем возможный вариант разбиения сегмента⁹.

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

Алгоритм представляет двойной цикл с условием проверки элементов сетки. При работе алгоритма формируется условие завершения цикла. Если оно срабатывает, то цикл либо продолжит своё выполнение, либо закончит. Необходимо учитывать, что при определенной ситуации цикл может быть бесконечным.

3.3.5.3. Описание алгоритма «Разбиение контура»

Данный алгоритм так же имеет ряд ограничений, накладываемых как на начальный сегмент¹⁰, для которого проверяется условие разбиения, так и на образуемые в результате возможного разбиения сегмента элементы. Характер ограничений аналогичен выше описанной процедуре.

Единственное отличие процедур в поиске сегмента. Для процедуры «Разбиение сегмента» сегментом будет только внутренний сегмент, а для данной процедуры только сегмент, принадлежащий оболочке (контуру).

Остановимся подробнее на самой реализации процедуры разбиения.

Приведем возможный вариант разбиения сегмента¹¹.

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

Алгоритм представляет двойной цикл с условием проверки элементов сетки. При работе алгоритма формируется условие завершения цикла. Если оно срабатывает, то цикл либо продолжит своё выполнение, либо закончит. Необходимо учитывать, что при определенной ситуации цикл может быть бесконечным.

3.3.5.4. Описание алгоритма «Разбиение треугольника»

Данный алгоритм представляет наибольший интерес и упрощенно также представляет собой двойной цикл с условием, который также может быть бесконечным. Более подробное описание в приложении 5.

Упрощенно алгоритм разбиения отдельного элемента выглядит следующим образом:

1. Начало цикла проверки всех элементов

2. Выбор последовательно каждого элемента

3. Если необходимо, то проверяем по минимальному углу, иначе и если проходит по углу, то шаг 5

4. Если необходимо, то проверяем по максимальной площади, иначе и если проходит по максимальной площади, то шаг 5

5. Проверка условий разбиения треугольника

6. Если условия срабатывают, то проверяем: можно ли осуществлять процедуру разбиения для данного элемента (шаг 7), иначе 2

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

8. Если возможно, то флаг разбиения становиться True, иначе шаг 2

9. Если флаг разбиения True, то шаг 1, иначе если не все элементы сетки обработаны, то шаг 2, а если все обработаны, то окончание процедуры разбиения

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

Характеристики

Список файлов лабораторной работы