По книге Laszlo
"Вычислительная геометрия и компьютерная графика на С++"

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

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

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

Доказательство теоремы ведется на основе индукции числа n, количества сторон полигона. Теорема тривиально справедлива для n = 3, что является основой для индукции. Так что пусть Р будет полигон с числом сторон n >= 4 и предположим (в качестве гипотезы индукции), что условия теоремы удовлетворяются для всех полигонов с числом сторон меньше, чем n. Будем искать хорду полигона Р.

Пусть b будет некоторая выпуклая вершина и пусть а и b будут ее соседи. Могут возникнуть две ситуации (рис. 1). В первом случае диагональ ac является хордой Р. Пусть Р' будет n-1-сторонний полигон, получающийся в результате отсечения треугольника abc. По гипотезе индукции существует набор из n - 4 хорд, которые делят полигон на n - 3 треугольников.

Добавляя к ним хорду ac и треугольник abc, мы получим набор из n-2 хорд, которые делят исходный полигон Р на n—2 треугольника.

Во втором случае диагональ ac не является хордой Р, полагая, что внутрь треугольника abc должна попасть по крайней мере одна вершина полигона Р. Из всех вершин внутри треугольника abc пусть d будет вершиной, расположенной дальше всех от прямой линии со, . Эту вершину d будем называть вторгающейся вершиной. При таком выборе вершины d диагональ bd должна лежать внутри Р — ибо если бы какое-либо другое ребро полигона вторглось бы между b и d, то по крайней мере один из его концов должен находиться внутри треугольника abc на расстоянии от прямой са дальше, чем вершина d, что противоречило бы нашему выбору d. Следовательно, отрезок bd должен быть хордой. Теперь хорда bd делит полигон Р на два меньших полигона P₁ и Р₂ с n₁ и n₂ сторонами соответственно. Поскольку n₁ + n₂ = n + 2 и n₁,n₂>=3, то каждое из n₁ и n₂ должно быть меньше n. Теперь мы можем применить гипотезу индукции к P₁ и к P₂. Подсчет числа хорд приводит к (n₁ - 3) + (n₂ - 3) + 1 = n - 3 хордам, а подсчет треугольников — к общему числу (n₁ - 2) + (n₂ - 2) = n - 2 треугольников. Теорема о триангуляции доказана.

^* - Реализация использует классы, описанные в разделе 'Структуры геометрических данных'.

Вышеприведенное доказательство теоремы прямо подводит к следующей программе для триангуляции полигонов. Программе передается полигон р и она возвращает список треугольников, представляющих его триангуляцию. Треугольники накапливаются в списке triangles:

List<Polygon*> *triangulate (Polygon  &p)
{
  List<Polygon*> *triangles = new List<Polygon*>;
  if   (p.size() == 3)
    triangles->append(&p);
  else {
    findConvexVertex(p);
    Vertex *d = findIntrudingVertex(p);
    if (d == NULL) {        // нет вторгающихся вершин
      Vertex  *c = p.neighbor(CLOCKWISE);
      p.advance (COUNTER_CLOCKWISE);
      Polygon *q = p.split(c);
      triangles->append(triangulate(p));
      triangles->append(q);
    } else {                  // d - вторгающаяся вершина
      Polygon   *q = p.split(d);
      triangles->append (triangulate (*q));
      triangles->append (triangulate (p));
    }
  }
  return triangles;
}

Используются функции findConvexVertex и findIntrudingVertex. При обработке полигона р функция findConvexVertex перемещает окно в полигоне р на некоторую выпуклую вершину. Это реализуется путем перемещения трех окон a, b и с, расположенных над тремя соседними вершинами, в направлении по часовой стрелке вокруг полигона до тех пор, пока не будет обнаружен поворот направо в вершине b:

void findConvexVertex (Polygon &p)
{
  Vertex *a = p.neighbor (COUNTER_CLOCKWISE);
  Vertex *b = p.v();
  Vertex *c = p.neighbor (CLOCKWISE);
  while (c->classify(*a, *b) != RIGHT) {
    a = b;
    b = p.aduance(CLOCKWISE);
    с = p.neighbor(CLOCKWISE);
  }
}

В функцию findlntrudingVertex передается полигон p, для которого предполагается, что его текущая вершина является выпуклой. Функция возвращает указатель на вторгающуюся вершину, если она существует или NULL в противном случае.

Vertex  *findIntrudingVertex (Polygon &p)
{
  Vertex *a = p.neighbor(COUNTER_CLOCKWISE);
  Vertex *b = p.v();
  Vertex *c = p.advance (CLOCKWISE);
  Vertex *d = NULL;     // лучший кандидат на данный момент
  double bestD = -1.0;  // расстояние до лучшего кандидата
  Edge ca(c->point(), a->point());
  Vertex *v = p.advance (CLOCKWISE);
  while (v != a) {
    if (pointInTriangle(*v, *a, *b, *c)) {
      double dist = v->distance (ca);
      if (dist > bestD) {
        d = v;
        bestD = dist;
      }
    }
    v = p.advance (CLOCKWISE);
  }
  p.setV(b);
  return d;
}

Функция pointInTriangle проверяет точки на попадание внутрь треугольника: функция возвращает значение TRUE, если точка р находится внутри треугольника с вершинами в точках а, b и с, в противном случае возвращаемое значение равно FALSE.

bool pointInTriangle (Point p, Point a, Point b, Point c)
{
  return ((p.classify (a, b) != LEFT) &&
        (p.classify(b, c) != LEFT) &&
        (p.classify(c, a) != LEFT));
}

При обработке n-угольника каждая из функций findConvexVertex и findIntrudingVertex затрачивает время О(n). Если не найдено ни одной вторгающейся вершины, то одиночный треугольник удаляется из п-угольника и подвергается рекурсивной триангуляции результирующий n-1-угольник. В худшем случае вторгающаяся вершина никогда не обнаруживается в процессе выполнения программы и размер полигона уменьшается на единицу на каждом последующем шаге. Это приводит к времени работы в худшем случае Т(n) = n + (n -1) + ... + 1, что равно O(n²). Такой самый плохой показатель получается при триангуляции выпуклого полигона.

Похоже, что программа будет работать значительно быстрее, если обнаруживается вторгающаяся вершина, поскольку в этом случае задача разбивается на две подзадачи, вполне возможно, примерно равного размера. Поскольку только вогнутая вершина может вторгаться в треугольник, то программа работает быстрее, если полигон имеет много вогнутых вершин. Однако не представляет труда составить такой полигон с Omega(n) вогнутыми вершинами, для триангуляции которого потребуется время Omega(n²), хотя вогнутые вершины и существуют, но алгоритм их не обнаруживает или находит такие "плохие", что они приводят к разбиению на очень неравные части, одну большую, а другую маленькую.