Пиши Дома Нужные Работы

Обратная связь

Алгоритмы построения выпуклых оболочек

Лабораторная работа № 1

Цель работы: научиться строить выпуклые оболочки

Задачи:. реализовать алгоритмы построения выпуклой оболочки: при пошаговом вводе точек, методом "заворачивания подарка", методом Грэхема

Алгоритмы построения выпуклых оболочек

1. Ввод оболочки.

Ввод оболочки представляет собой специальный подход к поиску выпуклой оболочки для конечного набора точек S путем последовательного ввода по одной точке и поддержание выпуклой оболочки для всех точек, введенных до этого момента. Такую оболочку будем называть текущей оболочкой. Вначале текущая оболочка состоит из одной точки, принадлежащей S. По завершении ввода всех точек текущая оболочка становится эквивалентной выпуклой оболочке CH(S) и задача оказывается решенной.

При вводе каждой новой точки s в текущую оболочку могут возникнуть две ситуации. В первом случае точка s может принадлежать текущей оболочке (находиться на ее границе или внутри) и тогда текущую оболочку изменять не требуется.

Во втором случае точка s лежит вне текущей оболочки и ее требуется модифицировать, как показано, например, на рис. 5.6. Через точку s могут

Рис. 5.6. Включение точки s в текущую оболочку.

быть проведены две вспомогательные прямые линии, каждая из которых образует касательную к текущей оболочке. (Линия является касательной к выпуклому полигону P, если она проходит через вершину Р и внутренняя область полигона Р полностью лежит по одну сторону от этой прямой линии). Левая (правая) касательная проходит через некоторую вершину l(r) текущей оболочки и лежит слева (справа) от текущей оболочки. Если наблюдатель находится в точке s и смотрит на выпуклую оболочку, то левая касательная будет видна слева, а правая касательная - справа.



Две вершины l и r, через которые проходят касательные, делят границу текущей оболочки на две цепочки вершин: ближняя цепочка, которая расположена ближе к точке s, и дальняя цепочка, которая находится дальше от точки s. (Ближняя цепочка расположена с той же стороны от отрезка прямой , что и точка s, дальняя цепочка располагается по другую сторону от отрезка ). Для модификации текущей оболочки сначала необходимо найти две вершины l и r, определяющие границу между ближней и дальней цепочками. Затем мы должны удалить вершины ближней цепочки (за исключением вершин l и r) и внести точку sв нужном месте.

Следующая программа insertionHull возвращает текущую оболочку для массива s из n точек:

Point somePoint; // global
Polygon *insertionHull (Point s[], int n)
{Polygon *p = new Polygon;
p->insert(s[0]);
for (int i = 1; i < n; i++)
{if (pointInConvexPolygon(s[i], *p))
continue;
somePoint = s[i];
leastVertex(*p, closestToPolygonCmp) ;
supportingLine(s[i], p, LEFT);
Vertex *l = p->v();
supportingLine(s[i], p, RIGHT);
delete p->split(l);
p->insert(s[i]);
}
return p;
}

На шаге i точка s[i] вносится в текущую оболочку р. Обращение к функции leastVertexперемещает окно полигона p на вершину, которая расположена ближе всего к точке s[i]. При этом осуществляется подготовка к последующему обращению supportingLine(s[i], р, LEFT), переносящему окно на вершину l через которую проходит левая касательная. При втором обращении к функции supportingLine окно перемещается на вершину r. Операция расщепления split применяется для удаления полигона p по его диагонали , отделяя таким образом ближнюю цепочку от дальней. Часть полигона, содержащая ближнюю цепочку, возвращается функцией split и удаляется. После этого точка s[i] вставляется в полигон p, который, после выполнения функции split, состоит только из дальней цепочки.

