Закрас попиксельно.

[NSvirus]

Приветствую, очень важная для меня тема.

Есть абсолютна любая фигура, есть точка внутри ее. Нужно ореентируясь от точки закрасить все что внутри фигуры.

Выполняя это задание столкнулся с небольшими проблемами.
Во первых использование массива (640, 480) - размеры экрана "великовато", во вторых производительность данного алгоритма не велика.
Вот небольшой набросок:

for N:=1 to 640 do //перебор для проверки на значения в массиве =30, если есть - точка не обрабатывается, если какое-то значение = 10 - обработка.
  begin
    for t:=1 to 480 do
    begin
      if a[N,t]=10 then
      begin
        x1:=N,x2:=N,y1:=t,y2:=t; //запись во вторичные координаты
        x1:=x1-1; //проверяем соседние координаты на наличие запретной линии
        x2:=x2+1;
        y1:=y1-1;
        y2:=y2+1;
          repeat
             f1:=Getcolor(x1,t); // проверка цвета
             f2:=getColor(x2,t);
             f3:=getColor(n,y1);
             f4:=getColor(n,y2);
             if f1=black(цвет фона)  then
                begin
                   a[x1,t]:=10; // метка перекрашенной клетки
                   putPixel(x1,t,green); 
                   x1:=x1-1; 
                end;
             if f2=black(цвет фона)  then
                begin
                   a[x2,t]:=10;
                   putPixel(x2,t,green);
                   x2:=x2+1;
                end;
             if f3=black(цвет фона)  then
                begin
                   a[n,y1]:=10;
                   putPixel(n,y1,green);
                   y1:=y1-1;
                end;
             if f4=black(цвет фона)  then
                begin
                   a[n,y2]:=10;
                   putPixel(n,y2,green);
                   y2:=y2+1;
                end;
          until not(f1=black) and not(f2=black) and not(f3=black) and not(f4=black) // пока все пути не врежутся в запретную линию
       a[N,t]=30 //обработанная точка метится для запрета последующей обработки.
end;end;end.

Нечто такое сотворил я, больше ничего придумать не смог, есть у кого идеи? Может уже существует оригинальный алгоритм без заморочек?

[EducatedFool]

Есть абсолютна любая фигура

А как она задана? Только массив с координатами точек?
Точки расположены в случайном порядке, или в порядке следования?

Если порядок точек в массиве случайный, то результат в общем случае неопределён:

[Smitt&Wesson]

У тебя идёт просмотр всего поля рисунка. В этом и кроется причина неэффективности алгоритма. На практике применяют способ обхода контура. От точки координат, с которой надо производить закрашивание, делается N шагов до нахождения 1-края рисунка; 2-пикселя закрашенного другим цветом. После этого, делается обход контура. Только проверок на окружение будет не 4 а 8. Поскольку закрашиваемая область всегда меньше общей площади рисунка, алгоритм работает быстрее.

[puporev]

Не понял к чему такие мучения. Если цвет контура и цвет закраски отличаются, то рисуем фигуру цветом закраски, floodfill(), перерисовываем фигуру изначальным цветом.

[Smitt&Wesson]

Сообщение от puporev

Не понял к чему такие мучения. Если цвет контура и цвет закраски отличаются, то рисуем фигуру цветом закраски, floodfill(), перерисовываем фигуру изначальным цветом.

А если не отличаються?
Сравнивать надо контур с цветом фона и заполнять цветом закраски.

[puporev]

А если не отличаються?

Тогда просто floodfill();

[puporev]

На всякий случай, перед floodfill нужно setfillstyle();

[NSvirus]

Тогда просто floodfill();

нет, нужно закрасить без оператора floodfill. Нужно написать алгоритм закрашивания самому.

А как она задана? Только массив с координатами точек?
Точки расположены в случайном порядке, или в порядке следования?

мы рисуем фигуру по формуле или обычными line.

У тебя идёт просмотр всего поля рисунка. В этом и кроется причина неэффективности алгоритма. На практике применяют способ обхода контура. От точки координат, с которой надо производить закрашивание, делается N шагов до нахождения 1-края рисунка; 2-пикселя закрашенного другим цветом. После этого, делается обход контура. Только проверок на окружение будет не 4 а 8. Поскольку закрашиваемая область всегда меньше общей площади рисунка, алгоритм работает быстрее.

Если пользоваться таким алгоритмом, получится(смотрим на картинку EducatedFool): находим точку - E6 и красим F6, а нам этого не нужно. + Если обход идет на 8 сторон, то выход за контур рисунка обеспечен(опять смотрим на тот же рисунок): Пусть заданная точка G9- здесь проверятся точка H8, которая тоже закрашивается, в результате - чушь.

[Tronix]

Если с английским и сями дружите - то вот, вполне подробно: http://www.academictutorials.com/gra...flood-fill.asp Если скорость не нужна, то самая обычная рекурсия. Процедура в пять строк.

[Arigato]

Набросал пример в Делфи.
Процедура заливки:

procedure TFMain.MyFill (X, Y: Integer);
var
  LX, RX: Integer;
begin
  with Canvas do
  begin
    LX := X;
    RX := X;
    while Pixels[LX,Y] = clWhite do Dec (LX);
    while Pixels[RX,Y] = clWhite do Inc (RX);
    Inc (LX);
    Dec (RX);
    MoveTo (LX, Y);
    LineTo (RX + 1, Y);
    for X := LX to RX do
    begin
      if Pixels[X,Y-1] = clWhite then MyFill (X, Y - 1);
      if Pixels[X,Y+1] = clWhite then MyFill (X, Y + 1);
    end; {for}
  end; {with}
end; {proc TFMain.MyFill}

Достаточно лобовое решение, при желании может быть оптимизировано. Но суть решения подобных задач показывает.
Можно было бы рисовать не линиями, а точками, проверяя 4 направления от каждой точки, но тогда при больших областях будет переполняться стек.

P.S. В примере: левой кнопкой мыши - рисовать, правой - заливать.