Подобно алгоритму Сайруса-Бека, алгоритм Сазерленда-Ходгмана отсекает полигон 5 относительно каждой ограничивающей полигон С прямой поочередно, оставляя только ту часть, которая находится внутри С. После того как все ребра полигона С будут обработаны таким способом, полигон 5 будет отсечен границами полигона С, как и требовалось. На рис. 4.53 показано применение этого алгоритма к отсекаемому семиугольнику 5 и отсекающему прямоугольнику С. В этом примере мы будем описывать каждый шаг процесса. Полигон 5 описывается списком вершин а, Ь, с, d, e,f,g. 5 отсекается относительно верхнего, правого, нижнего и левого ребер С поочередно, и на каждой стадии из старого списка вершин генерируется новый список. Этот список описывает один или несколько полигонов и выступает в качестве отсекаемого полигона для отсечения относительно следующего ребра полигона С.
Таким образом, основная операция состоит в отсечении полигона(ов), описанных посредством входного списка вершин, относительно текущего ребра полигона Сив создании выходного списка вершин. Чтобы проделать это, мы просматриваем входной список, формируя последовательные ребра из смежных пар вершин. Каждое такое ребро Е имеет первую и вторую концевые точки, которые мы назовем соответственно s и р. Существует четыре возможных ситуации для точек s и р: они могут обе располагаться во внутренней полуплоскости отсекающего ребра, обе быть в его внешней полуплоскости, одна из них может быть по одну, а другая - по другую сторону от ребра, и наоборот. В каждом из этих случа-
Векторные инструменты для графики
ев соответствующие точки выводятся в новый список вершин (или добавляются в него), как это показано на рис. 4.54. Все случаи и соответствующие им действия сведены в следующий список: а) 5 и р во внутренней полуплоскости ребра: выводится р; б) « во внутренней полуплоскости, р снаружи: найти точку пересечения г и вывести ее; в) « и р снаружи: не выводится ничего; г) « снаружи, р внутри: найти точку пересечения г, вывести i и затем р.