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

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;
};

struct SemiRib
{
    unsigned int next;
    unsigned int twin;
    unsigned int vert;
};

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

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

В начале 2025 года я написал функцию optiL, которая делает то же самое, что и maxL1, но при этом не является шаблоном, и используемый в ней функтор IDiagFunc прямо указывает - нужно ли изменить для данной пары треугольников диагональ. Для этого ему надо передать индекс полуребра и номера граней. Имеется две функции optiL. Первая использует уже созданный массив полурёбер rib, а вторая заполняет его по указанной триангуляции trian:

class IDiagFunc
{
public:
    virtual IDiagFunc & link ( CArrRef<SemiRib> & r ) = 0;
    virtual bool operator () ( nat r, nat s1, nat s2 ) = 0;
};

void optiL ( IDiagFunc & change, ArrRef<SemiRib> & rib );
void optiL ( IDiagFunc & change, CCArrRef<Set3<nat> > & trian, DynArray<SemiRib> & rib );

По идее шаблон maxL1 можно везде заменить на функцию optiL, но я пока это сделал в отдельных случаях.

Шаблон функций 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 и atrian.cpp.