Реализация использует класс стек и структуры геометрических данных. Что такое монотонный полигон? Говорят, что цепочка вершин монотонная, если любая вертикальная линия пересекает ее не более одного раза. Начиная с самого левого конца, все вершины монотонной цепочки расположены в порядке увеличения их координаты x. Полигон называется монотонным, если его граница составлена из двух монотонных цепочек вершин: верхней и нижней цепочек вершин полигона. Каждая цепочка заканчивается в самой левой и в самой правой вершинах полигона и содержит либо ни одной, либо несколько вершин между ними. На рисунке ниже показано несколько примеров. Заметим, что (обязательно непустое) пересечение вертикальной прямой линии и монотонного полигона состоит либо из отрезка прямой вертикальной линии, либо из точки. Алгоритм триангуляции Пусть р будет монотонный полигон и переименуем его вершины как v1, v2,..., vn в порядке увеличения координаты х, поскольку наш алгоритм будет обрабатывать эти вершины именно в таком порядке. Алгоритм формирует последовательность монотонных полигонов р = p1, p2,... , pn = 0. Полигон pi, как результат обработки вершины vi, получается путем отсечения нуля или нескольких треугольников от предыдущего полигона pi-1. Алгоритм заканчивает свою работу после выхода с pm, пустым полигоном, а коллекция треугольников, накопленная в процессе обработки, представляет собой триангуляцию исходного полигона р. Алгоритм хранит стек s вершин, которые были проверены, но еще не обработаны полностью (возможно, обнаружены еще не все треугольники, связанные с этой вершиной). Перед началом обработки вершины vi в стеке содержатся некоторые вершины, принадлежащие полигону pi-1. По мере выполнения алгоритма сохраняются определенные инварианты стека(Инвариантом называется состояние, существующее на определенной стадии работы алгоритма, например, в начале каждой итерации данного цикла). Пусть вершины в стеке обозначены как s1, s2,..., st в порядке снизу вверх, тогда могут встретиться четыре ситуации: s1, s2,..., st упорядочены по возрастанию координаты х и содержат каждую из вершин полигона pi-1, расположенную справа от s1 и слева от st. s1, s2,..., st являются последовательными вершинами либо в верхней, либо в нижней цепочках полигона pi-1. Вершины s1, s2,..., st являются вогнутыми вершинами полигона pi-1 (величина внутреннего угла при каждой из них превышает 180 градусов). Следующая подлежащая обработке вершина vi в полигоне pi-1 находится в следующем соотношении с вершинами st и s1: a. vi соседняя с st, но не с s1, б. vi соседняя с s1, но не с st, в. vi соседняя с обеими вершинами s1 и st. се эти три случая условия 4 показаны на рисунке ниже. Действия по обработке вершины vi будут различны для каждого из этих трех случаев, отражающих текущее состояние стека: Случай 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. Алгоритм непосредственно выполняет триангуляцию этого полигона и заканчивается. На рисунке ниже показан процесс работы алгоритма при решении простой задачи (порядок выполнения шагов сверху вниз и слева направо). На каждом шаге обрабатываемые вершины отмечены кружком, а вершины в стеке обозначены последовательностью s1, s2,..., st. Для приведенной ниже программы triangulateMonotonePolygon задается монотонный полигон р и она возвращает список треугольников, представляющий результат триангуляции полигона. В программе предполагается, что окно для полигона р расположено на его самой левой вершине. enum ( UPPER, LOWER ); List *triangulateMonotonePolygon(Polygon &p} { Stack s; List *triangles = new List; 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())); } Программа 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); } На рисунке ниже показана триангуляция, полученная с помощью описанного алгоритма. Монотонный полигон содержит 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 вершин.  8  Комментарии к статье  8 8  Обсудить в чате