Алгоритмические основы растровой графики

Заполнение многоугольников и областей

Разбить на страницы
Показывать лекцию целиком

6.1. Введение

В предыдущих лекциях мы рассмотрели алгоритмы отображения линий на растре. Линии на растре зачастую образуют замкнутые области, которые требуется закрасить (заполнить) тем или иным цветом. В этой лекции мы рассмотрим алгоритмы, позволяющие выполнить такое заполнение.

Будут рассмотрены два случая. В первом требуется нарисовать на растре многоугольник, заданный своими вершинами ( растеризация многоугольника ). Во втором, более общем случае мы будем считать, что растровая область задана цветом своей границы и точкой (пикселем) внутри области. Этот пиксель называется затравочным, а сам метод называется заполнением с затравкой.

6.2. Растеризация многоугольников

Пусть задан многоугольник P1P2 . . . PNP1 и требуется растеризовать его вместе с внутренними точками. Будем считать, что процедура отсечения (лекция 5) при необходимости была уже произведена и многоугольник целиком помещается в растровом окне. Для удобства каждое ребро многоугольника будем задавать координатами (x1, y1) и (x2, y2) его концов, так, что $$y_2 \ge y_1$$. Условимся также отсчитывать на экране координату x слева направо, а y - сверху вниз (таким образом, точка (x1, y1) будет верхним концом ребра, а (x2, y2) - нижним). Большинство алгоритмов заполнения основано на том факте, что любое горизонтальное сечение контура многоугольника состоит из четного числа точек. Это утверждение неверно в двух случаях (см. рис. 6.1):

  • когда секущая прямая содержит горизонтальное ребро;
  • когда она содержит вершину, а оба смежных ребра лежат выше (ниже) ее.
    •  (рис 6.1) Исключительные случаи.

    Однако существуют простые способы исключить эти случаи из рассмотрения; они будут рассмотрены позднее. Пока же будем считать, что приведенное утверждение справедливо всегда. Задача заполнения многоугольника, таким образом, сводится к заполнению определенных промежутков между точками сечения, что должно быть проделано для каждого горизонтального сечения многоугольника. Заметим, что при таком подходе никаких ограничений на свойства многоугольника (выпуклость, отсутствие самопересечений и т.д.) не накладывается.

    Алгоритм со списком реберных точек

    Этот алгоритм состоит из трех основных этапов.

    На первом этапе растеризуются все негоризонтальные ребра многоугольника. Все точки помещаются в списки. Для каждой координаты ymin, y2 . . . ymax сопоставим список x-координат всех пикселей, закрашенных при растеризации ребер, которые находятся на горизонтали y (здесь ymin и ymax - минимальная и максимальная y-координаты пикселей в растровом изображении многоугольника). Формально процедура описывается так:

    (рис 6.1) Пример сечений многоугольника.(рис 6.2) Растеризация реберforeach( ребро (x1, y1) - (x2, y2) in МножествоРебер )
{
      y = ceil(y1); // Округление до большего
      dx = (x2 - x1)/(y2 - y1);
      x = x1 + dx*(y - y1);

      while(y <= y2)
      {
            PutToList(x, y); // поместить x в список,
                                  // соответствующий данному y
            y++;
            x += dx;
      }
}

    На втором этапе для каждого y списки упорядочиваются по возрастанию. После этого для многоугольника, изображенного на рис. 6.2, списки будут выглядеть следующим образом:

    ymin x1, x2
    ymin + 1 x'1, x'2
    . . . . . .
    y0 x1 >>, x2 >>, x3 >>, x4 >>
    . . . . . .
    ymax

    На третьем этапе в каждой строке заполняются все отрезки вида [x2i-1, x2i].

    Алгоритм со списком активных ребер

    Попробуем несколько видоизменить предыдущий алгоритм. Вместо того чтобы хранить в памяти точки пересечения контура с каждой строкой растра, ограничимся лишь одной строкой - текущей. А именно, организуем список "активных" ребер (САР), в котором будем хранить информацию обо всех ребрах многоугольника, пересекаемых текущей строкой. Удобство такого подхода в том, что при переходе к новой строке не требуется полностью переформировывать САР. Достаточно лишь удалить из него "закончившиеся" ребра (то есть ребра из САР, чей нижний конец оказался выше нового значения y ) и добавить вновь появившиеся.

    Перейдем к формальному описанию алгоритма. Для каждого ребра создадим структуру данных:

    $$y = \lceil y_1 \rceil;$$ $$dx =\frac{x_2 - x_1}{y_2 - y_1};$$ $$x = x_1 + dx \cdot (y - y_1).$$

    Все такие структуры поместим в список (далее - y-список) и упорядочим его по возрастанию y.

    САР = пустой;
y = y_список[ первый элемент ].y;
do
{
      САР.Добавить( ребра из y-списка, у которых
                                 ребро.y = y);
      // сохраняя упорядоченность САР по возрастанию x
      y_список.Удалить( ребра, у которых ребро.y = y );

      Закрасить промежутки ( x_2i - 1, x_2i ) в строке y;
      y++;

      foreach( ребро из САР по порядку )
      {
            if(y > ребро.y2)
                  удалить ребро из САР;
            else
            {
                  ребро.x += ребро.dx;
                  while(соседнее_слева_ребро(ребро).x > ребро.x)
                        поменять местами в САР ребро с соседним;
            }
      }
}
while(САР не пуст);

    Ребра, помещенные в САР, удаляются из y-списка с той целью, чтобы свести проверку наличия в y-списке ребер, начинающихся с данного уровня y, к проверке этого условия для первого ребра в списке (это справедливо в силу упорядоченности списка). Цикл while используется для сохранения упорядоченности САР, которая может нарушиться при изменении значений x на dx.

    Пример такой ситуации показан на рис. 6.3. При ее возникновении указанный цикл выполняет локальную сортировку САР методом "пузырька".

    (рис 6.3) Локальная сортировка САР.

    Преимущество двух приведенных алгоритмов перед последующими состоит в том, что операции вывода на экран (относительно "медленные" во многих системах) для каждого пикселя выполняются не более одного раза. Недостатком является использование динамических структур данных (списков), что сильно усложняет код и требует дополнительной памяти.

    Существует класс систем, в которых использование динамических структур данных нежелательно (вследствие ограниченности ресурса памяти или отсутствия удобных средств разработки программ), в то время как замедление работы из-за частого обращения к видеопамяти некритично (сюда относятся, например, мобильные телефоны и другие портативные устройства, имеющие графический дисплей). В таких системах эффективным будет использование следующих алгоритмов, оперирующих непосредственно с данными в видеобуфере (то есть с "содержимым" экрана).

    Алгоритм с операцией XOR

    Этот оригинальный алгоритм использует свойства операции XOR (исключающее ИЛИ ). Напомним, что XOR - бинарная операция над битами, действующая по правилу:

    (рис 6.4) XOR-растеризация.
    a b a XOR b
    0 0 0
    0 1 1
    1 0 1
    1 1 0

    Пусть контур многоугольника растеризован и выведен на экран. Тогда его закрашивание сводится к заполнению в каждой строке растра всех промежутков вида [x2i-1, x2i], где через xk обозначены x-координаты "включенных" пикселей в данной строке, упорядоченные по возрастанию (см. рис. 6.4а).

    Через I(x, y) обозначим состояние пикселя с координатами (x, y): I(x, y) = 1, если пиксель "включен", и I(x, y) = 0 в противном случае. Нетрудно убедиться, что последовательное выполнение операции

    I(x + 1, y) = I(x, y)  XOR  I(x + 1, y)

    для x = 1, 2, 3, . . .X - 1 (где X - горизонтальный размер растра) приведет к требуемому результату - с той лишь разницей, что последний пиксель в каждом промежутке закрашен не будет (см. рис. 6.4б). Эта небольшая неточность в большинстве случаев некритична и визуально незаметна. Формально алгоритм записывается так:

    Растеризовать контур многоугольника и вывести его на экран;
for(y = 1; y <= Y; y++)
      for(x = 1; x <= X - 1; x++)
            I(x + 1, y) = I(x + 1, y) XOR I(x, y);

    Если же требуется получить результат, соответствующий рис. 6.4а, то можно либо после закрашивания повторно вывести на экран контур многоугольника, либо воспользоваться следующей модификацией приведенного алгоритма (называемой "XOR с флагом"):

    Растеризовать контур многоугольника и вывести его на экран;

