Заливка ограниченной области

[ex.cluz]

Прочитал лекцию (по ссылке). И очень рад! Я сам до этого додумался за 20минут шевелением извилинами (их итог - пост #21).
На радостях пойду спать.

[mutabor]

Там все точно, работает как часы. Не спеши просто и вдумчиво почитай. Возьми тетрадку в клетку, нарисуй фигуру, и проследи работу алгоритма с ручкой в руках, и все поймешь.

при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел

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

В диапазоне от Xлев до Xправ в выше и нижележащей строке

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

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

[Alex Cones]

Да, кстати мне не понятно насчет разрывов. Мы же ищем крайние точки следуя от другой строки, как тогда закрашивается это:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[mutabor]

Сообщение от Alex Cones

Да, кстати мне не понятно насчет разрывов. Мы же ищем крайние точки следуя от другой строки, как тогда закрашивается это:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Это запоминается в стек на потом. Алгоритм выполняется пока не опустеет стек, а по ходу выполнения стек бывает доходит до семи, восьми, в зависимости от сложности фигуры, т.е. все найденные по ходу ответвления (от разрывов или хвостов) записываются в стек, и ждут своей очереди.

Я хотел свою функцию привести как пример, но как глянул на нее, передумал, не тянет она на пример, там сотни строк кода, только запутает, я ведь не заливку делал, а просто как за основу взял алгоритм этот и понавешивал на него кучу всего.

[Alex Cones]

Все таки я еще не до конца понял формирования очереди в стеке. На псевдоязыке можете подробно рассказать? Pls

[mutabor]

Он на самом деле не такой сложный, вот он полностью

Занести координаты затравочного пиксела в стек;
While стек не пуст

* Взять координаты затравки из стека;
* Перекрасить пиксел;
* Закрасить строку вправо и влево от затравки пока не встретится уже закрашенный или граничный пиксел;
* Запомнить координаты крайних закрашенных пикселов Xлев и Xправ;
* В диапазоне от Xлев до Xправ в выше и нижележащей строке отыскиваются крайние правые пикселы в еще незакрашенных сегментах.
* Координаты отысканных пикселов запоминаются в стеке как затравки.

Endwhile

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

[mutabor]

Вот, нашел код, на к-ром я тренировался, тут только заливка, ничего лишнего

procedure TForm1.FillExScanLine(bm: TBitmap; p: TPoint);
//построчный алгоритм заливки
var
  stack: TObjectStack;
  ps: TPos;
  t1, t2: cardinal;
  xl, xr: integer; //координаты крайних левых и правых пикселей в закрашиваемой строке
  x, y: integer; //закрашиваемая строка
  srcColor: cardinal;
  StartSeq: boolean; //признак, что начата последовательность

  p1: PByteArray;
  clr: cardinal; //цвет из массива ScanLine, для удобства
begin
  //ShowMessage(GetEnumName(TypeInfo(TPixelFormat), Ord(bm.PixelFormat)));
  bm.PixelFormat:=pf24bit;
  //ShowMessage(GetEnumName(TypeInfo(TPixelFormat), Ord(bm.PixelFormat)));
  Screen.Cursor:=crHourGlass;
  t1:=GetTickCount;

  srcColor:=bm.Canvas.Pixels[p.x, p.y]; //запоминаем исходный цвет затравочного пиксела

  stack:=TObjectStack.Create;
  stack.Push(TPos.Create(p.X, p.Y)); //занести координаты затравочного пиксела в стек

  while stack.Count > 0 do begin //пока стек не пуст

    ps:=stack.Pop as TPos; //Взять координаты затравки из стека

    bm.Canvas.Pixels[ps.x, ps.y]:=clWhite; //Перекрасить пиксел

    //закрашиваем вправо
    xr:=ps.x;
    y:=ps.y;
    p1:=bm.ScanLine[y]; //эта строка действительна также и в следующем блоке
    clr:=RGB(p1[(xr+1)*3+2], p1[(xr+1)*3+1], p1[(xr+1)*3]);
    while clr = srcColor do begin
      Inc(xr);
      p1[xr*3+2]:=255;
      p1[xr*3+1]:=255;
      p1[xr*3]:=255;
      clr:=RGB(p1[(xr+1)*3+2], p1[(xr+1)*3+1], p1[(xr+1)*3]);
    end;

    //закрашиваем влево
    xl:=ps.x;
    clr:=RGB(p1[(xl-1)*3+2], p1[(xl-1)*3+1], p1[(xl-1)*3]);
    while clr = srcColor do begin
      Dec(xl);
      p1[xl*3+2]:=255;
      p1[xl*3+1]:=255;
      p1[xl*3]:=255;
      clr:=RGB(p1[(xl-1)*3+2], p1[(xl-1)*3+1], p1[(xl-1)*3]);
    end;

    //теперь в xl и xr находятся правая и левая координаты закрашенной строки

    //в пределах диапазона xl - xr ищем интервалы в верхней и нижней строке
    //и помещаем крайние правые точки их в стек, как затравочные

    //в верхней
    y:=ps.y-1;
    p1:=bm.ScanLine[y];
    StartSeq:=false;
    for x := xl to xr do begin
      clr:=RGB(p1[x*3+2], p1[x*3+1], p1[x*3]);
      if clr = srcColor then begin
        StartSeq:=true;
        if x = xr then //помещаем крайнюю правую (здесь последнюю) точку в стек
          stack.Push(TPos.Create(xr, y));
      end
      else
        if StartSeq then begin
          stack.Push(TPos.Create(x-1, y)); //помещаем крайнюю правую точку в стек
          StartSeq:=false;
        end;
    end;

    //в нижней
    y:=ps.y+1;
    p1:=bm.ScanLine[y];
    StartSeq:=false;
    for x := xl to xr do begin
      clr:=RGB(p1[x*3+2], p1[x*3+1], p1[x*3]);
      if clr = srcColor then begin
        StartSeq:=true;
        if x = xr then //помещаем крайнюю правую (здесь последнюю) точку в стек
          stack.Push(TPos.Create(xr, y));
      end
      else
        if StartSeq then begin
          stack.Push(TPos.Create(x-1, y)); //помещаем крайнюю правую точку в стек
          StartSeq:=false;
        end;
    end;

    //bm.Canvas.TextOut(0,0,'Stack: '+IntToStr(stack.Count));
    //PaintBox1.Canvas.Draw(0,0,bm);
    //Sleep(50);
  end;

  stack.Free;

  t2:=GetTickCount;
  ShowMessage(IntToStr(t2-t1)+' ms');
  Screen.Cursor:=crDefault;
end;

Прям захотелось на базе этого прямо сейчас градиент замутить, но я все же наверное спать пойду