• Хаотическая генерация точек с распределением плотности.
  • Прямоугольная регулярная структура точек.
  • Равноугольная регулярная структура точек.
  • Использование узлов имеющейся сетки
  • Алгоритмы триангуляции Делоне
  • Алгоритм S - Hull .
  • Алгоритм Пола Бурка.



  • страница11/32
    Дата11.07.2018
    Размер4.51 Mb.

    Описание препроцессора


    1   ...   7   8   9   10   11   12   13   14   ...   32

    Хаотическая генерация точек.

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

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

    Пользователь препроцессора имеет возможность задать следующие параметры алгоритма генерации:

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

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

    Предельное количество попыток генерации координат новой точки.



    Хаотическая генерация точек с распределением плотности.

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

    Список плотности зон: список зон с указанным для них количеством точек и минимальным расстоянием между этими точкам;

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



    Алгоритм генерации можно представить в виде последовательности следующих шагов:

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

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

    3. Для каждого элемента списка плотности подобластей: удалить все точки, попавшие в подобласть в ходе генерации п.1 и п.2, кроме точек соответствующих узлам зон.

    4. Для каждого элемента списка плотности подобластей: использовать метод хаотической генерации точек для подобласти. Для проверки принадлежности точки подобласти использовать два условия:

    Где:


    – точка центра окружности, описывающей подобласть

    ­– радиус этой окружности.

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



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

    Эффективным и экономичным является регулярное разбиение области семейством вертикальных и горизонтальных линий с шагом






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

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

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

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



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

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

    Использование узлов имеющейся сетки

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

    Алгоритмы триангуляции Делоне

    Сгенерированный тем или иным методом набор опорных точек далее передаётся одному из двух (по выбору пользователя) реализованных в системе методу триангуляции по Делоне. Рассмотрим подробнее каждый из них.



    Алгоритм S-Hull.

    Этот новый алгоритм был разработан в 2011 году. Его создателями являются Phil Atkin, Dr. Sinclair. Этот алгоритм обладает высокой (O(nlog(n))) скоростью работы и предназначен для построения триангуляции по Делоне на наборе двумерных точек. Подробное описание алгоритма можно найти на сайте их создателей: http://s-hull.org/ . Ниже приведена последовательность шагов алгоритма.



    Для набора уникальных точек в области

    1. Выбрать начальную точку из .

    2. Сортировать точки по критерию

    3. Найти точку наиболее близку к .

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

    5. Упорядочить точки для образования праворукой системы: эти три точки образуют базовую выпуклую оболочку.

    6. Упорядочить оставшиеся точки согласно критерию для формирования набора

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

    8. На этом этапе получена непересекающаяся триангуляция набора точек. (Этот метод показывает потрясающую скорость при создании такой триангуляции).

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


    Алгоритм Пола Бурка.

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



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


    Новая точка

    Предыдущая добавленная точка

    Имеющаяся сетка


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




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


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


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

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




    Результирующие треугольники, образованные с использованием новой точки


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

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


    1   ...   7   8   9   10   11   12   13   14   ...   32

    Коьрта
    Контакты

        Главная страница


    Описание препроцессора