for(y = 1; y <= Y; y++)
{
      flag = 0;
      for(x = 1; x <= X; x++)
     {
            if( I(x, y) == 1 ) flag = 1 - flag;
            if( flag == 1 ) I(x, y) = 1;
      }
}

    Достоинством алгоритмов XOR является их предельная простота. Недостаток - невозможность работы при наличии посторонних изображений на экране.

    Исключительные случаи

    Остановимся теперь на способах исключения случаев, приведенных на рис. 6.1. В случае горизонтального ребра, очевидно, достаточно при растеризации этого ребра вывести лишь его концы.

    Для исключения остальных случаев можно поступить следующим образом. При растеризации каждого ребра многоугольника не будем выводить его нижний конец (x2, y2), а верхний конец выведем с помощью операции I(x1, y1) = I(x2, y2) XOR 1. Это приведет к тому, что верхние (нижние) концы ребер, попавшие в один и тот же пиксель, не будут выведены, а значит, "одиночные" точки в строках растра будут исключены.

    (рис 6.5) Шаги закрашивания многоугольника.

    Алгоритм с операцией XOR с перегородкой

    Алгоритм заключается в инвертировании цвета всех пикселей, расположенных правее i -го ребра, производимом последовательно для i = 1, 2, . . .N (порядок нумерации ребер не имеет значения). Горизонтальные ребра при этом игнорируются. Как видно из рис. 6.5, в результате закрашенными окажутся все внутренние пиксели многоугольника и только они.

    К достоинствам данного алгоритма можно отнести его простоту и оригинальность, а также отсутствие дополнительных структур данных. Недостатком является необходимость выполнения большого числа операций с пикселями (до N операций с каждым пикселем), в том числе и вне многоугольника. В частности, чем больше расстояние между многоугольником и правой границей экрана, тем больше будет совершено "лишних" операций.

    От этого недостатка свободна модификация данного алгоритма - "XOR-2 с перегородкой". Идея ее заключается в том, чтобы инвертировать область не между ребром и правой границей экрана, а между ребром и вертикальной прямой ("перегородкой"), мысленно проведенной в любом удобном месте - например пересекающей многоугольник (см. рис. 6.6).

    (рис 6.6) Растеризация с операцией XOR с перегородкой.

    6.3. Заполнение с затравкой

    Область, подлежащая заполнению, не всегда задается в виде многоугольника. В этом разделе мы рассмотрим случай, когда заполняемая область задается цветом своей границы. Множество пикселей на растре не задает область однозначно, поэтому требуется задать координаты "затравочного" пикселя, принадлежащего области.

    Алгоритмы, рассматриваемые в этом разделе, используют структуру данных под названием стек. Стек содержит упорядоченный набор элементов и поддерживает две основные операции: добавить элемент и извлечь элемент. Вторая операция возвращает элемент, добавленный последним, и удаляет его из набора элементов. Программно стек может быть реализован на основе одномерного массива.

    Простейший алгоритм заполнения с затравкой - это так называемый алгоритм короеда, получивший подобное название, поскольку заполняемая область последовательно "выедается" по одному пикселю. Он устроен следующим образом:

    //Заполняет цветом A область, ограниченную цветом B
Добавить затравочный пиксель в стек;
while(стек не пуст)
{
      P = стек.Извлечь(); //извлечение пикселя из стека
      Закрасить пиксель P;
      foreach(Q in соседние с P пиксели)
            if(цвет Q != B и Q еще не закрашен)
                  стек.Добавить(Q)
}

    При обходе соседних пикселей может рассматриваться и 4-связность ( Q принимает 4 значения), и 8-связность ( Q принимает 8 значений). В зависимости от этого результат будет различным.

    Внутри приведенного алгоритма производится проверка "Q еще не закрашен". Если известно, что пикселей цвета А внутри нашей области изначально не было, то это условие эквивалентно условию "цвет Q != A". В противном случае для проверки этого условия требуется введение специального буфера, где каждому пикселю соответствует флаг закраски, инициализируемый нулем и становящийся единицей при закраске пикселя.

    Пример работы алгоритма показан на рис. 6.7. 4-связная область закрашивается в серый цвет и ограничена темными пикселями. Пиксель P извлечен из стека. Он закрашивается серым. Соседние незакрашенные пиксели Q, R и S добавляются в стек.

    Используя пространственную когерентность, можно построить более эффективный алгоритм, использующий стек меньшей глубины и закрашивающий за одну итерацию целый горизонтальный отрезок пикселей:

    (рис 6.6) Алгоритм короеда.(рис 6.7) Заполнение с затравкой по отрезкам//Заполняет цветом A область, ограниченную цветом B
