Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 54

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 48 49 50 51 52 53 < 54 > 55 56 57 58 59 60 .. 180 >> Следующая


Рассмотрим построение опорных прямых из некоторой точки р к выпуклому многоугольнику С. (Структура данных для

Опорное

¦3.3. Алгоритм построения выпуклой оболочки

147

представления вершин С пока не определена. Мы выберем ее после того, как определим, какие операции с ней будут проводиться.) В последующем обсуждении важную роль будет играть классификация вершин многоугольника С по отношению к отрезку pv, соединяющему вершину v с точкой р. Вершина v называется вогнутой (следовало бы добавить «по отношению к отрезку pv», но обычно это уточнение будет опускаться), если

Р

(а) Вогнутая (Ь) Опорная

(с) Выпуклая

Рис. 3.15. Классификация вершины о многоугольника С относительно отрезка pv. (Стрелки указывают направление обхода при поиске левой опорной прямой.)

отрезок pv пересекает внутренность многоугольника С. Иначе, если две смежные с v вершины лежат по одну сторону от прямой, проходящей через точки р и v, вершина v называется опорной. В оставшемся случае v называется выпуклой вершиной. Мы оставляем читателю в качестве упражнения показать, что вершина v может быть классифицирована за постоянное время.

Если v — опорная вершина, то на этом решение задачи завершается. Предположим, что ищется левая опорная прямая. Если точка v не является опорной, то необходимо шагать (или еще лучше прыгать!) по вершинам многоугольника С против или по часовой стрелке в зависимости от того, является ли v вогнутой или выпуклой вершиной (рис. 3.15). Таким способом

Гл. 3. Выпуклые оболочк

можно определить две опорные точки (если они существуют). Если это сделано, необходимо иметь возможность удалить из циклической последовательности вершин многоугольника С це-м m почку вершин (возможно,

^^''''l-^Nm пустую) и вставить в об-

разовавшийся разрыв точку р.

Теперь стало ясно, какой должна быть структура данных для открытого алгоритма. Необходимо иметь возможность эффективно выполнять следующие операции:

I. ПОИСК в упорядоченной последовательности элементов (кольцевого списка вершин оболочки) для определения опорных прямых из точки рг,

II. РАСЦЕПЛЕНИЕ последовательности на две последовательности и СЦЕПЛЕНИЕ двух последовательностей ;

III. ВСТАВКА одного элемента (текущей точки pi).

Структура данных, в полной мере удовлетворяющая перечисленным требованиям, хорошо известна и называется сцепляемой очередью1). Она реализуется с помощью сбалансированного по высоте дерева поиска, и при этом каждая из указанных выше операций может быть выполнена за время О (log г) в худшем случае, где i — число узлов дерева. Естественно, кольцевая последовательность вершин представляется в этой древовидной структуре данных (называемой далее Т) цепочкой, и при этом первый и последний элементы считаются смежными.

') См. разд. 1.2.3, а также [Aho, Hopcroft, Ullman (1974)] и [Reingold, Nievergelt, Deo (1977)], где этот вопрос рассмотрен более подробно.

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

149

В структуре Т будут выделены две вершины: m — самый левый член цепочки и М — корневой член цепочки. Кроме того, мы будем использовать угол Z(mpiM), который обозначим а. Этот угол называется выпуклым, если он меньше или равен л, и вогнутым в противном случае.

В зависимости от классификации вершин m и М (вогнутая, опорная или выпуклая) и угла а возможны всего восемнадцать случаев. Однако все эти случаи можно свести к восьми (покрывающим все возможности), сведенным в табл. I и показанным

Таблица I

Случай
»

м

,
выпуклый
вогнутая
вогнутая

2
выпуклый
вогнутая
невогнутая

3
выпуклый
невогнутая
выпуклая

4
выпуклый
невогнутая
невыпуклая

5
вогнутый
выпуклая
выпуклая

6
вогнутый
выпуклая
невыпуклая

7
вогнутый

вогнутая

8
вогнутый
невыпуклая
невогнутая

на рис. 3.16. Диаграммы на рис. 3.16 расшифровываются следующим образом: окружность, на которой лежат точки Мят, обозначает многоугольник Р; упорядоченная последовательность вершин начинается в точке т и располагается по окружности в порядке против часовой стрелки; L(M) и R(M) — это последовательности вершин, хранимые в левом и правом поддеревьях корня дерева Т.

Каждый из представленных на рис. 3.16 случаев требует различной обработки для определения левой и правой опорных точек, обозначаемых соответственно / и г.

Рассмотрим сначала случаи 2, 4, 6 и 8. Для этих случаев известно, что / и г существуют (так как р не может быть внутренней точкой многоугольника) и их следует искать в различных поддеревьях корня дерева Т (одно из этих поддеревьев расширяется, чтобы включить сам корень). Таким образом, поиск / и г должен проходить одинаково. Например, следующая процедура осуществляет поиск вершины /:

function ЛЕВЫЙ-ПОИСКА) Input: дерево Т, описывающее последовательность вершин Output: вершина /

1. begin с :=КОРЕНЬ(7');

2. if (рс — опорная прямая) then 1:—с

150

Г л. 3. Выпуклые оболочки: основные алгоритмы

5.

end.

else begin if (с — выпуклая вершина) then
Предыдущая << 1 .. 48 49 50 51 52 53 < 54 > 55 56 57 58 59 60 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed