Френсис Хилл

Рис. 4.43. Возможный интервал для пересечения

4.8. Задачи о пересечениях многоугольников верка завершается: возможный интервал составляет [0,28, 0,66]. И действительно, луч находится внутри Рдля всех £ от 0,28 до 0,66.

Френсис Хилл

Рис. 4.44. Проверка нахождения луча внутри выпуклого полигона Таблица 4.1. Обновления значений t и t

L(прямая)

К,

 

0,83

0,66

0,66

0,66

0,2

0,66

0,28

0,66

В табл. 4.1 показана последовательность обновлений значений £п и гои1, которые происходили при тестировании относительно каждой из описанных выше прямых.

4.8.3. Алгоритм Сайруса-Бека Давайте теперь применим только что изложенные идеи к созданию подпрограммы, осуществляющей отсечение отрезка прямой границами произвольного выпуклого полигона. Впервые этот метод был создан Сайрусом и Беком (Cyrus, Beck) [Cyrus, 78]. Позднее высокоэффективный отсекатель для прямоугольных окон, основанный на аналогичных идеях, был разработан Лиангом и Барски (Liang, Barsky) [Liang, 84]. Последний алгоритм будет рассматриваться в тематическом задании в конце главы. Подпрограмма, реализующая отсекатель Сайруса-Бека, имеет следующий интерфейс:

int CyrusBeckClip{LineS seg, LineListS L); Параметрами являются отрезок прямой seg, подлежащий отсечению (он содержит первую и вторую концевые точки, именуемые соответственно seg.first и seg.second), а также список прямых, ограничивающих полигон. Подпрограмма производит отсечение seg относительно каждой прямой из списка L, как описано в разделе «Пересечение с лучами и отсечение для выпуклых полигонов'», и помещает отсеченный отрезок обратно в seg (поэтому seg должен передаваться по ссылке). Подпрограмма возвращает следующие значения: О 0, если никакая часть отрезка не располагается в Р (возможный интервал пуст); О 1, если некоторая часть отрезка располагается в Р.

Глава 4. Векторные инструменты для графики Листинг 4.3. Псевдокод отсекателя Сайруса-Бека для выпуклого полигона, двумерный случай

int CyrusBeckClip(LineSegment& seg, LineList L) {

double numer. denom: // used to find hit time for each line // используются для нахождения времени соударения //с каждой прямой


⇐ Предыдущая| |Следующая ⇒