Добавить затравочный пиксель в стек;
while(стек не пуст)
{
      (X,Y) = стек.Извлечь(); //извлечение пикселя из стека
   
      X_min = X;
      while(цвет(X_min-1,Y) != B)
            X_min--;

      X_max = X;
      while(цвет(X_max+1,Y) != B)
            X_max++;

      Закрасить отрезок (X_min,Y)--(X_max,Y) цветом A;

      //обработка строки сверху
      флаг = 1;
      for(X = X_min; X <= X_max; X++)
      {
            if( цвет(X,Y-1) != B и (X,Y-1) еще не закрашен)
            {
                  if( флаг == 1 )
                  {
                        стек.Добавить(X,Y-1);
                        флаг = 0;
                  }
            }
            else
                  флаг = 1;
      }
      //обработка строки снизу
      флаг = 1;
      for(X = X_min; X <= X_max; X++)
      {
            if( цвет(X,Y+1) != B и (X,Y+1) еще не закрашен)
            {
                  if( флаг == 1 )
                  {
                        стек.Добавить(X,Y+1);
                        флаг = 0;
                  }
            }
            else
                  флаг = 1;
      }
}

    Пример работы алгоритма показан на рис. 6.8. Пиксель P - затравочный; 4-связная область закрашивается в серый цвет и ограничена темными пикселями. При первой итерации производится заполнение целого отрезка. Пиксели Q и R на строке сверху и S на строке снизу добавляются в стек.

    Заметим, что приведенные в данном разделе алгоритмы несложно переделать для перекрашивания с затравкой области постоянного цвета A в другой цвет B. Иными словами, для случая, когда область задается не цветом границы, а собственным цветом. В этом случае алгоритмы даже упрощаются: соседний пиксель добавляется в стек, только если он имеет цвет A (иначе он или не принадлежит перекрашиваемой области, или уже закрашен).

    (рис 6.8) Заполнение с затравкой по отрезкам.
    Страницы:

    6.1. Введение

    В предыдущих лекциях мы рассмотрели алгоритмы отображения линий на растре. Линии на растре зачастую образуют замкнутые области, которые требуется закрасить (заполнить) тем или иным цветом. В этой лекции мы рассмотрим алгоритмы, позволяющие выполнить такое заполнение.

    Будут рассмотрены два случая. В первом требуется нарисовать на растре многоугольник, заданный своими вершинами ( растеризация многоугольника ). Во втором, более общем случае мы будем считать, что растровая область задана цветом своей границы и точкой (пикселем) внутри области. Этот пиксель называется затравочным, а сам метод называется заполнением с затравкой.

    6.2. Растеризация многоугольников

    Пусть задан многоугольник P1P2 . . . PNP1 и требуется растеризовать его вместе с внутренними точками. Будем считать, что процедура отсечения (лекция 5) при необходимости была уже произведена и многоугольник целиком помещается в растровом окне. Для удобства каждое ребро многоугольника будем задавать координатами (x1, y1) и (x2, y2) его концов, так, что $$y_2 \ge y_1$$. Условимся также отсчитывать на экране координату x слева направо, а y - сверху вниз (таким образом, точка (x1, y1) будет верхним концом ребра, а (x2, y2) - нижним). Большинство алгоритмов заполнения основано на том факте, что любое горизонтальное сечение контура многоугольника состоит из четного числа точек. Это утверждение неверно в двух случаях (см. рис. 6.1):

  • когда секущая прямая содержит горизонтальное ребро;
  • когда она содержит вершину, а оба смежных ребра лежат выше (ниже) ее.
    •  (рис 6.1) Исключительные случаи.

    Однако существуют простые способы исключить эти случаи из рассмотрения; они будут рассмотрены позднее. Пока же будем считать, что приведенное утверждение справедливо всегда. Задача заполнения многоугольника, таким образом, сводится к заполнению определенных промежутков между точками сечения, что должно быть проделано для каждого горизонтального сечения многоугольника. Заметим, что при таком подходе никаких ограничений на свойства многоугольника (выпуклость, отсутствие самопересечений и т.д.) не накладывается.

    Алгоритм со списком реберных точек

    Этот алгоритм состоит из трех основных этапов.

    На первом этапе растеризуются все негоризонтальные ребра многоугольника. Все точки помещаются в списки. Для каждой координаты ymin, y2 . . . ymax сопоставим список x-координат всех пикселей, закрашенных при растеризации ребер, которые находятся на горизонтали y (здесь ymin и ymax - минимальная и максимальная y-координаты пикселей в растровом изображении многоугольника). Формально процедура описывается так:

    (рис 6.1) Пример сечений многоугольника.(рис 6.2) Растеризация реберforeach( ребро (x1, y1) - (x2, y2) in МножествоРебер )
{
      y = ceil(y1); // Округление до большего
      dx = (x2 - x1)/(y2 - y1);
      x = x1 + dx*(y - y1);

      while(y <= y2)
      {
            PutToList(x, y); // поместить x в список,
                                  // соответствующий данному y
            y++;
            x += dx;
      }
}

    На втором этапе для каждого y списки упорядочиваются по возрастанию. После этого для многоугольника, изображенного на рис. 6.2, списки будут выглядеть следующим образом:

    ymin x1, x2
    ymin + 1 x'1, x'2
    . . . . . .
    y0 x1 >>, x2 >>, x3 >>, x4 >>
    . . . . . .
    ymax

    На третьем этапе в каждой строке заполняются все отрезки вида [x2i-1, x2i].

    Алгоритм со списком активных ребер

    Попробуем несколько видоизменить предыдущий алгоритм. Вместо того чтобы хранить в памяти точки пересечения контура с каждой строкой растра, ограничимся лишь одной строкой - текущей. А именно, организуем список "активных" ребер (САР), в котором будем хранить информацию обо всех ребрах многоугольника, пересекаемых текущей строкой. Удобство такого подхода в том, что при переходе к новой строке не требуется полностью переформировывать САР. Достаточно лишь удалить из него "закончившиеся" ребра (то есть ребра из САР, чей нижний конец оказался выше нового значения y ) и добавить вновь появившиеся.

    Перейдем к формальному описанию алгоритма. Для каждого ребра создадим структуру данных:

    $$y = \lceil y_1 \rceil;$$ $$dx =\frac{x_2 - x_1}{y_2 - y_1};$$ $$x = x_1 + dx \cdot (y - y_1).$$

    Все такие структуры поместим в список (далее - y-список) и упорядочим его по возрастанию y.

    САР = пустой;
