:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Многоугольники »
На правах рекламы
По низким ценам кондиционеры москва для всех со скидками.
  Триангуляция монотонных полигонов



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

Реализация использует класс стек и структуры геометрических данных.


  Что такое монотонный полигон?



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

Полигон называется монотонным, если его граница составлена из двух монотонных цепочек вершин: верхней и нижней цепочек вершин полигона. Каждая цепочка заканчивается в самой левой и в самой правой вершинах полигона и содержит либо ни одной, либо несколько вершин между ними. На рис. 1 показано несколько примеров. Заметим, что (обязательно непустое) пересечение вертикальной прямой линии и монотонного полигона состоит либо из отрезка прямой вертикальной линии, либо из точки.
Два монотонных полигона. Верхняя цепочка полигона (б) состоит из единственного ребра
Рис. 1: Два монотонных полигона. Верхняя цепочка полигона (б) состоит из единственного ребра

  Алгоритм триангуляции



Пусть р будет монотонный полигон и переименуем его вершины как v1, v2,..., vn в порядке увеличения координаты х, поскольку наш алгоритм будет обрабатывать эти вершины именно в таком порядке. Алгоритм формирует последовательность монотонных полигонов р = p1, p2,... , pn = 0. Полигон pi, как результат обработки вершины vi, получается путем отсечения нуля или нескольких треугольников от предыдущего полигона pi-1. Алгоритм заканчивает свою работу после выхода с pm, пустым полигоном, а коллекция треугольников, накопленная в процессе обработки, представляет собой триангуляцию исходного полигона р.

Алгоритм хранит стек s вершин, которые были проверены, но еще не обработаны полностью (возможно, обнаружены еще не все треугольники, связанные с этой вершиной). Перед началом обработки вершины vi в стеке содержатся некоторые вершины, принадлежащие полигону pi-1. По мере выполнения алгоритма сохраняются определенные инварианты стека(Инвариантом называется состояние, существующее на определенной стадии работы алгоритма, например, в начале каждой итерации данного цикла). Пусть вершины в стеке обозначены как s1, s2,..., st в порядке снизу вверх, тогда могут встретиться четыре ситуации:

  1. s1, s2,..., st упорядочены по возрастанию координаты х и содержат каждую из вершин полигона pi-1, расположенную справа от s1 и слева от st.
  2. s1, s2,..., st являются последовательными вершинами либо в верхней, либо в нижней цепочках полигона pi-1.
  3. Вершины s1, s2,..., st являются вогнутыми вершинами полигона pi-1 (величина внутреннего угла при каждой из них превышает 180 градусов).
  4. Следующая подлежащая обработке вершина vi в полигоне pi-1 находится в следующем соотношении с вершинами st и s1:
    • a. vi соседняя с st, но не с s1,
    • б. vi соседняя с s1, но не с st,
    • в. vi соседняя с обеими вершинами s1 и st.

Все эти три случая условия 4 показаны на рис. 2.

Действия по обработке вершины vi будут различны для каждого из этих трех случаев, отражающих текущее состояние стека:

Три случая, которые могут возникнуть при триангуляции монотонного полигона: Вершина v(a) - соседняя с s<sub>t</sub>, но не с s<sub>1</sub>; (б) — соседняя с s<sub>1</sub>, но не с s<sub>t</sub>; (в)—соседняя с обеими вершинами s<sub>1</sub> и s<sub>t</sub>
Рис. 2: Три случая, которые могут возникнуть при триангуляции монотонного полигона: Вершина v(a) - соседняя с st, но не с s1; (б) — соседняя с s1, но не с st; (в)—соседняя с обеими вершинами s1 и st

Случай 4а. Вершина vi соседняя с st, но не с s1: Если t > 1 и внутренний угол vistst-1 меньше 180 градусов, то отсекается треугольник vistst-1 и st исключается из стека. После этого в стек заносится vi. В алгоритме используется тот факт, что угол vistst-1 < 180 только в том случае, когда либо st-1 лежит слева от вектора vist, если vi принадлежит полигону pi-1 из верхней цепочки, либо st-1 лежит справа от вектора vist, если vi принадлежит нижней цепочке.

Ядром полигона называется подмножество его точек, из которых виден весь полигон. В частности, ядро выпуклого полигона - он сам. Полигон называется веерообразным, если ядро содержит одну или более вершин - корней полигона.

