Алгоритм Рупперса - Википедия - Rupperts algorithm

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

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

Мотивация

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

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

Описание алгоритма

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

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

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

Псевдокод

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

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

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

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

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

Рекомендации

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

внешняя ссылка