Алгоритми заповнення області з затравкою

В алгоритмах заповнення області з затравкою використовується інший підхід. У них передбачається, що границя області задана на растровій площині і зазначена одна з внутрішніх точок області, що має назву затравочна. Потрібно заповнити визначеним кольором зв’язну компоненту області, що містить затравочний пісел. Можна представити, що в затравочній точці знаходиться джерело, що заливає всю область визначеним кольором. Тому цей процес іноді називають заливанням області.

Опишемо алгоритм заповнення області з затравкою, що використовує стек. Під стеком розуміється лінійний масив (список) елементів, причому вставки і видалення елементів можна робити лише з одного кінця, тобто якщо елемент був вставлений у список останнім, він повинний бути оброблений і видалений із списку першим.

Алгоритм заповнення з затравкою по рядках

Застосуємо ідею сканування по рядках для розвязання задачі заповнення. Зауважимо, що на кожному рядку міститься деяка множина пікселів, що мають бути зафарбованими, і вона складається з інтервалів, що належать області. Ці інтервали відокремлені друг від друга інтервалами з пікселів, що належать границі або зовнішності області. Крім того, якщо набір пікселів утворює інтервал, що належить внутрішній частині області, тоді піксели над і під цим інтервалом або являються граничними, або належать внутрішній частині області. Останні можуть служити в якості затравочних пікселів для рядків, що лежать вище і нижче розглянутого рядка. Приймаючи до уваги сказане, можна запропонувати наступну схему заповнення області.

Ініциалізуємо стек, вміщуючи в нього затравочний піксел. Поки стек не порожній:

1. виймаємо піксел (x,y) із стека;

2. заповнюємо максимально можливий інтервал, у якому знаходиться піксел, вправо і вліво аж до досягнення граничних пікселів;

3. запам'ятовуємо крайню ліву Lx і крайню праву Rx абсциси заповненого інтервалу;

4. у сусідніх рядках над і під інтервалом (Lx,Rx) знаходимо незаповнені до дійсного часу внутрішні піксели області, що, як ми вже зауважили, об'єднані в інтервали, а в кожному з цих інтервалів знаходимо крайні праві піксели. Кожний із цих пікселів вносимо в стек у якості пікселу затравки.

Цей алгоритм буде правильно заповнювати будь-яку область, у тому числі й таку, у якій присутні отвори.

{Рор(x,y) – процедура, що виймає зі стека координати чергового піксела,

Push(x,y) – процедура, що поміщає в стек координати піксела,

C(x,y) – колір піксела з координатами (x,y),

Cb – колір границі,

Ci – колір внутрішньої області,

(x0,y0) – координати затравочного піксела.}

Push(x0,y0);

While {стек не порожній} do

Begin

{виймаємо піксел із стека та ініциалізуємо його}

Pop(x,y);

C(x,y):=Ci;

Xm:=x; {запам'ятовуємо абсцису піксела затравки}

While c(x,y) <> Cb {заповнюємо інтервал справа}

Begin

C(x,y):=Ci;

X:=x+1

End;

Rx:=x-1; {запам'ятовуємо крайній справа піксел інтервалу}

X:=xm; {відновлюємо абсцису піксела затравки}

While c(x,y) <> Cb do {заповнюємо інтервал зліва}

Begin

C(x,y):=Ci;

X:=x-1

End;

Lx:=x+1; [запам'ятовуємо крайній справа піксел інтервалу]

X:=xm; {відновлюємо абсцису піксела затравки}

{знаходимо затравочні піксели на нижньому рядку, починаючи з лівого краю інтервалу (Lx,Rx), потім ту ж операцію проробляємо на верхньому рядку}

for j:=-1 step 2 to 1 do

begin

y:=y+1;

x:=Lx;

while x <= Rx do

begin

Empty:=false;

While (c(x,y) <> Cb) and (c(x,y) <> Ci) and (x < Rx) do

{внутрішня точка не заповнена}

begin

if not Empty then Empty:=true;

x:=x+1

end;

{крайній справа піксел вміщуємо в стек}

if Empty then

begin

if (x = Rx) and (c(x,y) <> Cb) and (c(x,y) <> Ci) then

Push(x,y)

Else

Push(x-1,y);

Empty:=false

End;

{шукаємо інші незаповнені інтервали в рядку}

xb:=x;

while (c(x,y) = Cb) or (c(x,y) = Ci) and (x < Rx) do

if x = xb then x:=x+1

end

end {for}

end.