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

template <class F, class A1, class A2=A1>
class Func2a // Функция двух аргументов
{
public:
    virtual F operator () ( A1 a1, A2 a2 ) const = 0;
};

template <F, class A1, class A2=A1, class A3=A2>
class Func3a // Функция трёх аргументов
{
public:
    virtual F operator () ( A1 a1, A2 a2, A3 a3 ) const = 0;
};

template <class T>
void maxL1 ( const Func3a<T,nat> & quality, const Func2a<T,T> & merge, ArrRef<SemiRib> rib )
...

Исходными данными являются: функтор качества треугольника, функтор слияния качеств, количество рёбер, ссылка на массив с рёбрами. В массиве должна быть записана какая-то триангуляция. Причём рёбра принадлежащие к одному треугольнику должны находится последовательно, и поле twin должно быть меньше количества рёбер только у одного ребра из пары.
Оптимизация исходной триангуляции происходит путём сравнения двух пар треугольников - существующей пары соседних треугольников и альтернативной пары треугольников полученной перестановкой разделяющей диагонали. Если качество второй пары окажется больше первой, то триангуляция меняется. И так до тех пор пока такие пары находятся. Т. к. эта оптимизация локальная, то глобальный максимум может быть и не найден ( будет найден локальный ). Этот алгоритм требует дополнительной памяти O ( n ) и времени в среднем тоже O ( n ). Вторая оценка определена экспериментально.

Шаблон функций maxG1 осуществляет глобальную оптимизацию путём перебора всех возможных вариантов триангуляции:

template <class T> 
SuiteRef<Set3<nat> > & maxG1 ( const Func3a<T,nat> & quality, const Func2a<T,T> & merge, 
                               nat nv, SuiteRef<Set3<nat> > & res )
...

Описание шаблона классов Set3 находится здесь.
Описание шаблонов классов ArrRef и SuiteRef находится здесь.
Исходники находятся в файле atrian.h.