|
Пусть р будет монотонный полигон и переименуем его вершины как 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 показаны на рис. 2.
Действия по обработке вершины vi будут различны для каждого из этих трех случаев, отражающих текущее состояние стека:
Рис. 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 вершин.
Рис. 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 для стека.
|
