Skip to content

8. Заполнение многоугольников. Алгоритмы заполнения по ребрам, с перегородкой, со списком ребер и флагом.

Jump to bottom
Pandas edited this page May 27, 2017 · 2 revisions

Алгоритм по рёбрам
фон = -закраска; закраска = -фон. Для каждой сканирующей строки, пересекающей ребро многоугольника, дополнить все пиксели, лежащие правее точки пересечения. Недостаток – каждый пиксель может перекрашиваться много раз.

Алгоритм с перегородкой
Для сокращения числа обрабатываемых пикселов используется ″перегородка". Рекомендуется проводить перегородку через одну из вершин многоугольника.

Если точка пересечения сканирующей строки с ребром лежит левее перегородки, то дополнить все пиксели правее точки пересечения, но левее перегородки. Если правее – дополнить левее пересечения, но правее перегородки.Недостатком алгоритма заполнения с перегородкой все же остается неоднократная обработка части пикселов.

Для того чтобы избавиться от этого, разработан модифицированный алгоритм заполнения сплошной области со списком ребер и флагом.
Imgur В обоих алгоритмах очерчивание границ не нужно.

Алгоритм с флагом

  1. Обработка ребер многоугольника, ограничивающего заполняемую область. Также, как в предыдущих алгоритмах, считается, что строки сканирования проходят через центр строк пикселов, то есть через середину интервала y. После определения пересечений вычисляем самый левый пиксел, расположенный правее точки пересечения, у которого абсцисса x больше абсциссы точки пересечения.
  2. Заполнение области. Для каждой строки сканирования, имеющей точки пересечения с многоугольником, ограничивающим область, выполняется следующая последовательность действий:
    а) f=0, (f-промежуточная переменная (флаг), показывающая расположение очередного пиксела: fl=0 - пиксел лежит вне области заполнения, fl=1 - пиксел лежит внутри заполняемой области);
    x=xl (xl - левая граница);
    б) пока (x<=xr ) (xr - правая граница) выполнить следующие действия:
    * если пиксел (x,y) имеет граничное значение , то проинвертировать значение переменной f (f=0, если было f=1; f=1, если было f=0);
    * если f=1, то присвоить пикселу (x,y) цвет многоугольника, в противном случае, присвоить пикселу (x,y) цвет фона;
    x=x+1.
    в) переход к следующей сканирующей строке y=y+1.
Clone this wiki locally