Практическое упражнение 4.8.4. Произвести отсечение прямой Найдите те части прямой от точки А = (1,3,5) до точки В = (9,3,5), которые находятся внутри полигона со списком вершин (2,4), (3,1), (4,4), (3,3).
Алгоритмы отсечения являются основой компьютерной графики, в связи с чем было разработано большое количество эффективных алгоритмов такого рода. До сих пор мы исследовали два подхода: алгоритм отсечения Кохена-Сазерленда (Cohen-Sutherland), описанный в главе 2, отсекает прямые границами выровненного прямоугольника; отсекатель Сайруса-Бека (Cyrus-Beck) обобщает первый алгоритм на отсечение прямой границами любого выпуклого многоугольника или многогранника. Однако возникают ситуации, когда необходимо более сложное отсечение. Здесь мы коснемся двух таких методов, однако их детали рассмотрим в тематических заданиях в конце главы.
Отсекатель Сазерленда-Ходгмана (Sutherland-Hodgman) напоминает метод Сайруса-Бека, выполняющий отсечение границами выпуклого полигона. Однако вместо того, чтобы отсекать один отрезок прямой, он отсекает целый полигон (который не обязан быть выпуклым) границами выпуклого полигона. Самое важное при этом, что на выходе он снова дает полигон (или несколько полигонов). Иногда бывает необходимо сохранять полигональную структуру во время отсечения, так как отсеченные полигоны, возможно, требуется заполнить каким-нибудь узором или цветом. А этого нельзя сделать, если вершины полигона отсекаются по отдельности.
Алгоритм отсечения Уейлера-Азертона (Weiler-Atherton) отсекает любой полигон р границами любого другого полигона w, как выпуклого, так и не выпуклого. Этот алгоритм может выдавать на выходе ту часть полигона р, которая располагается внутри w (внутреннее отсечение - interior clipping), или часть р, расположенную вне "/(внешнее отсечение - exterior clipping). Кроме того, внутри обоих полигонов - р и W- могут содержаться отверстия («дыры»). Как и следовало ожидать, данный алгоритм является более сложным, чем все другие, изученные до сих пор, однако благодаря своей мощности он оказывается прекрасным дополнением к инструментарию для многих приложений.