Декомпозиция полигонов на монотонные части Программа верхнего уровня Структура сканирующей линии Переходы Анализ Декомпозиция полигонов на монотонные части В этом разделе представим алгоритм для декомпозиции произвольного полигона на монотонные подполигоны, этот процесс иногда называют регуляризацией. Алгоритм использует сканирование на плоскости для регуляризации n-угольника за время О(n log n). Используя этот алгоритм совместно со способом триангуляции монотонных полигонов, выполняемым за линейное время, мы получим алгоритм для триансуляции произвольного полигон за время О(n log n): сначала выполним декомпозицию заданного полигона на монотонные подполигоны, затем осуществим триангуляцию каждого из них по очереди. Для упрощения описания ниже в этом разделе будем предполагать, что никакие две вершины в полигоне не имеют одинаковой координаты х. В алгоритме применяется подход сканирующей линии: воображаемая прямая идет по плоскости слева направо, пересекая объекты и останавливаясь в точках-событиях - точках на плоскости, достижение которых вызывает изменение состояния алгоритма. При остановке линии происходит обработка соответствующего события. Наш алгоритм основан на определении понятия излома. Вогнутая вершина - вершина, внутренний угол которой превышает 180 градусов - является изломом, если обе ее соседние вершины лежат либо слева, либо справа от нее (рисунок справа). Легко видеть, что никакой монотонный полигон не может содержать излом. Это правило обратимо и выражается следующей теоремой, лежащей в основе алгоритма: Теорема о монотонности полигона: любой полигон, не содержащий излома, является монотонным. Теорема доказывается от противного: если полигон Р немонотонный, тогда в нем есть излом. Предположим, что полигон Р немонотонный и его немонотонность является следствием того, что его верхняя цепочка не является монотонной. Обозначим вершины вдоль верхней цепочки полигона Р как v1, v2,..., vk и пусть vi будет первой вершиной вдоль цепочки такой, что вершина vi+1 будет лежать слева от vi (рисунок справа). Если вершина vi+1 лежит над ребром vi-1vi, тогда vi будет изломом, так что мы предположим, что вершина vi+1 находится под vi-1vi. Пусть vj будет самой левой вершиной цепочки от vi до vk, прежде чем цепочка пересечет ребро vivk . Вершина vj является вогнутой, поскольку она локально самая левая и внутренность полигона лежит слева от нее, эта же вершина vj является изломом, поскольку она вогнутая и обе соседние с ней вершины находятся справа от нее. Таким образом теорема доказана. Программа верхнего уровня Наш алгоритм выполняется путем декомпозиции полигона Р на подполи-гоны без изломов. В первой из двух фаз по мере продвижения сканирующей линии по прямоугольнику R слева направо алгоритм удаляет изломы, направленные влево, формируя набор подполигонов P1, P2,..., Рm ни один из которых не содержит изломов, направленных влево. Во время второй фазы алгоритм удаляет изломы, направленные вправо, продвигая сканирующую линию справа налево по подполигонам Pi по очереди. Полученная коллекция полигонов и будет декомпозицией исходного полигона Р на подполигоны, в которых нет ни право-, ни лево-направленных изломов и, следовательно, совсем никаких изломов. В программу regularize передается полигон р и она возвращает список монотонных полигонов, представляющих регуляризацию исходного полигона р. В процессе работы программы исходный полигон р разрушается. Реализация использует класс кольцевого списка и классы из раздела структуры геометрических данных. В качестве класса Dictionary можно использовать любой словарь, поддерживающий требуемые операции. Например, можно переопределить #define Dictionary RandomizedSearchTree. enum ( LEFT_TO_RIGHT, RIGHT_TO_LEFT); // слева-направо, справа-налево List *regularize(Polygon &p) { // фаза 1 List *polysl = new List; semiregularize(p, LEFT_TO_RIGHT, polys1); // фаза 2 List *polys2 = new List; polysl->last(); while (!polysl->isHead()) { Polygon *q = polysl->remove(); semiregularize(*q, RIGHT_TO_LEFT, polys2); } return polys2; } В этой программе полигоны, создаваемые в первой фазе, накапливаются в списке polysl, а формируемые во второй фазе - в списке polys2. Основное назначение функции semiregularize заключается в исключении всех изломов, направленных в одну сторону. Например, при обращении semiregularize (р, LEFT_TO_RIGHT, polysl) выполняется сканирование полигона р слева направо и удаляются изломы, направленные влево, а получающиеся подполигоны добавляются в список polysl. Каждый раз, когда сканирующая линия обнаруживает направленные влево изломы v, полигон разбивается вдоль хорды, соединяющей v с некоторой вершиной w, расположенной слева от v. Чтобы отрезок прямой линии vw был действительно хордой (т. е. внутренней диагональю) полигона, выбор вершины w должен быть оправданным. Если вершина v лежит между активными ребрами а и d в качестве вершины w выбирается самая правая из тех вершин, что лежат между ребрами а и d и расположены слева от сканирующей линии (рисунок ниже). Выбор вершины w можно пояснить и другим способом: рассмотрим трапецоид, образованный сканирующей линией, ребром а, ребром d и прямой линией, параллельной сканирующей линии и проходящей через точку х. Здесь в качестве точки х можно выбрать левую концевую точку ребер а или d, лежащую правее другой. Вершина w должна быть самой правой вершиной, лежащей внутри этого трапецоида, но если внутри трапецоида нет других вершин, то такой вершиной w будет вершина х. Вершину w будем называть целевой вершиной пары ребер a-d (вертикально соседней пары ребер a и d). На рисунке ниже (б) показаны действия, предпринимаемые, когда сканирующая линия обнаруживает излом v: полигон расщепляется по хорде vw. Ни в одном из полученных новых полигонов вершина и уже не будет изломом - в каждом новом полигоне одна из соседних с v вершин лежит слева, другая - справа. Конечно, такая ситуация обеспечивается при перемещении сканирующей линии слева направо: ни одна из вершин, лежащих слева от сканирующей линии, не может быть изломом, указывающим влево. Переход выполняется каждый раз как только сканирующая линия обнаруживает вершину полигона. Тип перехода зависит от типа вершины, если вершины классифицировать в соответствии с положением их двух соседей относительно направления сканирования: Начальная вершина: обе соседние вершины для вершины и располагаются после сканирующей линии, т. е. в направлении перемещения сканирующей линии. Вершина перегиба: одна из соседних вершин находится сзади от сканирующей линии, другая - впереди. Концевая вершина: обе соседние с и вершины расположены позади сканирующей линии. Три взаимосвязанных перехода - начальный переход, переход при перегибе и концевой переход - показаны на рисунок ниже, где предполагается, что сканирование осуществляется в направлении слева направо. Типы перехода определены в терминах направления сканирования, так что функция semiregularize может быть использована при сканировании в любом направлении. В обращении к функции semiregularize задается произвольный полигон р и указывается направление сканирования: LEFT_TO_RIGHT для обнаружения изломов, указывающих влево, и RIGHT_TO_LEFT для обнаружения изломов, указывающих вправо. Получающиеся в результате подполигоны добавляются в список polys. В функции используются три глобальные переменные: int sweepdirection; // текущее направление сканирования double curx; // текущая позиция сканирующей линии int curtype; // текущий тип перехода void semiregularize(Polygon &p, int direction, List *polys) { sweepdirection = direction; int (*cmp)(Vertex*, Vertex*); if (sweepdirection==LEFT_TO_RIGHT) cmp = leftToRightCmp; else cmp = rightToLeftCmp; Vertex **schedule = buildSchedule(p, cmp); Dictionary sweepline = buildSweepline(); for (int i = 0; i < p.size(); i++) { Vertex *v = schedule[i]; curx = v->x; switch (curtype = typeEvent(v, cmp)) { case START_TYPE: startTransition(v, sweepline); break; case BEND_TYPE: bendTransition(v, sweepline); break; case END_TYPE: endTransition(v, sweepline, polys); break; } } p.setV(NULL); } Точки-события возникают при обнаружении вершин полигона. Поскольку все они известны заранее, то перечень точек-событий записан в массиве вершин, предварительно отсортированном в порядке увеличения координаты х (поэтому нет необходимости в динамической пересортировке словаря). Перечень формируется функцией buildSchedule, которой передается одна из функций сравнения точек leftToRightCmp или rightToLeftCmp в зависимости от направления сканирования: Vertex **buildSchedule(Polygon &p, int(*cmp) (Vertex* , Vertex*)) { Vertex **schedule = new (Vertex*) [p. size()]; for (int i = 0; i < p.size(); i++, p.advance (CLOCKWISE) ) schedule [i] = p.v(); insertionSort (schedule, p.size(), cmp); // сортировка с функцией сравнения cmp return schedule; } Чтобы определить, какой тип перехода должен быть соотнесен с данной вершиной, в функции semiregularize используется функция typeEvent. Для классификации вершины v функция typeEvent проверяет положение двух соседних с ней вершин относительно направления сканирования: int typeEvent (Vertex *v, int (*cmp) (Vertex* , Vertex*) ) { int a = (*cmp) (v->cw(), v); int b = (*cmp) (v->ccw(), v); if ((a <= 0) && (b <= 0)) return END_TYPE; else if ( (a > 0) && (b > 0) ) return START_TYPE; else return BEND_TYPE; } Вперед  >>>  1  2  3   8  Комментарии к статье  8 8  Обсудить в чате