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

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

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


снизу и в соответствии с этим называются В-оболочкой и Н-оболочкой множества точек («В» обозначает верхнюю, а «Н» — нижнюю оболочку). Например, В-оболочка множества точек S получается как обычная выпуклая оболочка множества SU{°°h} (рис. 3.19), где ооя точка плоскости с координатами (0,—°о)'). Поняв, что выпуклая оболочка множества S тривиально получается в результате пере-

') Это понятие уже использовалось при обсуждении предложенного Эндрью варианта алгоритма построения оболочки методом Грэхема (см. разд. 3.3.2).

3.19.

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

153

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

Нет ничего удивительного в том, что как открытый алгоритм построения выпуклой оболочки, рассмотренной в разд. 3.3.6, так и настоящий полностью динамический метод используют в качестве структур данных деревья. Однако в представлениях оболочки в этих двух подходах имеется существенное различие. При первом подходе каждый узел дерева представляет некоторую точку множества. При втором подходе только листья дерева используются для представления точек, а каждый внутренний узел представляет В-оболочку точек, соответствующих его листьям.

Соответствующая структура данных Т организована следующим образом. Ее основой является сбалансированное по высоте двоичное дерево поиска Т (с некоторой предосторожностью вместо него можно было бы использовать 2-3-дерево {Aho, Hop-croft, Ulman (1974), (с. 169 русского издания)]), листья которого используются для хранения точек текущего множества. Процедура поиска будет производиться в соответствии со значением абсциссы (ж-координаты) точек, так что прохождение листьев дерева слева направо дает множество точек, упорядоченное по х-координате. Заметим, что последовательность точек В-оболочки (ее вершин) также упорядочена по возрастанию абсциссы, и, следовательно, она является подпоследовательностью глобальной последовательности точек, хранящейся в листьях дерева.

Пусть v — узел дерева Т. Обозначим через ЛСЫЩу] и ПСЫН[у] его левого и правого потомков соответственно. Мы хотим научиться строить В-оболочку точек, хранящихся в листьях поддерева с корнем в узле v. Так как для этого надо будет выполнять сцепление и расцепление цепей вершин, то мы предполагаем, что каждая такая цепь представлена в виде сцепляемой очереди (см. разд. 3.3.6). Обозначим через U(v) В-оболочку множества точек, хранящихся в листьях поддерева с корнем в v. Следуя принципу индукции, предположим теперь, что уже имеются /У(ЛСЫН[и])и /7(ПСЫН [v]), т. е. В-оболочки, связанные с потомками узла v. Каким образом можно построить U(v)? Взгляните на рис. 3.20. Все, что необходимо сделать,— это определить две опорные точки р\ и р2 единственного общего опорного отрезка для двух оболочек. Здесь нам необходима функция СОЕДИНИТЬ(V\, U2), позволяющая найти опорный отрезок для двух В-оболочек U\ и Ц2. Функция СОЕДИНИТЬ позволяет эффективно расцеплять U\ на две цепи, составляющие упорядоченную пару (?/ц, UX2) (рис. 3.20), и аналогичным образом U2 — на пару цепей (U2\, U22). При этом выполняется следующее условие: опорная точка pi е= U\ входит в состав Un,

154

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

а точка р2 е U2 входит в состав U22 (т. е. в обоих случаях опорная точка принадлежит «внешней» подцепи). На этом этапе, сцепив Un и U22, получаем искомую В-оболочку Ui U U2. Естественно, чтобы каждый узел v дерева Т указывал на сцепляемую очередь, представляющую ту часть U(v), которая не принадлежит ?/(ОТЕЦ|>]).

Предположим, что мы хотим выполнить обратную операцию, т. е., имея U(v), получить 1/(ЛСЫН[о]) и Е/(ПСЫН(и]). Все, что требуется в этом случае, так это знать ребро р\р2, соединяющее опорные точки, т. е. одно целое число J[v], указывающее положение точки pi в цепи вершин U(v). Имея эту информацию,

Рис. 3.20. Для построения В-оболочки объединения оболочек U, и О, необходимо построить общий опорный отрезок (мост) р,р2.

можно расцепить U(v) на цепи Ип и U22, которые в свою очередь могут быть сцеплены с цепями, хранящимися в ЛСЫН[и] и ПСЫЩи] соответственно. В заключение структура данных Т дополняется следующими атрибутами, связываемыми с каждым узлом v дерева Т:

1. указатель на сцепляемую очередь Q[v], содержащую часть U(v), не входящую в (/(ОТЕЩи]) (если v является корнем, то Q[v] =!/(»));

2. целым числом J[v], указывающим положение (индекс) левой опорной точки в U{о).

Эта интересная структура данных использует память объемом лишь 0(N), где N — размер текущего множества точек. В самом деле, дерево Т, являющееся основой структуры данных, имеет JV листьев и N — 1 узлов на более высоких уровнях, в то время как множества точек, хранимые в сцепляемых очередях, представляют разбиение множества всех точек.

Учитывая, что операции расцепления и сцепления сцепляемых очередей являются стандартными, наше внимание будет сосредоточено на операции, выполняемой функцией СОЕДИНИТЬ, для которой Овермарс и Ван Леювен [Overmars, van Leeuwen (1981)] предложили следующее решение:
Предыдущая << 1 .. 50 51 52 53 54 55 < 56 > 57 58 59 60 61 62 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed