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

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

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 129 130 131 132 133 134 < 135 > 136 137 138 139 140 141 .. 180 >> Следующая


Рис. 7.26. Иллюстрация к определению вершин Ft и I/.

заключенный между ш, и wi+\ и ориентированный от wi к Если многоугольник Ki не ограничен, то два его ребра — лучи; поэтому обозначим через Aew луч, заканчивающийся в точке w и ориентированный как ребро е, а через weA луч, дополняющий первый до прямой.

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

Среди вершин Ki выделим две —Р, и L,-, определяемые следующим образом. Рассмотрим пару опорных к Ki прямых, проходящих через вершину у,- из Р (рис. 7.26). Пусть Д и /, —такие два луча на этих прямых, которые содержат опорные точки, и названные так, что угол, отсчитанный по часовой стрелке от до /,¦ в клине плоскости, содержащем Ki, не превосходит п (рис. 7.26). Обозначим через F, такую точку, общую для /« и Ki, которая наиболее удалена от и,; аналогично определяется

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

367

и точка Li. Эти две вершины играют важную роль при построении Ki+i по Ki.

Если в Р нет вогнутых вершин, то Р выпуклый и, очевидно, К(Р)=Р. Поэтому пусть vo — вогнутая вершина Р. Теперь можно описать алгоритм построения ядра.

Рис. 7.27. Пример многоугольника К\.

Начальный шаг. (* К\ обозначает пересечение полуплоскостей, лежащих слева от ребер е0 и в\, см. рис. 7.27 *)

= AeiV0e0A;

- точка на бесконечности на луче AeiVQ; = точка на бесконечности на луче v0e0A.

Общий шаг. (Переход от Ki к Ki+i.) Предположим, что вершины Ki занумерованы последовательно при обходе против часовой стрелки: w\, ш2, .... Будем различать следующие случаи: (1) Вершина ы вогнута (рис. 7.28 и 7.29).

(1.1) Ft лежит на луче Ле1+1у,+1 или справа от него (рис. 7.28). Обходим границу Ki против часовой стрелки, начиная с Ft, до тех пор, пока не достигнем единственного ребра wt-iwt из Ki, которое пересекает луч Ле,+1у,+ь или пока не достигнем Li, не найдя подобного ребра. В последнем случае закончим работу алгоритма (К[Р) = 0). В первом случае предпримем следующие действия:

(1.1.1) находим точку w' пересечения wt-\wt с Ae,-+ii/,-+1;

(1.1.2) обходим границу Ki по часовой стрелке от Ft до тех пор, пока не достигнем ребра ws-\ws, пересекающего Aei+lvl+x в точке w" (это наверняка произойдет, если К; ограничен) или (если только Ki неограничен) пока не достигнем головы списка, не

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

найдя подобного ребра. В первом случае, обозначая Ki = aws ¦ ¦. wt-ф (где а и Р — последовательности чередующихся ребер и вершин), полагаем Ki+i:=a>w"ei+iw'$; во втором случае (когда Ki неограничен) необходимо проверить, будет Ki+i ограниченным или нет. Если наклон луча Aei+iVt+i заключен в пределах между наклонами начального и конечного лучей Ki, то Ki+i := Ле(+1о/р

Рис. 7.28. Действия на общем шаге, если у, —вогнутая вершина, a Fi лежит на луче AeI+it),+i или справа от него.

также неограничен. В противном случае начнем обход границы Ki по часовой стрелке от хвоста спи-ска до тех пор, пока не достигнем ребра wr-\wr, которое пересекает луч Ae*+it/«+i в точке w"; обозначая Ki = ywt-\bw,r\, полагаем Ki+i :=bw"ei<Hw', и список становится циклическим.

Выбор Fi+i производится так: если Aei+iVi+i имеет ровно одну точку пересечения с Ki, то := (бесконечная точка луча Aei+iVi+i); иначе Fi+\\=w". Для определения Li+i обходим Ki против часовой стрелки от L, до тех пор, пока или не найдена такая вершина wu на Ki, что wu+i

лежит слева от луча Vi+\(vi+\wu)A, или не исчерпан весь список Ки а подобная вершина не найдена. В первом случае L,-+i := дои; в другом случае (который может встретиться, только если Ki неограничен) Lw := Li. (1.2) Fi лежит слева от луча Aei+\Vi+i (рис. 7.29). В этом случае Ki+i := Ki, но Fi и Li нужно скорректировать. Для определения Р,+\ обходим К; против часовой стрелки от Ft до тех пор, пока не найдена такая вершина wt на Ki,

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

что wt+i лежит справа от луча Vi+\{Vi+\Wt)A; затем положим Fi+i := wt. Определение точки Li+i проводится так же, как в случае (1.1).

Рис. 7.29. Действия на общем шаге, Рис. 7.30. Действия на общем шаге, если vi — вогнутая вершина, a Fi ле- если v — выпуклая вершина, а Ц лежит слева от луча Aet+iVi+i. жит на луче viei+i\ или справа от него.

(2) Вершина ы выпукла (рис. 7.30 и 7.31).

(2.1) Li лежит на луче viei+iA или справа от него (рис. 7.30). Обходим границу Ki по часовой стрелке от Li до тех пор, пока не достигнем или того единственного ребра wt-iWt,

Рис. 7.31. Действия на общем шаге, если и, —выпуклая вершина, а Ц лежит слева от луча у,е;+,Л. ¦' -

которое пересекает луч Vid+xA, или вершины Ft, не обнаружив подобного ребра. В последнем случае заканчиваем алгоритм (К(Р)= 0). В первом случае предпримем следующие действия:

(2.1.1) находим точку w' пересечения wt~\Wt с у,-е,-+)Л;
Предыдущая << 1 .. 129 130 131 132 133 134 < 135 > 136 137 138 139 140 141 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed