Информационные и коммуникационные технологии. Дешко И.П - 119 стр.

                                 119

заполненные), то в указанном диапазоне данные о крайнем пра-
вом пикселе на каждом интервале поместить в стек.
      Рис.2 иллюстрирует последовательность действий при рабо-
те такого алгоритма по заполнению конкретной гранично-
определенной четырехсвязной области. В качестве исходной за-
травки используется пиксель с координатами адресуемой точки
(3, 5). На рисунке обозначены также уровни стека, на которые
помещаются данные о соответствующих пикселях.
      Алгоритм двумерного отсечения Сазерленда-Коэна
   y Данный алгоритм реализует
                            h          отсечение отрезков координат-
                  i
но-ориентированным
        1001         1000прямоугольником,
                                    1010       границы которого: ле-
вая, правая, нижняя и верхняя – задаются координатами соот-
yв
ветственно    xл , xп , yн и yв (рис.3).
                                  e       В алгоритме используются
      j
четырехразрядные (битовые)    g коды, определяющие расположение
концов0001отрезков   0000
                 a относительно     0010
                                     границ отсекающего окна. При
       d
формировании кода конца отрезка с координатами (x, y) в первый
(крайний                  b
           правый) бит заносится     1, если x < xл , во второй – если
yн
x > xп , в третий – если y < yн , в четвертый – если y > yв . В
        0101         0100           0110
остальных
    c        случаях   в соответствующие     биты заносится 0. Таким
                            f           x
образом, вся координатная плоскость разбивается на девять
 0            x                xп
областей, в лкаждой из которых          концу отрезка присваивается
    Рис.3. Коды
уникальный      кодконцов
                       (см.отрезков
                              рис.3). При внутреннем отсечении
признаком полной видимости отрезка являются нулевые коды
обоих его концов (как для отрезка ab на рис.3). Признак
безусловной невидимости отрезка – отличное от нуля побитовое
логическое произведение концевых кодов (так, у отрезка cd,
расположенного целиком левее отсекающего окна, с кодами
концов 0101 и 0001 такое произведение будет равно 0001).
Вместе с тем, при полностью нулевом побитовом логическом
произведении концевых кодов отрезок может оказаться частично
видимым (как отрезки ef и gh) или полностью невидимым (как
отрезок ij). Для подобных отрезков при выявлении их возможных
видимых частей используются результаты определения точек
пересечения бесконечной прямой линии, проведенной через
отрезок, с бесконечными прямыми линиями, проведенными через
ребра отсекающего окна.