Глобальная балансировка триангуляционной сети

Abstract

Предложен новый алгоритм балансировки триангуляционной сети, содержащей точки Штейнера, основанный на методе наименьших квадратов. Он минимизирует среднеквадратичное отклонение косинусов углов триангуляции от оптимального значения 0,5. Алгоритм не имеет ограничений, поэтому может быть применен к любым триангуляциям, полученным алгоритмами сгущения триангуляционной сети, например алгоритмами Рупперта или Эртена и Унгора, при этом он не увеличивает число точек, а также не нарушает реберных связей. Проведенные эксперименты показали, что предлагаемый алгоритм существенно повышает число углов в диапазоне от 50 до 70° и не приводит к появлению треугольников с существенно меньшими минимальными углами. Алгоритм может быть эффективно реализован с использованием специализированных программных пакетов, предназначенных для быстрого решения разреженных систем линейных уравнений методом наименьших квадратов, например SuiteSparse. Благодаря этому алгоритм является простым в реализации