Переходы Рассмотрим теперь, как обрабатывать переходы, начиная с первого. Когда сканирующая линия достигает начальной вершины v, то мы должны сначала отыскать в структуре сканирующей линии два активных ребра a и d, между которыми лежит вершина v. Если вершина v является точкой встречи ребер b и с, то b и с заносятся в структуру сканирующей линии и вершина v будет считаться целевой вершиной для пар ребер а-b, b-с и c-d. Кроме того, если вершина v является вогнутой (означающее, что v является изломом), то полигон, которому принадлежит вершина v, расщепляется вдоль хорды, соединяющей вершины v и w. В результате получается функция startTransition: void startTransition (Vertex* v, Dictionary &sweepline) { ActivePoint ve (v->point()); ActiveEdge *a = (ActiveEdge*) sweepline.locate(&ve); Vertex *w = a->w; if ( !isConvex (v) ) { Vertex *wp = v->split (w); sweepline.insert (new ActiveEdge (wp->cw(), CLOCKWISE, wp->cw()) ); sweepline.insert (new ActiveEdge (v->ccw(), COUNTER_CLOCKWISE, v) ); a->w = (sweepdirection==LEFT_TO_RIGHT) ? wp->ccw():v; } else { sweepline.insert (new ActiveEdge (v->ccw(), COUNTER_CLOCKWISE,v) ); sweepline.insert (new ActiveEdge (v, CLOCKWISE, v)); a->w = v; } } Разбиение полигона v в функции startTransition выполняется с помощью функции Vertex::split, вместо Polygon::split, поэтому нет необходимости знать, какому полигону принадлежит вершина v. По мере перемещения сканирующей линии в сторону вершины v в результате выполнения операции split формируются новые полигоны и вершина v может мигрировать из одного полигона в другой. Работая на уровне вершин, а не погигонов, мы можем избежать необходимости отслеживать, какому полигону принадлежит каждая вершина. При обращении к функции isConvex(v) возвращается значение TRUE, если вершина v выпуклая, или значение FALSE в противном случае (вершина v вогнутая). Функция определяется в виде: bool isConvex (Vertex *v) { Vertex *u = v->ccw(); Vertex *w = v->cw(); int с = w->classify (*u, *v); return ( (c == BEYOND) I I (c == RIGHT) ); } Для обработки перехода для точки перегиба в вершине перегиба v сначала требуется найти в структуре сканирующей линии ребра a, b и с и принять вершину v в качестве целевой вершины для пар ребер а-b и b-с. Затем ребро b в структуре сканирующей линии заменяется на ребро b', которое встречается с ребром b в вершине v. Таким образом получаем функцию bendTransition: void bendTransition (Vertex *v, Dictionary &sweepline) { ActivePoint ve(v->point()); ActiveEdge *a = (ActiveEdge*) sweepline.locate(&ve); ActiveEdge *b = (ActiveEdge*) sweepline.next(); a->w = v; b->w = v; b->v = b->v->neighbor (b->rotation); } Для обработки концевого перехода в концевой вершине и сначала в структуре сканирующей линии найдем активные ребра а, b, с и d (рис. 4в). С одной стороны, если вершина v выпуклая, тогда v должна быть самой крайней правой вершиной полигона. Если это не так, то полигон, которому принадлежит вершина и, должен был бы обладать изломом, указывающим влево и расположенным слева от и, что противоречило бы условию сканирования. Поскольку вершина v является самой правой вершиной в полигоне, то на этот раз полигон добавляется в список polys. С другой стороны, если вершина v вогнутая, то v становится целевой вершиной для пары ребер a-d, а ребра b is. с удаляются из структуры сканирующей линии. Функцию endlransition получаем в следующем виде: void endTransition (Vertex *v, Dictionary &sweepline, List *polys) { ActivePoint ve(v->point()); ActiveElement *a = sweepline.locate (&ve); ActiveEdge *b = (ActiveEdge*) sweepline.next(); ActiveEdge *c = (ActiveEdge*) sweepline.next(); if (isConvex(v) ) polys->append(new Polygon (v) ); else ((ActiveEdge*) a)->w = v; sweepline.remove (b); sweepline.remove (c); } На рисунке ниже показан результат регуляризации 25-угольника. При сканировании слева направо удаляются четыре излома, направленных влево, и один - направленный вправо (одна из операций расщепления split удаляет два излома одновременно). При последующем сканировании справа налево удаляются два оставшихся излома, направленных вправо, и получаются семь монотонных полигонов. Каждый из этих полигонов подвергается триангуляции с использованием алгоритма для монотонных полигонов. Анализ Проведем анализ работы программы regularize для входного полигона, имеющего п вершин. По мере выполнения программы после ряда последовательных обращений к функции semiregularize общее число вершин увеличивается на две вершины после каждого выполнения операции расщепления split. Однако, поскольку не более, чем n/2 вершин исходного полигона могут быть изломами, то может быть добавлено не более, чем 2(n/2) = n вершин, что дает в результате не более 2n вершин. Так как каждая вершина может возбудить не более двух переходов (по одному на каждое направление сканирования), то всего может потребоваться выполнить не более 4n переходов. Время выполнения перехода каждого типа определяется в основном небольшим постоянным числом операций со словарем, что занимает время O(log n). Поскольку всего выполняется О(n) переходов, то весь алгоритм выполняется за время О(n log n). <<<  Назад  1  2  3   8  Комментарии к статье  8 8  Обсудить в чате