Построчный алгоритм заполнения многоугольника с затравкой (Билдер С++)

[SKA_zo4nik]

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

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

Есть многоугольник (или же его надо самому нарисовать). И программа заполняет его данным алгоритмом.

Заранее спасибо. Очень прошу помочь.

[mutabor]

Можно поподробнее, что значит с затравкой?

[Virtson]

это значит что дается внутренний пиксель, и от него пляшем ...
заливка в Painte - это она и есть

[mutabor]

Ну раз построчный, то построчно и заполняй. Сделай двойной цикл for и в нем проверяй цвет пикселей, если цвет равен заданному меняй его. Похоже на перебор матрицы. Еще нужна будет проверка принадлежности пикселя к многоугольнику.

[Virtson]

http://www.yandex.ru/yandsearch?text...BA%D0%BE%D0%B9

[SKA_zo4nik]

спасибо большое. Буду разбираться.

[SKA_zo4nik]

А у кого-нить есть сам код такой программы на С++? А то мне по коду проще разобраться.........очень нужно...

[SKA_zo4nik]

а как задается затравочный пиксел? вообще не представляю себе, как все должно происходить

[erhan777]

есть код Delfi

unit Unit1;
interface
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
type
  StackPix = record
    x: integer;
    y: integer;
  end;
  TForm1 = class(TForm)
    Button1: TButton;
    procedure FormPaint(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
var
  Form1: TForm1;
  arrStack: array of StackPix;
implementation
uses Math;
{$R *.dfm}
procedure pushStack(pxl: StackPix);
begin
SetLength(arrStack, Length(arrStack)+1);
arrStack[High(arrStack)]:=pxl;
end;
function popStack():StackPix;
begin
if High(arrStack)>=0 then
  begin
  popStack:=arrStack[High(arrStack)];
  SetLength(arrStack, High(arrStack));
  end
end;
procedure www(npxl:StackPix; Xmax:integer);
var
  fl: boolean;
  pc: TColor;
  i: integer;
begin
  while npxl.x <= Xmax do
    begin
      fl:=false;
      pc:=Form1.canvas.Pixels[npxl.x,npxl.y];
      while ((pc <> clBlack) and (pc <> clred) and (npxl.x < Xmax)) do
        begin
          if fl=false then fl:=true;
          npxl.x:=npxl.x+1;
          pc:=Form1.canvas.Pixels[npxl.x,npxl.y];
        end;
      if fl=true then
        begin
          if (npxl.x=Xmax) and (pc <> clBlack) and (pc <> clGreen) then
             pushStack(npxl)
          else
             begin
             npxl.x:=npxl.x-1;
             pushStack(npxl);
             end;
    //    fl:=false;
        end;
      i:=npxl.x;
      pc:=Form1.canvas.Pixels[npxl.x,npxl.y];
      while (((pc=clBlack) or (pc=clGreen)) and (npxl.x<Xmax)) do
        begin
          npxl.x:=npxl.x+1;
          pc:=Form1.canvas.Pixels[npxl.x,npxl.y];
        end;
 
      if npxl.x=i then npxl.x:=npxl.x+1;
  end;
end;
procedure nearby(pxl: StackPix);
var
  pc: TColor;
begin
pc:=Form1.canvas.Pixels[pxl.x,pxl.y];
if (pc <> clBlack) and (pc <> clRed) then pushStack(pxl);
end;
procedure TForm1.FormPaint(Sender: TObject);
begin
canvas.Pen.Color:=clBlack;
canvas.MoveTo(100,115);
canvas.LineTo(180,115);
canvas.LineTo(280,115);
canvas.LineTo(280,270);
canvas.LineTo(230,270);
canvas.LineTo(70,270);
canvas.LineTo(20,270);
canvas.LineTo(20,115);
canvas.LineTo(200,115);
end;
procedure TForm1.Button1Click(Sender: TObject);
var
  pxl: StackPix;
  npxl: StackPix;
  i:integer;
  color: TColor;
begin
  Button1.Enabled:=false;
  pxl.x:=270;
  pxl.y:=118;
  pushStack(pxl);
  while High(arrStack)>-1 do
    begin
    case i  of
    0: color:=clblack;
    1: color:=clblack;
    2: color:=clblack;
    3: color:=clblack;
    4: color:=clblack;
    5: color:=clblack;
    end;
    pxl:=popStack;
    i:=RandomRange(0,5);
    canvas.Pixels[pxl.x,pxl.y]:=color;

    npxl.x:=pxl.x-1;
    npxl.y:=pxl.y;
    nearby(npxl);
 
    npxl.x:=pxl.x+1;
    npxl.y:=pxl.y;
    nearby(npxl);
 
    npxl.x:=pxl.x;
    npxl.y:=pxl.y-1;
    nearby(npxl);
 
    npxl.x:=pxl.x;
    npxl.y:=pxl.y+1;
    nearby(npxl);
    end;
 Button1.Enabled:=true;
end;
end.

Но вообще по сути алгоритм предусматривает работу со стеком прямого действия (стеком с дисциплиной обслуживания FILO), т.е.

first input last output (по принципу патронов в магазине). Принцип работы алгоритма следующий:

Поместить затравочный пиксел в стек

Пока стек не пуст

Извлечь пиксел из стека

Присвоить пикселу требуемое значение

Для каждого из соседних к текущему 4-х связных пикселов проверить: является ли он граничным пикселом или не присвоено ли уже пикселу требуемое значение. Проигнорировать пиксел в любом из этих двух случаев. В противном случае поместить пиксел в стек.

На псевдокоде это можно представить таким образом:

Затравка (х, у) выдает затравочный пиксел

Push – процедура, которая помещает пиксел в стек

Pop – процедура, которая извлекает пиксел из стека

Пиксел (х, у) = Затравка (х, у)

инициализируем стек

Push Пиксел (х, у)

while (стек не пуст)

извлекаем пиксел из стека

Pop Пиксел (х, у)

if Пиксел (х, у) < > Нов_значение then

Пиксел (х, у) = Нов_значение

end if

проверим, надо ли помещать соседние пикселы в стек

if (Пиксел (х + 1, у) < > Нов_значение and

Пиксел (х + 1, у) < > Гран_значение) then

Push Пиксел (х + 1, у)

if (Пиксел (х, у + 1) < > Нов_значение and

Пиксел (х, у + 1) < > гран_значение) then

Push Пиксел (х, у + 1)

if (Пиксел (х – 1, у) < > Нов_значение and

Пиксел (х – 1, у) < > Гран_значение) then

Push Пиксел (х – 1, у)

if (Пиксел (х, у – 1) < > Нов_значение and

Пиксел (х, у – 1) < > гран_значение) then

Push Пиксел (х, у – 1)

end if

end while

Простой алгоритм с затравкой не всегда применим, ввиду большого размера стека.