Триангуляция в пространстве

Первый алгоритм предназначен для триангуляции замкнутой ломаной. Он основан на полном переборе различных вариантов триангуляции и выборе из них лучшего варианта. Лучшим считается тот вариант, у которого будет наименьшая суммарная площадь треугольников. Этот подход имеет физический смысл. Например, мыльная плёнка, натянутая на проволочный каркас произвольной формы, имеет минимальную по площади поверхность.
Этот алгоритм требует дополнительную память порядка O(n2), и время работы алгоритма пропорционально n3: 

DynArrRef< Set3<nat> > & trian ( CArrRef<Vector3d> vert, DynArrRef< Set3<nat> > & res );

Исходными данными являются: ссылка на массив вершин ломаной и ссылка на массив, куда будет записываться результат ( эта же ссылка и возращается ). Треугольник описывается тремя целыми числами, которые являются индексами массива вершин.

Иногда нужно соединить две ломаные в пространстве ( замкнутые или незамкнутые одновременно ) треугольниками так, чтобы каждый треугольник касался обеих линий. Среди множества вариантов выберем тот, у которого суммарная площадь минимальна.
Время работы алгоритма и требуемая память пропорциональны n1*n2, где n1 и n2 - количество точек соответственно первой и второй ломаной. 

DynArrRef< Set3<nat> > & trian ( CArrRef<Vector3d> vert1, CArrRef<Vector3d> vert2, 
                                 bool isCycle, DynArrRef< Set3<nat> > & res );
Здесь vert1 и vert2 - ломаные, заданные своими вершинами. Если isCycle = true - ломаные считаются замкнутыми и результирующая поверхность будет замкнута в кольцо. res - массив результирующих треугольников, заданных индексами вершин из ломаных vert1 и vert2. Номер индекса от 0 до n1-1 задает точку из vert1, а номер индекса от n1 до n1+n2-1 задает точку из vert2. n1 и n2 должны быть больше 1. Размер массива res будет равен n1 + n2, если isCycle = true и n1 + n2 - 2, если isCycle = false.

В приложении DEMO можно посмотреть на результаты этих триангуляций.

Описание шаблонов классов CArrRef и DynArrRef находится здесь.
Описание класса Vector3d находится здесь.
Описание шаблона Set3 находится здесь.
Исходники находятся в файле trian3d.cpp.

Наверх