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

Аннотация

В статье рассматривается проблема повышения вычислительной надежности треугольных сеток, используемых в численных методах и геометрическом моделировании, на примере триангуляции плоской многоугольной области. Обосновано, что точность приближений в треугольных элементах определяется не только характерным размером ячеек, но и их формой: появление вытянутых треугольников с малыми углами приводит к росту погрешности при сгущении сетки, вплоть до неограниченного. В качестве идеализированного ориентира вводится функционал, равный минимальному углу по всем элементам триангуляции, и обсуждается его максимизация за счет перемещения внутренних узлов, однако отмечаются вычислительная трудоемкость и сложность прямой реализации. Для практического улучшения сетки предложены два локальных критерия качества, определяемые в окрестности каждого внутреннего узла через многоугольник соседства, образованный смежными вершинами. Первый критерий основан на минимизации «разброса» углов при внутренней вершине относительно равномерного значения 2π/r, что приводит к выравниванию углов и, в предельном случае, к положению узла вблизи центра многоугольника соседства. Второй критерий использует минимизацию дисперсии квадратов расстояний от узла до сторон многоугольника соседства, обеспечивая более равномерное положение точки относительно границ локальной конфигурации. Для обоих критериев представлены итерационные процедуры переноса узла с оценкой производной по конечным разностям и последовательной коррекцией координат до стабилизации. Эффективность методик продемонстрирована на триангуляции Делоне для прямоугольника с 80 точками (граничными и случайными внутренними): среднее значение углового функционала уменьшается более чем на 22%, а функционала расстояний – более чем на 18%. На модельной задаче вычисления интегрального функционала для u(x,y)=x²+y² показано снижение ошибки приближения: после оптимизации по угловому критерию – на 18%, по критерию расстояний – на 6%. Отмечена программная реализация в среде Python, включающая построение триангуляции Делоне и процедуры улучшения формы элементов.