Рассмотрим функцию supportingLine более детально. Для определения вершины l, через которую проходит левая касательная, начнем с некоторой вершины в ближней цепочке и затем будем совершать обход по часовой стрелке вдоль текущей оболочки до тех пор, пока не дойдем до первой вершины v, последователь которой не лежит ни слева, ни после направленного отрезка прямой линии . Вершина v и будет вершиной l, которую мы ищем. Заметим, что если последователь для вершины v (например, вершина w) располагается за отрезком , то процесс поиска продолжается, поскольку вершина и не может быть крайней точкой, если она лежит между точками s и w.

При обращении к функции supportingLine в качестве аргументов задается полигон p, точка sвне полигона p и один из параметров типа перечисления LEFT или RIGHT (слева или справа), показывающий, какая из вершин (l или r) имеется в виду. Предполагается, что вершина, находящаяся в окне для полигона p, принадлежит ближней цепочке, что обеспечивается предварительным обращением к функции leastVertex. Функция перемещает окно полигона p на вершину, которую она находит (l или r):

void supportingLine(Point &s, Polygon *p, int side}
{int rotation = (side==LEFT) ? CLOCKWISE : COUNTER_CLOCKWISE;
Vertex *a = p->v () ;
Vertex *b = p->neighbor(rotation) ;
int с = b->classify(s, *a);
while ((c == side) ||(c == BEYOND)||(c = BETWEEN))
{p->advance(rotation);
a = p->v() ;
b = p->neighbor(rotation);
с = b->classify(s, *a); //в первоисточнике после ";" находился символ "{",возможно опечатка
}
}

Функция leastVertex, описанная в подразделе 4.3.6, используется программой insertionHullдля нахождения в полигоне p вершины, расположенной ближе всего к точке, хранящейся в глобальной переменной somePoint. Функция сравнения closestToPolygonCmp, вместе с которой вызывается функция leastVertex, сравнивает две точки и выбирает, какая из них находится ближе к точке somePoint:

int closestToPolygonCnp(Point *a, Point *b)
{double distA = (somePoint - *a).length();
double distB = (somePoint - *b).length();
if(distA < distB)
return -1;
else
if (distA > distB)
return 1;
return 0;
}

2. Построение выпуклой оболочки: метод обхода Грэхема.

В этом разделе мы раскроем сущность способа построения выпуклой оболочки по методу обхода Грэхема, названному так по имени его создателя. В методе обхода Грэхема выпуклая оболочка конечного набора точек S находится в два этапа. На первом этапе предварительной сортировки алгоритм выбирает экстремальную точку и сортирует остальные точки S в соответствии с углом направленного к ним луча относительно точки . На этапе построения выпуклой оболочки алгоритм выполняет пошаговую обработку отсортированных точек, формируя последовательность текущих выпуклых оболочек,которые в конце концов образуют искомую выпуклую оболочку CH(S). Предварительная сортировка упрощает выполнение этапа построения выпуклой оболочки - каждая обрабатываемая на этом этапе точка включается в текущую оболочку без дополнительных условий. Более того, при этом оказывается очень легко обнаружить те точки, которые следует

Рис. 6.2. Обозначение точек на основе их полярной координаты относительно точки .

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

Для заданного набора точек S при методе обхода Грэхема сначала находится некоторая экстремальная точка . Выберем в качестве такой точки точку из S с минимальной координатой y или самую правую в случае сильно вытянутого набора. Затем остальные точки сортируются в порядке полярного угла относительно точки . Если две точки имеют одинаковый полярный угол, то точка, расположенная ближе к точке , считается меньшей, чем более дальняя точка. Это обычное словарное правило для определениясоотношения точек по их полярной координате относительно точки . котороереализуется функцией сравнения polarCmp, приведенной в разделе 5.2. Переименуем теперь оставшиеся точки в соответствии с их упорядочением, как показано на рис. 6.2.