y = y_список[ первый элемент ].y;
do
{
      САР.Добавить( ребра из y-списка, у которых
                                 ребро.y = y);
      // сохраняя упорядоченность САР по возрастанию x
      y_список.Удалить( ребра, у которых ребро.y = y );

      Закрасить промежутки ( x_2i - 1, x_2i ) в строке y;
      y++;

      foreach( ребро из САР по порядку )
      {
            if(y > ребро.y2)
                  удалить ребро из САР;
            else
            {
                  ребро.x += ребро.dx;
                  while(соседнее_слева_ребро(ребро).x > ребро.x)
                        поменять местами в САР ребро с соседним;
            }
      }
}
while(САР не пуст);

    Ребра, помещенные в САР, удаляются из y-списка с той целью, чтобы свести проверку наличия в y-списке ребер, начинающихся с данного уровня y, к проверке этого условия для первого ребра в списке (это справедливо в силу упорядоченности списка). Цикл while используется для сохранения упорядоченности САР, которая может нарушиться при изменении значений x на dx.

    Пример такой ситуации показан на рис. 6.3. При ее возникновении указанный цикл выполняет локальную сортировку САР методом "пузырька".

    (рис 6.3) Локальная сортировка САР.

    Преимущество двух приведенных алгоритмов перед последующими состоит в том, что операции вывода на экран (относительно "медленные" во многих системах) для каждого пикселя выполняются не более одного раза. Недостатком является использование динамических структур данных (списков), что сильно усложняет код и требует дополнительной памяти.

    Существует класс систем, в которых использование динамических структур данных нежелательно (вследствие ограниченности ресурса памяти или отсутствия удобных средств разработки программ), в то время как замедление работы из-за частого обращения к видеопамяти некритично (сюда относятся, например, мобильные телефоны и другие портативные устройства, имеющие графический дисплей). В таких системах эффективным будет использование следующих алгоритмов, оперирующих непосредственно с данными в видеобуфере (то есть с "содержимым" экрана).

    Алгоритм с операцией XOR

    Этот оригинальный алгоритм использует свойства операции XOR (исключающее ИЛИ ). Напомним, что XOR - бинарная операция над битами, действующая по правилу:

    (рис 6.4) XOR-растеризация.
    a b a XOR b
    0 0 0
    0 1 1
    1 0 1
    1 1 0

    Пусть контур многоугольника растеризован и выведен на экран. Тогда его закрашивание сводится к заполнению в каждой строке растра всех промежутков вида [x2i-1, x2i], где через xk обозначены x-координаты "включенных" пикселей в данной строке, упорядоченные по возрастанию (см. рис. 6.4а).

    Через I(x, y) обозначим состояние пикселя с координатами (x, y): I(x, y) = 1, если пиксель "включен", и I(x, y) = 0 в противном случае. Нетрудно убедиться, что последовательное выполнение операции

    I(x + 1, y) = I(x, y)  XOR  I(x + 1, y)

    для x = 1, 2, 3, . . .X - 1 (где X - горизонтальный размер растра) приведет к требуемому результату - с той лишь разницей, что последний пиксель в каждом промежутке закрашен не будет (см. рис. 6.4б). Эта небольшая неточность в большинстве случаев некритична и визуально незаметна. Формально алгоритм записывается так:

    Растеризовать контур многоугольника и вывести его на экран;
for(y = 1; y <= Y; y++)
      for(x = 1; x <= X - 1; x++)
            I(x + 1, y) = I(x + 1, y) XOR I(x, y);

    Если же требуется получить результат, соответствующий рис. 6.4а, то можно либо после закрашивания повторно вывести на экран контур многоугольника, либо воспользоваться следующей модификацией приведенного алгоритма (называемой "XOR с флагом"):

    Растеризовать контур многоугольника и вывести его на экран;

for(y = 1; y <= Y; y++)
{
      flag = 0;
      for(x = 1; x <= X; x++)
     {
            if( I(x, y) == 1 ) flag = 1 - flag;
            if( flag == 1 ) I(x, y) = 1;
      }
}

    Достоинством алгоритмов XOR является их предельная простота. Недостаток - невозможность работы при наличии посторонних изображений на экране.

    Исключительные случаи

    Остановимся теперь на способах исключения случаев, приведенных на рис. 6.1. В случае горизонтального ребра, очевидно, достаточно при растеризации этого ребра вывести лишь его концы.

    Для исключения остальных случаев можно поступить следующим образом. При растеризации каждого ребра многоугольника не будем выводить его нижний конец (x2, y2), а верхний конец выведем с помощью операции I(x1, y1) = I(x2, y2) XOR 1. Это приведет к тому, что верхние (нижние) концы ребер, попавшие в один и тот же пиксель, не будут выведены, а значит, "одиночные" точки в строках растра будут исключены.

    (рис 6.5) Шаги закрашивания многоугольника.

    Алгоритм с операцией XOR с перегородкой

    Алгоритм заключается в инвертировании цвета всех пикселей, расположенных правее i -го ребра, производимом последовательно для i = 1, 2, . . .N (порядок нумерации ребер не имеет значения). Горизонтальные ребра при этом игнорируются. Как видно из рис. 6.5, в результате закрашенными окажутся все внутренние пиксели многоугольника и только они.

    К достоинствам данного алгоритма можно отнести его простоту и оригинальность, а также отсутствие дополнительных структур данных. Недостатком является необходимость выполнения большого числа операций с пикселями (до N операций с каждым пикселем), в том числе и вне многоугольника. В частности, чем больше расстояние между многоугольником и правой границей экрана, тем больше будет совершено "лишних" операций.

    От этого недостатка свободна модификация данного алгоритма - "XOR-2 с перегородкой". Идея ее заключается в том, чтобы инвертировать область не между ребром и правой границей экрана, а между ребром и вертикальной прямой ("перегородкой"), мысленно проведенной в любом удобном месте - например пересекающей многоугольник (см. рис. 6.6).

    (рис 6.6) Растеризация с операцией XOR с перегородкой.

    6.3. Заполнение с затравкой

    Область, подлежащая заполнению, не всегда задается в виде многоугольника. В этом разделе мы рассмотрим случай, когда заполняемая область задается цветом своей границы. Множество пикселей на растре не задает область однозначно, поэтому требуется задать координаты "затравочного" пикселя, принадлежащего области.

    Алгоритмы, рассматриваемые в этом разделе, используют структуру данных под названием стек. Стек содержит упорядоченный набор элементов и поддерживает две основные операции: добавить элемент и извлечь элемент. Вторая операция возвращает элемент, добавленный последним, и удаляет его из набора элементов. Программно стек может быть реализован на основе одномерного массива.

    Простейший алгоритм заполнения с затравкой - это так называемый алгоритм короеда, получивший подобное название, поскольку заполняемая область последовательно "выедается" по одному пикселю. Он устроен следующим образом:

    //Заполняет цветом A область, ограниченную цветом B
