Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Второй алгоритм Чу [ править ]

Сетка, созданная с помощью текста второго алгоритма Чу
Сетка озера Мичиган с использованием второго алгоритма Чу, реализованного в пакете Triangle .

Второй алгоритм Чу берет кусочно-линейную систему (PLS) и возвращает ограниченную триангуляцию Делоне только для качественных треугольников, где качество определяется минимальным углом в треугольнике. Разработанный Л. Полом Чу для создания сетки поверхностей, встроенных в трехмерное пространство, [1] второй алгоритм Чу был принят в качестве генератора двумерной сетки из-за практических преимуществ перед алгоритмом Рупперта в некоторых случаях и является генератором сетки качества по умолчанию. в свободно доступном пакете Triangle . [2] Второй алгоритм Чу гарантированно завершит работу и создаст сетку с градуированными размерами локальных объектов с минимальным углом примерно до 28,6 градусов.[3]

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

Алгоритм Рупперта [ править ]

Выход, соответствующий триангуляции Делоне
Выход, соответствующий триангуляции Делоне
Пример алгоритма Рупперта

Алгоритм Рупперта берет планарный прямолинейный график (или кусочно-линейную систему с размерностью больше двух ) и возвращает соответствующую триангуляцию Делоне только качественных треугольников. Треугольник считается некачественным, если его отношение радиуса описанной кромки к самому короткому краю превышает некоторый предписанный порог. Обнаруженный Джимом Руппертом в начале 1990-х годов [4], «алгоритм Рупперта для создания двумерной качественной сетки, возможно, является первым теоретически гарантированным алгоритмом создания сетки, который действительно удовлетворителен на практике». [5]

Мотивация [ править ]

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

Промежуточные триангуляции алгоритма Рупперта

Алгоритм [ править ]

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

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

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

Псевдокод
функция Рупперта ( точки , сегменты , порог ) :  T  : = Триангуляция Делоне ( точки ) Q  : = набор вторгшихся сегментов и треугольников низкого качества while  Q  не пусто: // Основной цикл,  если  Q содержит сегмент s : вставьте среднюю точку s в T,  иначе  Q содержит треугольник t низкого качества : если центр описанной окружности t вторгается в сегмент s : добавить s к Q ; еще : вставьте центр описанной окружности t в конец T,  если  конец, если обновите Q  конец, пока Возвращение  Т конец Рупперт.

Практическое использование [ править ]

Без модификации алгоритм Рупперта гарантированно завершит работу и сгенерирует качественную сетку для неострых входных данных и любого порога низкого качества менее 20,7 градусов. Чтобы ослабить эти ограничения, были внесены различные небольшие улучшения. Ослабляя требования к качеству вблизи малых входных углов, алгоритм может быть расширен для обработки любого линейного входного сигнала. [6] Изогнутые входные данные также могут быть построены с использованием аналогичных методов. [7] Алгоритм Рупперта можно естественным образом расширить до трех измерений, однако его выходные гарантии несколько слабее из-за тетраэдра типа ленты.

Расширение алгоритма Рупперта в двух измерениях реализовано в свободно доступном пакете Triangle . Два варианта алгоритма Рупперта в этом пакете гарантированно завершат работу при пороге низкого качества около 26,5 градусов. [8] На практике эти алгоритмы успешны для некачественных пороговых значений более 30 градусов. Однако известны примеры, которые приводят к сбою алгоритма с порогом выше 29,06 градуса. [9]

См. Также [ править ]

  • Размер локального объекта
  • Многоугольная сетка
  • TetGen
  • Диаграмма Вороного

Ссылки [ править ]

  1. Перейти ↑ Chew, L. Paul (1993). «Создание сетки гарантированного качества для криволинейных поверхностей». Материалы девятого ежегодного симпозиума по вычислительной геометрии . С. 274–280.
  2. ^ Шевчук, Джонатан (2002). «Алгоритмы уточнения Делоне для генерации треугольной сетки». Вычислительная геометрия: теория и приложения . 22 (1–3): 21–74. DOI : 10.1016 / s0925-7721 (01) 00047-5 .
  3. ^ Рэнд, Александр (2011). «Где и как работает второй алгоритм уточнения Делоне Чу» (PDF) . Труды 23-й Канадской конференции по вычислительной геометрии . С. 157–162.
  4. ^ Рупперт, Джим (1995). «Алгоритм уточнения Делоне для создания качественной двумерной сетки». Журнал алгоритмов . 18 (3): 548–585. DOI : 10.1006 / jagm.1995.1021 .
  5. ^ Шевчук, Джонатан (12 августа 1996). «Алгоритм уточнения Делоне Рупперта» . Проверено 28 декабря 2018 .
  6. ^ Миллер, Гэри; Пав, Стивен; Уокингтон, Ноэль (2005). «Когда и почему работают алгоритмы уточнения Делоне». Международный журнал вычислительной геометрии и приложений . 15 (1): 25–54. DOI : 10.1142 / S0218195905001592 .
  7. ^ Пав, Стивен; Уокингтон, Ноэль (2005). Доработка Делоне за счет обрезки углов . Материалы 14-го Международного круглого стола по сетке. С. 165–181.
  8. ^ Шевчук, Джонатан (2002). «Алгоритмы уточнения Делоне для генерации треугольной сетки». Вычислительная геометрия: теория и приложения . 22 (1–3): 21–74. DOI : 10.1016 / s0925-7721 (01) 00047-5 .
  9. ^ Рэнд, Александр (2011). «Улучшенные примеры незавершенности алгоритма Рупперта». arXiv : 1103.3903 [ cs.CG ]..

Дальнейшее чтение [ править ]

  • Рино, Лоран. «2D согласующиеся триангуляции и сетки» . Проверено 28 декабря 2018 .
  • Шевчук, Джонатан. "Треугольник: Генератор двумерных качественных сеток и триангулятор Делоне" . Проверено 28 декабря 2018 .
  • Си, Ханг (2015). «TetGen: Качественный Генератор Тетраэдрической сетки и 3D Триангулятор Делоне» . Архивировано с оригинала c. 2014 . Проверено 28 декабря 2018 .