На этапе построения выпуклой оболочки при методе Грэхема текущая выпуклая оболочка строится на основе уже обработанных точек. На рис. 6.3 показан процесс работы алгоритма. Рассмотрим обработку точки (рис. 6.Зе). Поскольку точки упорядочены в порядке возрастания полярного угла относительно точки , то очевидно, что точка должна быть включена в состав оболочки и что точка должна быть ее предшественницей, но какая точка будет включена после точки ? Для ответа на этот вопрос используем тот факт, что каждая вершина должна соответствовать повороту влево при обходе границы выпуклой оболочки в направлении против движения часовой стрелки. Рассмотрим сначала первого кандидата - точку . Поскольку угол представляет нелевый поворот ( лежит справа от ребра ), точка удаляется из текущей оболочки. Затем рассмотрим точку . Поскольку угол также представляет нелевый поворот, то удаляется и точка . Аналогичным образом удаляется точка . Ситуация изменяется при достижении точки : угол обозначает поворот влево и таким образом находится последователь для точки в текущей оболочке (точка ).

В программу grahamScan передается массив pts из n точек и возвращается полигон, представляющий собой выпуклую оболочку для точек pts.

Программа выполняется за пять шагов: первые два образуют этап предварительной сортировки, а в течение оставшихся трех находится выпуклая оболочка:

Рис. 6.3. Работа по методу обхода Грэхема.

1. Поиск экстремальной точки .
2. Сортировка остальных точек по их полярному углу относительно точки .
3. Инициализация текущей оболочки.
4. Формирование текущей оболочки, пока она не станет равной выпуклой оболочке для всехn элементов.
5. Преобразование текущей оболочки в объект типа полигон (Polygon) и возврат его.

Программа выглядит следующим образом:

Point originPt;
Polygon *grahamScan(Point pts[], int n)
{ // шаг 1
int m=0;
for (int i = 1; i< n; i++)
if ((pts[i] .y< pts[m] .y)||
((pts[i].y == pts[m].y)&&(pts[i].x < pte[m].x)))
m = i;
swap(pts[0], pts[m]);
originPt = pts[0];
Point **p = new (Point*) [n] ; // шаг 2
for (i = 0; i< n; i++)
p[i] = &pts[i];
selectionSort(&p[1], n-1, polarCmp); //или любой другой способ сортировки
// шаг 3
for (i=1, p[i+1]->classify(*p[0], *p[i]) == BEYOND; i++)
;
Stack < Point* > s;
s.push(p[0]);
s.push(p[i]);
for (i = i+1; i < n; i++) // шаг 4
{while (p[i]->classify(*s.nextToTop(), *s.top()) ! = LEFT)
s.pop ();
s.push(p[i]);
}
Polygon *q = new Polygon; // шаг 5
while (!s .empty ())
q->insert(*s.pop());
delete p;
return q;
}

Первый шаг ясен. На шаге 2 создается массив p и его элементы инициализируются равными точкам Point в массиве pts. Нам требуется массив указателей, чтобы можно было использовать одну из обобщенных подпрограмм сортировки. Затем массив p сортируется с помощью функции сравнения polarCmp, которая определена в разделе 5.2 в контексте построения звездчатого полигона по заданному набору точек. Напомним, что глобальная iпеременная originPt используется для того, чтобы передать в функцию polarCmp начальную точку - в данном случае точку .

На 3 и 4 шагах в стеке s создается текущая оболочка. Пусть имеем набор и стек представляет текущую оболочку CH(S) следующим образом. Если точки в стеке обозначены как в порядке от низа стека к его верху, то стек удовлетворяет таким условиям стека:

1. Точки являются вершинами текущей оболочки СН(S) в направлении обхода против часовой стрелки;

2. Ребро является ребром окончательной выпуклой оболочки СН(S).

На шаге 3 эти условия определяются предварительно. В цикле for осуществляется пошаговое продвижение по лучу до тех пор, пока не будет достигнута последняя (самая дальняя) точка , после чего точки и , будут записаны в стек. Первое условие стека будет удовлетворено по той причине, что отрезок прямой линии является выпуклой оболочкой для поскольку точки расположены между и . Второе условие выполнено потому, что является ребром для CH(S).

На шаге 4, проиллюстрированном на рис. 6.4, обрабатывается точка для формирования текущей оболочки CH( ). Программа grahamScan выбирает из стека точки до тех пор, пока не будет достигнута точка , самая верхняя точка в стеке такая, что угол представляет левый поворот. Поскольку все эти вызванные точки лежат внутри треугольника или вдоль одного из ребер или , то ни одна из них не может быть вершиной выпуклой оболочки CH( ). Так как из стека будут удалены только эти точки и никакие другие, оставшиеся точки вместе с будут вершинами выпуклой оболочки CH( ). Вследствие того, что первое условие стека гарантирует корректность упорядочения точек внутри стека, а точка следует за ними в порядке увеличения полярного угла, то новое содержимое стека правильно упорядочено в порядке обхода против часовой стрелки. Из этого следует, что первое условие соблюдено.

Назначение условия 2 заключается в гарантии существования точки . Поскольку ребро является ребром оболочки CH(S), то каждая точка , прошедшая обработку, лежит слева от отрезка . Поскольку угол представляет левый поворот, то из этого следует, что точка существует для некоторого . Более того, так как исходные точки и никогда не вызываются из стека, условие 2 сохраняется.

На шаге 5 программа grahamScan формирует объект q типа Polygon путем итеративного вызова точки из стека и записи ее в q. Согласно условию 1 точки вызываются из стека в порядке обхода по часовой стрелке.

Рис. 6.4. Включение точки для образования текущей оболочки CH( ).

Что касается времени работы, то легко видеть, что каждый из шагов 1, 3 и 5 выполняется за время . На шаге 4 тело цикла while выполняется не более одного раза для каждой точки (будучи вызванной из стека, точка никогда вторично в стек не записывается). Следовательно, выполнение шага 4 также занимает время и общее время выполнения в основном зависит от начальной сортировки на шаге 2, поэтому метод обхода Грэхема выполняется за время , если используется подходящий способ сортировки. Стоит еще раз напомнить, что метод обхода Грэхема будет выполняться за линейное время, если известно, что набор точек изначально отсортирован.

3. Сортировка при вводе.

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

Рассмотрим, как использовать сортировку при вводе для упорядочения элементов массиваа[0], . . ., а[n-1] в порядке увеличения. (Для краткости этот набор элементов будем обозначать как a[0 . . . n-1]). Для каждого i от 1 до n - 1 в начале итерации i подмассив a[0...i-l] считается отсортированным. Наша задача на шаге итерации i заключается в сортировке массива a[0...i]путем занесения элемента a[i] в его соответствующую позицию. Чтобы выполнить это, мы запишем элемент a[i] в некоторой переменной v и затем по очереди будем перемещать элементы a[i-1], a[i-2], ... на один элемент вправо до тех пор, пока не найдем первый элементa[j-l], не больший, чем v. Наконец скопируем значение v в "дырку", которая образовалась в позиции j. На рис. 5.1 показано, как этот алгоритм сортирует короткий массив целый чисел.

Рис. 5.1. Сортировка при вводе массива из шести целых чисел. Кружком отмечены очередные числа, подлежащие вводу.

Алгоритм реализован шаблоном функции insertionSort, которая сортирует массив a[0...n-1]. Аргумент cmp устанавливает функцию сравнения, которая возвращает значения -1, 0 или 1, если ее первый аргумент меньше, равен или больше второго аргумента соответственно:

template< class T >
void insertionSort(Т а[], int n, int (*cmp)(Т,Т))
{for (int i = 1; i < n; i++)
{Т v = a [ i ] ;
int j = i;
while ((j > 0) && ((*cmp)(v, a[j-l]) < 0))
{a[j] = a[j-l];
j --;
}
a[j] = v;
}
}

На каждой итерации i от 1 до n - 1 цикл while вводит элемент a[i] в сортируемый подмассивa[0. . .1-1]. Проверка j > 0 в цикле while гарантирует, что работа программы не нарушится при достижении начального элемента массива a в процессе ввода.

В представленной здесь программе сортировки предполагается, что параметр типа T в шаблоне является типом указателя. Тем не менее шаблон функции insertionSort, может быть использован для сортировки объектов любого типа, для которых существует оператор присвоения = и копирующий конструктор. Например, следующий фрагмент программы считывает 100 строк в массив s и затем сортирует их с помощью стандартной библиотечной программы strcpy языка C++, которая сравнивает строки символов в словарном порядке.

