Триангуляция многоугольников на плоскости

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

Функция trianSweepLine использует на первом этапе алгоритм с заметающей прямой:

SuiteRef<Set3<nat> > & trianSweepLine ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );
Здесь vert - это массив вершин простого многоугольника ( обход вершин против часовой стрелки ), а res - массив полученных треугольников, заданных в виде троек индексов.

Функция ttrianSeidel использует на первом этапе алгоритм Зейделя, который позволяет делать триангуляцию многоугольников с дырками. Кроме того, у этого алгоритма зависимость времени выполнения от количества вершин - почти линейная:

SuiteRef<Set3<nat> > & 
trianSeidel ( CArrRef<nat> cntr, CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );
Здесь cntr - это количества вершин многоугольников, vert - общий массив всех вершин, res - треугольники. Внешний многоугольник должен иметь обход вершин против часовой стрелки, а внутренние - по часовой. Порядок перечисления многоугольников произвольный.

В моих экспериментах функция trianSweepLine работала быстрее функции trianSeidel в среднем в 5 раз.

Далее следуют алгоритмы, которые не разбивают исходный многоугольник на монотонные многоугольники.

Шаблон функций tempTrianNat1:

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

template <class Scalar, class Vector> 
nat tempTrianNat1 ( CArrRef<Vector> vert, ArrRef<SemiRib> res )
...

Исходными данными являются: ссылка на массив с вершинами многоугольника и ссылка на массив, куда будет записываться результат. Функция возвращает количество рёбер записанных в массив или, по-другому, количество граней умноженных на 3 ( = 3 * nv - 6 ). В качестве классов-параметров можно использовать пары int-Vector2i, float-Vector2f, double-Vector2d и др.
Структура SemiRib описывает ребро и имеет поля: next - индекс следующего ребра в треугольнике, twin - индекс смежного ребра в соседнем треугольнике ( если соседнего треугольника нет, то twin равен количеству рёбер ), vert - индекс начальной вершины ребра.
Дополнительно известно, что рёбра принадлежащие к одному треугольнику находятся последовательно, и что поле twin меньше количества рёбер только у одного ребра из пары. Эти особенности будут использоваться в других алгоритмах для которых массив res будет входным. Идея алгорима следующая: для треугольника выбираются три соседние вершины такие, что площадь треугольника будет неотрицательной, и новая диагональ не пересечёт ни одну из сторон многоугольника. После нахождения такого треугольника он записывается в результат, а средняя вершина отбрасывается. Если же такой треугольник не найден, то выбирается просто ненулевой треугольник. Если же и такого нет, то берётся произвольный. В результате такой триангуляции могут появляться узкие и даже с нулевой площадью треугольники, поэтому предполагается, что эта триангуляция будет исправляться подходящими алгоритмами. Этот алгоритм требует дополнительной памяти O ( n ) и времени в среднем O ( n 2 ). Вторая оценка определена экспериментально.

Шаблон функций tempTrianNat1L1 вначале вызывает триангуляцию tempTrianNat1, а затем улучшает её при помощи шаблона maxL1:

template <class Scalar1, class Vector, class Scalar2> 
SuiteRef<Set3<nat> > & tempTrianNat1L1 ( const Func3a<Scalar2,nat> & quality,
                                         const Func2a<Scalar2,Scalar2> & merge, 
                                         CArrRef<Vector> vert, SuiteRef<Set3<nat> > & res )
...

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

SuiteRef<Set3<nat> > & 
trianNat1L1MaxMinArea ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );
Исходными данными являются: ссылка на массив с вершинами многоугольника и ссылка на массив, куда будет записываться результат. Её же функция возвращает. Треугольник описывается тремя целыми числами, которые являются индексами массива вершин.

В рассмотренном выше варианте триангуляции могут появляться длинные узкие треугольники. Для того, чтобы этого избежать можно использовать в роли функции качества треугольника отношение удвоенной площади треугольника к сумме квадратов длин сторон ( TQ_AdivR2 ). Это отношение не зависит от размеров треугольника и достигает максимума у равностороннего треугольника. Функция trianNat1L1MaxMinAdivR2 ищет максимин таких качеств, а функция trianNat1L1MaxSumAdivR2 - максимум суммы таких качеств. Для второго случая используется не просто сумма, а сумма с проверкой на неотрицательность ( шаблон PosSum ):
SuiteRef<Set3<nat> > & 
trianNat1L1MaxMinAdivR2 ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianNat1L1MaxSumAdivR2 ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );
Следующие две функции используют в роли функции качества треугольника соответственно минимальный тангенс ( TQ_MinTan ) и минимальный угол ( TQ_MinAngle ). В этом случае функция trianNat1L1MaxMinTan делает триангуляцию Делоне:

SuiteRef<Set3<nat> > & 
trianNat1L1MaxMinTan     ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianNat1L1MaxSumMinAngle( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

Следующие несколько алгоритмов сделаны на основе шаблона maxG1, который осуществляет глобальную оптимизацию:

SuiteRef<Set3<nat> > & 
trianG1MaxMinArea    ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianG1MaxMinAdivR2  ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianG1MaxSumAdivR2  ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianG1MaxMinTan     ( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );

SuiteRef<Set3<nat> > & 
trianG1MaxSumMinAngle( CArrRef<Vector2d> vert, SuiteRef<Set3<nat> > & res );
Происходит полный перебор всех вариантов триангуляции и выбор из них наилучшего по заданному критерию. Недостатками являются: 1) требуемая память зависит от квадрата вершин многоугольника, 2) зависимость времени выполнения от количества вершин - кубическая, 3) если вариантов с наилучшим качеством много, то из них выбирается первый попавшийся.

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

bool trianTestNat1L1Area   ( CArrRef<Vector2d> vert );

bool trianTestNat1L1AdivR2 ( CArrRef<Vector2d> vert );

bool trianTestNat1L1MinTan ( CArrRef<Vector2d> vert );

В этом разделе представлено несколько алгоритмов триангуляции, и у читателя может возникнуть вопрос: "Какой из них мне использовать?" Я рекомендую trianNat1L1MaxMinTan, который делает триангуляцию Делоне, хотя в отдельных случаях может оказаться более предпочтительным какой-нибудь другой. Если же многоугольник с дырками, то здесь подойдёт только триангуляция Зейделя.

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

Описание класса Vector2d смотрите в разделе Вектора на плоскости.
Описание шаблонов классов CArrRef и SuiteRef находится здесь.
Описание шаблона Set3 находится здесь.
Исходники алгоритмов находятся в файле trian2d.cpp.

Наверх