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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 118 119 120 121 122 123 < 124 > 125 126 127 128 129 130 .. 180 >> Следующая


Ключевым является наблюдение, что пересечение каждого сектора с выпуклым многоугольником образует четырехугольник (трапецию, если О —бесконечно удаленная точка). Поэтому внутри каждого сектора пересечением Р и Q будет пересечение двух четырехугольников, которое можно найти за константное время. Результирующие куски можно собрать воедино за один обход секторов, на который понадобится линейное время. А затем потребуется очищающий просмотр для удаления ложных вершин, которые возникают на границах между секторами.

Теорема 7.3. 'Пересечение выпуклых L-угольника и М-уголь-ника можно построить за время 8 (L + М).

На рис. 7.5 проиллюстрирован метод, где точка О выбрана так, как предложили Шеймос и Хоуи. В данном случае секторы называются полосами, а полярный угол относительно О заменен значением абсциссы х.

334

Гл. 7. Пересечения

Другой подход является, как это ни удивительно, элегантным усовершенствованием [O'Rourke, Chien, Olson, Naddor (1982)] того грубого метода, который был описан в начале данного

Рис. 7.5. Полосы, определенные вершинами двух выпуклых многоугольников.

раздела. Его основная идея неформально следующая. Предположим, что РП<Э Ф 0, и рассмотрим многоугольник P*AP(]Q-Границей Р* является чередующаяся последовательность участков границ Р и Q. Если одним из таких участков является кусок границы, скажем, Р, то некий участок границы Q окружает ее во внешней области Р* (рис. 7.6). Благодаря выпуклости обоих многоугольников в каждой паре таких смежных

Рис. 7.6. Два пересекающихся многоугольника. «Серпы» заштрихованы.

участков естественно выделяются внешняя и внутренняя цепи, которые можно назвать в совокупности «серпом» для удобства последующего описания. Серп ограничен парой точек пересечения, именуемых начальной и конечной в соответствии с единой ориентацией границ Р и Q. Говорят, что вершина (из Р или Q) принадлежит серпу, если (1) она лежит между начальной и конечной точками пересечения (на любой цепи) или (2) яв-

7.2. Плоские приложения

335

ляется концом ребра внутренней цепи, содержащего конечную точку серпа (рис. 7.7). Заметим, что существуют вершины, принадлежащие двум серпам.

Для создания механизма Рг, Pl) и (qu q2, qM)-ветственно, перечисленных при обходе их против часовой стрелки (так что многоугольник считается расположенным «слева» от своей границы). Предположим, что продвижение осуществляется одновременно по обеим границам и что р,-и qj — текущие вершины заданных многоугольников, а, кроме того, текущие ребра оканчиваются в pi и q,-; возможны четыре разные ситуации, которые показаны на рис. 7.8. (Остальные ситуации сводятся к данным четырем путем замены ролей Р и q.) Пусть h(pd обозначает полуплоскость, определенную p,_ip,- и содержащую Р (аналогично определяется и А (?,¦)). Очевидно, что Р* содержится внутри пересечения А(р,-) областях на рис. 7.8.

продвижения положим, что (рь -это списки вершин Р и Q соот-

другой граш

тельного расположения текущих вершин pt и qj (текущие ребра показаны жирными прямыми).

[ h(qj), т. е. в заштрихованных

336

Гл. 7. Пересечения

Идея заключается в том, чтобы не двигаться по той границе (Р или Q), текущее ребро которой еще может содержать необнаруженную точку пересечения. Тогда в случае (2) мы продвинемся по Р, поскольку текущее ребро qs-\q\ из Q может содержать еще не обнаруженную точку пересечения; по тем же причинам в случае (3) мы продвинемся по границе Q. в случае (4) все пересечения на текущем ребре из Р уже обнаружены, в то время как текущее ребро из Q все еще может содержать необнаруженное пересечение; поэтому мы продвинемся вдоль Р. Наконец, в случае (1) выбор произволен, и выберем, например, Q. Рассмотрение этих четырех случаев полностью определяет механизм продвижения в данном методе, осуществляемый подпрограммой движение. Выражение «движение реализует случай (/)» (при /= 1, 2, 3, 4) означает, что продвижение, соответствующее случаю (/), выполняется корректно.

Если пренебречь для ясности и простоты вырожденными случаями (когда граница Р содержит вершину Q и наоборот), которые требуют особого внимания1), то можно формализовать алгоритм. Заметим, что pL и qM непосредственно предшествуют pi и qi соответственно (это означает, что, как обычно, Ро = рь и q0 = qM).

procedure построение-пересечения-

выпуклых-многоугольников

begin /:= j:=k:= 1:

repeat _

begin if (Pi-iPi и 9/_1<7/ пересекаются) then вывод пересечения;

движение (* i или / увеличивается *); k:=k+ 1

end;

until k = 2{L + M); if (не найдено пересечений) then begin if p< <=Q then P<=Q

else if q, e= P then Q <= P else P[)Q= 0

end;

end.

Теперь установим корректность данного алгоритма. Если р, и q, принадлежат одному серпу, то подпрограмма движение гарантирует достижение конечной точки пересечения данного серпа (как очередного пересечения), поскольку не допускается

') Подробности можно найти в первоисточнике [O'Rourke et al. (1982)].

7.2. Плоские приложения

337

продвижения по той границе, текущее ребро которой может содержать искомую точку пересечения. Это в свою очередь гарантирует, что поскольку обе текущие вершины принадлежат одному и тому же серпу, то все серпы будут построены последовательно. Для завершения доказательства необходимо убедиться, что данный алгоритм обнаруживает хотя бы одну точку пересечения, если она существует. Заметим, что точки пересечения образуют пары, поэтому будет по крайней мере две точки
Предыдущая << 1 .. 118 119 120 121 122 123 < 124 > 125 126 127 128 129 130 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed