Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Как в алгоритме избежать рекрусии?

Автор: Sergio 8.8.2008, 19:51

Здраствуйте. Есть алгоритм:

Код


DoRock(struct Image* image, int x, int y, int color, int range_color)
{
    int current_color = imgGetPixel(image, x, y);

    if(current_color != range_color && current_color != color)
    {
        imgSetPixel( image, x, y, color);

        DoRock(image, x+1, y, color, range_color);
        DoRock(image, x-1, y, color, range_color);
        DoRock(image, x, y+1, color, range_color);
        DoRock(image, x, y-1, color, range_color);
    }
}

Как видите используется рекрусия.
Мне нужно избежать этого. Помогите плз с задачей smile

Заранее спасибо.

Автор: bsa 8.8.2008, 20:01

Sergio, сделай очередь. Функция в цикле обрабатывает каждую запись очереди, добавляя в конец другие записи, если необходимо.

Автор: andrew_121 8.8.2008, 20:19

Сам удалил.

Автор: source777 8.8.2008, 20:47

Либо я не понял хитровыдуманности вашего алгоритма(ты бы его словами что-ль описал...), либо нахрена там рекурсия???

Код


ReplaceColorsExceptRange(struct Image* image, int color, int range_color)
{
    int current_color;
    for (int x = 0; x < image.Width; x++)
       for (int y = 0; y < image.Height; y++)
      {
         current_color = imgGetPixel(image, x, y); 
         if(current_color != range_color && current_color != color)
         {
            imgSetPixel( image, x, y, color);
         }
      }
}

Автор: maxim1000 8.8.2008, 20:52

Цитата(source777 @ 8.8.2008, 20:47

)

Либо я не понял хитровыдуманности вашего алгоритма

я бы сказал, что это - обычная заливка

Автор: Partizan 8.8.2008, 20:53

source777, +1 любая рекурсия представима в виде цикла.

Автор: source777 8.8.2008, 21:45

Цитата(maxim1000 @ 8.8.2008, 20:52

)

я бы сказал, что это - обычная заливка

Ну не скажи, она как минимум необычная, ведь цвет почти каждой точки дёргается(imgGetPixel) по 5 раз в варианте Sergio. Вот я и спросил зачем это делается? Да и в конце остаётся только 2 цвета, т.е. уже монохроматизация какая-то, а не заливка...
Так же интересно было бы услышать обоснование рекурсивного захламления стека неизменяемыми параметрами color, range_color. А также пояснение названия метода(DoRock), мне лично сразу представился листинг с кучей идентификаторов типа DoRock, DoRock1, DoRock2,..., DoWork, DoSomething, DoSomethingElse smile

Автор: Partizan 8.8.2008, 21:48

source777,
DoRock можно перевести на русский язык как "Отжечь" smile

Автор: source777 8.8.2008, 21:55

Цитата(Partizan @ 8.8.2008, 21:48

)

source777,
DoRock можно перевести на русский язык как "Отжечь" smile

Спасибо за пояснение, теперь наконец-то ясно что делает данный метод, он просто "отжигает" smile

Автор: Sergio 8.8.2008, 23:33

maxim1000,Вы правы. Это алгоритм заливки
Partizan, код в студию. Я не очень знаю как это реализовать в моём случае smile

Использовал рекурсию потому что важно быстро залить объэкт

Есть нарисованая фигура напрмер вот такая:
http://ipicture.ru/

Нужно её залить вот так:
http://ipicture.ru/

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

Автор: Mayk 9.8.2008, 15:58

Цитата(Sergio @ 9.8.2008, 03:33

)

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

Сказали же.

Цитата(bsa @ 9.8.2008, 00:01

)

Sergio, сделай очередь.

Чем не подходит?

Автор: Sergio 10.8.2008, 21:36

Цитата

Sergio, сделай очередь.

Mayk, как это реализовать? smile

Можешь помочь с существующим уже кодом?

Автор: Sartorius 10.8.2008, 21:58

Код


for(int y = 0; y < maxY; y++)
{
bInside = false;
 for (int x = 0; x < maxX; x++)
 {
   if (color(x, y) == borderColor) 
   {
      bInside = !bInside; 
      for (;color(x,y) == borderColor, x < maxX; x++);
      --x;
      continue;
    }
    if (bInside) setColor(x,y, fillColor);
 }
}

если фигура не пересекает границу то покатит...

Автор: bsa 11.8.2008, 16:13

Цитата(Sergio @ 10.8.2008, 21:36)

Mayk, как это реализовать? smile

Можешь помочь с существующим уже кодом?

http://www.sgi.com/tech/stl/queue.html

Код

#include <queue>

struct Point
{
    Point(int x, int y) : x_(x), y_(y){}
    int getX() const { return x_; }
    int getY() const { return y_; }
private:
    int x_;
    int y_;
};

typedef std::queue<Point> PointQueue;

...

DoRock(struct Image* image, int x, int y, int color, int range_color)
{
   PointQueue pq;
   pq.push( Point(x, y) );
   while(!pq.empty()) {
      const Point &p = pq.front();
      int current_color = imgGetPixel(image, p.getX(), p.getY());
      if(current_color != range_color && current_color != color) {
          imgSetPixel(image, p.getX(), p.getY(), color);
          pq.push( Point(p.getX() - 1, p.getY()) );
          pq.push( Point(p.getX() + 1, p.getY()) );
          pq.push( Point(p.getX(), p.getY() - 1) );
          pq.push( Point(p.getX(), p.getY() + 1) );
      }
      pq.pop();
   }
}