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

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

4.8. Задачи о пересечениях многоугольников верка завершается"images/tmp8E4A-225.png" alt="Проверка нахождения луча внутри выпуклого полигона" />

Рис. 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]. Последний алгоритм будет рассматриваться в тематическом задании в конце главы. Подпрограмма, реализующая отсекатель Сайруса-Бека, имеет следующий интерфейс"opengl1_274.html">⇐ Предыдущая| |Следующая ⇒