Случай 46. Вершина vi соседняя с s1, но не с st. Отсекаем полигон, определяемый вершинами vi, s1, s2,..., st, очищаем стек и затем заносим в него сначала st, потом vi. Полигон, определяемый вершинами vi, s1, s2,..., st фактически является веерообразным с узлом в точке vi (т. е. вершина vi принадлежит корню веера). После этого алгоритм выполняет триангуляцию полученного полигона.

Случай 4в.

Вершина vi соседняя с обеими вершинами s1 и st:

В этом случае vi = vn и полигон pi-1, определяемый вершинами vi, s1, s2,..., st, является веерообразным с узлом в точке vn. Алгоритм непосредственно выполняет триангуляцию этого полигона и заканчивается.

На рис. 3 показан процесс работы алгоритма при решении простой задачи (порядок выполнения шагов сверху вниз и слева направо). На каждом шаге обрабатываемые вершины отмечены кружком, а вершины в стеке обозначены последовательностью s1, s2,..., st.

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

enum ( UPPER, LOWER );

List<Polygon*> *triangulateMonotonePolygon(Polygon &p}
{
  Stack<Vertex*> s;
  List<Polygon*> *triangles = new List<Polygon*>;
  Vertex *v, *vu, *vl;
  leastVertex(p, leftToRightCmp);
  v = vu = vl = p.v();
  s.push(v);
  int chain = advancePtr(vl, vu, v);
  s.push(v);
  while (1) {                                           // внешний цикл while
    chain = advancePtr(vl, vu, v);
    if (adjacent(v, s.top()) && !adjacent(v, s . bottom ())) {// случай 4a
      int side = (chain == UPPER) ? LEFT : RIGHT;
      Vertex *a = s.top();
      Vertex *b = s.nextToTop();
      while ((s. size() > 1) &&
       (b->classify(v->point() ,a->point() ) == side)) {
        if (chain == UPPER) {
          p.setV(b);
          triangles->append (p.split(v) );
        } else {
          p.setv (v);
          triangles->append (p.split(b) );
        }
        s.pop();
        a = b;
        b = s.nextToTop();
      }
      s.push (v);
    } else if (! adjacent (v, s.top())) {                     // случай 4б
      Polygon *q;
      Vertex *t = s.pop();
      if (chain == UPPER) {
        p.setV(t);
        q = p.split(v);
      } else {
        p.setV(v);
        q = p.split(t);
        q->advance(CLOCKWISE);
      }
      triangulateFanPolygon (*q, triangles);
      while (! s.empty ())
        s.pop();
      s.push(t);
      s.push(v);
    } else {	                                              // случай 4в 
      p.setV (v);
      triangulateFanPolygon (p, triangles);
      return triangles;
    }
  }                                           // конец внешнего цикла while
}

Функция adjacent возвращает значение TRUE только в том случае, если две указанные в обращении вершины, являются соседними.

bool adjacent (Vertex  *v, Vertex  *w)
{
  return ( (w == v->cw() ) || (w = v->ccw()));
}
Триангуляция небольшого монотонного полигона. Треугольники, обнаруженные на каждом шаге, выделены толстыми линиями. Порядок выполнения шагов сверху вниз, слева направо
Рис. 3: Триангуляция небольшого монотонного полигона. Треугольники, обнаруженные на каждом шаге, выделены толстыми линиями. Порядок выполнения шагов сверху вниз, слева направо

Программа triangulateMonotonePolygon при обработке полигона р анализирует одновременно верхнюю и нижнюю цепочки полигона, используя преимущества уже выполненного упорядочения вершин по возрастанию координаты х (в противном случае потребовалась бы дополнительная сортировка за время О(n log n)). На каждой итерации переменная v указывает на обрабатываемую вершину. В программе формируются еще две переменные vu и vl, которые указывают на последнюю обрабатываемую вершину в верхней и нижней цепочках полигона р соответственно. По мере работы программы эти указатели функцией advancePtr продвигаются слева направо. При каждом обращении к функции advancePtr она изменяет значение либо vu, либо vl и корректирует указатель v в соответствии с произведенным изменением:

int advancePtr(Vertex* &vu, Vertex* &vl, Vertex* &v}
{
  Vertex *vun = vu->cw();
  Vertex *vln = vl->ccw();
  if (vun->point() < vln->point()) {
    v = vu = vun;
    return UPPER;
  } else {
    v = vl = vln;
    return LOWER;
  }
}

Функция advancePtr возвращает значение UPPER или LOWER, показывающее, к какой из двух цепочек вершин v относится произведенное действие. Это значение используется в программе triangulateMonotonePolygon для контроля, чтобы ее последующее обращение к функции split вызывало возврат части, выделенной из основного полигона, а не основного полигона, из которого эта часть исключена.

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

void triangulateFanPolygon(Polygon &p, List<Polygon*> *triangles)
{
  Vertex *w = p.v()->cw()->cw();
  int size = p.size();
  for (int i = 3; i < size; i++) {
    triangles—>append(p.split(w));
    w = w—>cw();
  }
  triangles->append(&p);
}

На рис. 4 показана триангуляция, полученная с помощью описанного алгоритма. Монотонный полигон содержит 35 вершин.

Триангуляция монотонного 35-угольника
Рис. 4: Триангуляция монотонного 35-угольника

  Корректность



Нам необходимо доказать два положения: (1) каждая диагональ, которую алгоритм находит на шаге i, является внутренней хордой для полигона pi-1 (2) алгоритм восстанавливает четыре состояния стека при переходе от одной итерации к следующей. (То, что найденные хорды преобразуют исходный полигон в треугольники, очевидно из рис. 3).

Сначала рассмотрим диагональ vist-1 на рис. 3а (здесь t = 5). Обозначим треугольник Т = st-1stvi и заметим, что ни одна из вершин полигона pi-1 не может лежать внутри Т: вершины s0,..., st-2 расположены слева от самой левой вершины st-1 треугольника Т, а вершины vj для j > i лежат справа от самой правой вершины vi треугольника Т. Следовательно, любое ребро, пересекающее диагональ vist-1, должно выходить из треугольника Т через одно из ребер st-1st или stvi, что невозможно, поскольку они являются граничными ребрами полигона pt-1. Таким образом, диагональ vist-1 является хордой. Отсечем треугольник Т от полигона pi-1. Те же аргументы показывают, что оставшиеся диагонали, получаемые в случае 4а, также являются хордами.

Теперь рассмотрим случай 46, показанный на рис. 36. Согласно условиям 2 и 3 для стека, полигон Т, определяемый вершинами vi, s1, s2,..., st, является веерообразным с корнем в вершине vi. Заметим, что ни одна из вершин полигона pi-1 не может лежать внутри полигона Т — если бы там оказалась одна или несколько вершин, то самая правая из таких вершин должна бы оказаться записанной в стеке и следовательно находиться на границе полигона pi-1. Поскольку внутри Т нет ни одной вершины, то любое ребро, пересекающее vist, должно также пересекать одно из ребер vis1, s1s2 , ... , st-1st , что невозможно, поскольку они являются граничными ребрами полигона pi-1. Аналогично также можно показать, что в случае 4в (рис. 3в) полигон pi-1 является веерообразным с корнем в вершине vi и внутри него нет ни одной другой вершины.

Затем докажем, что условия стека сохраняются от одной итерации к другой. По крайней мере две вершины vi и st должны быть записаны в стеке с обязательным учетом порядка их расположения по горизонтали. Тем самым удовлетворяется условие 1. Вершины образуют цепочку вершин в pi-1 по индукции (в случае 4а) или вследствие того, что стек сокращен до двух соседних вершин (в случае 46), тем самым оказывается удовлетворенным условие 2. Вершины стека являются вогнутыми (за исключением верхней и нижней вершин), поскольку вершина vi записывается в стек только в том случае, если верхняя вершина стека (над которой будет записана новая вершина) станет вогнутой. Следовательно, в этом случае удовлетворяется условие 3 (при этом безусловно удовлетворяется случай 46, поскольку в стеке содержатся лишь две вершины). Наконец, вершина st должна быть соседней либо s1, либо st, поскольку монотонность полигона pi-1 гарантирует, что вершина vi имеет соседа слева, а все вершины в стеке за исключением s1 и st уже имеют двух соседей. Следовательно, удовлетворяется условие 4 для стека.


  Анализ



Программа triangulateMonotonePolygon выполняется за время Theta(n), если задаваемый на входе полигон содержит n вершин. Для получения верхней границы О(n) заметим, что при каждой итерации двух внутренних циклов while из стека исключается одна вершина (в случаях 4а и 46). Однако каждая вершина записывается в стек только однажды (при первой ее обработке) и, следовательно, может быть выбрана из стека тоже только однажды. Поскольку алгоритм выполняет О(n) операций со стеком одинаковой длительности и затрачивает одинаковое время между двумя такими последовательными операциями, то время работы программы пропорционально О(n). Нижняя граница определяется тем, что должна быть обработана каждая из n вершин.