Добавить затравочный пиксель в стек;
while(стек не пуст)
{
      P = стек.Извлечь(); //извлечение пикселя из стека
      Закрасить пиксель P;
      foreach(Q in соседние с P пиксели)
            if(цвет Q != B и Q еще не закрашен)
                  стек.Добавить(Q)
}

    При обходе соседних пикселей может рассматриваться и 4-связность ( Q принимает 4 значения), и 8-связность ( Q принимает 8 значений). В зависимости от этого результат будет различным.

    Внутри приведенного алгоритма производится проверка "Q еще не закрашен". Если известно, что пикселей цвета А внутри нашей области изначально не было, то это условие эквивалентно условию "цвет Q != A". В противном случае для проверки этого условия требуется введение специального буфера, где каждому пикселю соответствует флаг закраски, инициализируемый нулем и становящийся единицей при закраске пикселя.

    Пример работы алгоритма показан на рис. 6.7. 4-связная область закрашивается в серый цвет и ограничена темными пикселями. Пиксель P извлечен из стека. Он закрашивается серым. Соседние незакрашенные пиксели Q, R и S добавляются в стек.

    Используя пространственную когерентность, можно построить более эффективный алгоритм, использующий стек меньшей глубины и закрашивающий за одну итерацию целый горизонтальный отрезок пикселей:

    (рис 6.6) Алгоритм короеда.(рис 6.7) Заполнение с затравкой по отрезкам//Заполняет цветом A область, ограниченную цветом B
Добавить затравочный пиксель в стек;
while(стек не пуст)
{
      (X,Y) = стек.Извлечь(); //извлечение пикселя из стека
   
      X_min = X;
      while(цвет(X_min-1,Y) != B)
            X_min--;

      X_max = X;
      while(цвет(X_max+1,Y) != B)
            X_max++;

      Закрасить отрезок (X_min,Y)--(X_max,Y) цветом A;

      //обработка строки сверху
      флаг = 1;
      for(X = X_min; X <= X_max; X++)
      {
            if( цвет(X,Y-1) != B и (X,Y-1) еще не закрашен)
            {
                  if( флаг == 1 )
                  {
                        стек.Добавить(X,Y-1);
                        флаг = 0;
                  }
            }
            else
                  флаг = 1;
      }
      //обработка строки снизу
      флаг = 1;
      for(X = X_min; X <= X_max; X++)
      {
            if( цвет(X,Y+1) != B и (X,Y+1) еще не закрашен)
            {
                  if( флаг == 1 )
                  {
                        стек.Добавить(X,Y+1);
                        флаг = 0;
                  }
            }
            else
                  флаг = 1;
      }
}

    Пример работы алгоритма показан на рис. 6.8. Пиксель P - затравочный; 4-связная область закрашивается в серый цвет и ограничена темными пикселями. При первой итерации производится заполнение целого отрезка. Пиксели Q и R на строке сверху и S на строке снизу добавляются в стек.

    Заметим, что приведенные в данном разделе алгоритмы несложно переделать для перекрашивания с затравкой области постоянного цвета A в другой цвет B. Иными словами, для случая, когда область задается не цветом границы, а собственным цветом. В этом случае алгоритмы даже упрощаются: соседний пиксель добавляется в стек, только если он имеет цвет A (иначе он или не принадлежит перекрашиваемой области, или уже закрашен).

    (рис 6.8) Заполнение с затравкой по отрезкам.
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^