char buffer[80];
char *s[100];
for (int i=0; i < 100 ; i++)
{cin >> buffer ;
s[i] = new char[strlen(buffer)+1];
strcpy(s[i], buffer);
}
insertionSort(s, 100, strcmp);

Заметим, что в этом фрагменте программы сортируется скорее массив указателей на строки (массив s), чем сами строки. Очень часто оказывается, что гораздо эффективнее сортировать указатели вместо самих объектов, на которые они указывают. Если объекты не очень малы (четыре байта или меньше), то сортирующая программа может перемещать указатели быстрее, чем сами объекты.

4. Построение выпуклой оболочки способом "заворачивание подарка".

Один из способов формирования выпуклой оболочки конечного набора точек S на плоскости напоминает действия по вычерчиванию выпуклой оболочки с помощью линейки и карандаша. Вначале выбирается некоторая точка такая, что она явно должна принадлежать границе выпуклой оболочки - для этого годится самая левая точка. Затем вертикальный луч поворачивается по направлению движения часовой стрелки вокруг этой точки до тех пор, пока он не наткнется на некоторую другую точку b в наборе S; отрезок будет ребром выпуклой оболочки. Для поиска следующего ребра будем продолжать вращение луча по часовой стрелке, на этот раз вокруг точки b до встречи со следующей точкой c из набора S, отрезок будет следующим ребром выпуклой оболочки. Этот процесс продолжается до тех пор, пока не будет достигнута точка a. Процесс изображен на рис. 6.1, он получил название способ "заворачивание подарка".

Процесс поворота луча вокруг каждой точки является "выбирающей" частью алгоритма. При выборе точки, следующей за точкой a на границе выпуклой оболочки, ищем такую точку b, для которой нет ни одной точки, лежащей слева от луча . Все точки анализируются по очереди, пока алгоритм не проследит весь путь, вплоть до самой левой точки, обнаруженной к этому моменту. При этом проверке подвергаются только те еще не известные точки, которые должны принадлежать границе выпуклой оболочки. Следующая программаgiftwrapHull возвращает полигон, представляющий выпуклую оболочку n точек в массиве s. Массив s должен иметь длину n+1, поскольку в элементе s[n] программа хранит ограничивающий элемент ("страж"):

Polygon *giftwrapHull(Point s[], int n)
{int a, i;
for (a=0, i=1; i< n; i++)
if (s[i] < s[a])
a = i;
s[n] = s[a];
Polygon *p = new Polygon;
for (int m = 0; m < n; m++)
{swap(s[a], a[m]);
p->insert(s[m]);
a = m+1;
for (int i =m + 2; i <=n; i++)
{int с = s[i].classify(s[m], s[a]);
if (c==LEFT || c == BEYOND)
a = i;
}
if (a == n)
return p;
}
return NULL;
}

Вращение луча вокруг некоторой точки s[m] моделируется внутренним циклом for. Точкаs[a] должна быть самой левой, которая встречается на пути луча. Если новая точка s[i] лежит слева от луча, начинающегося в точке s[m] и проходящего через точку s[a], тогда вращаемый луч должен поместить точку s[i] перед точкой s[a], так что точка a будет изменена.

Рис 6.1. Заворачивание подарка для набора точек на плоскости.

Переменная a также изменяется, если точка s[i] лежит позади s[a] - точка s[a] не может быть вершиной выпуклой оболочки, если она лежит между точками s[m] и s[i].

Заметим, что функция giftwrapHull реорганизует точки в массиве s. В конце шага mподмассив s[0..m] содержит известные вершины выпуклой оболочки, упорядоченные в направлении по движению часовой стрелки, а подмассив s[m+l..n-l] содержит остальные точки, которые принадлежат или нет вершинам выпуклой оболочки. Именно эти последние точки и должны проверяться на последующих шагах.

 






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.