VPF::Как в алгоритме избежать рекрусии?

Sergio

Дата 8.8.2008, 19:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: 0
Всего: 1

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

Код


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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

andrew_121

Дата 8.8.2008, 20:19 (ссылка)

(нет голосов)

Загрузка ...

Кодофей

Профиль
Группа: Завсегдатай
Сообщений: 3448
Регистрация: 3.1.2008

Репутация: 6
Всего: 33

Сам удалил.

Это сообщение отредактировал(а) andrew_121 - 8.8.2008, 23:04

--------------------

Удалил аккаунт. Прощайте!

source777

Дата 8.8.2008, 20:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1878
Регистрация: 12.3.2007

Репутация: 1
Всего: 56

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

Код


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);
         }
      }
}

Это сообщение отредактировал(а) source777 - 8.8.2008, 20:50

--------------------

Если бы программистам платили за то, чтобы убирать код из программы вместо того, чтобы добавлять его, программы были бы намного лучше © Николас Негропонте

maxim1000

Дата 8.8.2008, 20:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 17
Всего: 110

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

)

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

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

--------------------

qqq

Partizan

Дата 8.8.2008, 20:53 (ссылка)

(нет голосов)

Загрузка ...

Let's do some .NET

Профиль
Группа: Модератор
Сообщений: 2828
Регистрация: 19.12.2005
Где: Санкт-Петербург

Репутация: 4
Всего: 67

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

--------------------

СУВ,
Partizan.

source777

Дата 8.8.2008, 21:45 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1878
Регистрация: 12.3.2007

Репутация: 1
Всего: 56

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

)

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

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

Это сообщение отредактировал(а) source777 - 8.8.2008, 21:51

--------------------

Partizan

Дата 8.8.2008, 21:48 (ссылка)

(нет голосов)

Загрузка ...

Let's do some .NET

Профиль
Группа: Модератор
Сообщений: 2828
Регистрация: 19.12.2005
Где: Санкт-Петербург

Репутация: 4
Всего: 67

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

--------------------

СУВ,
Partizan.

source777

Дата 8.8.2008, 21:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1878
Регистрация: 12.3.2007

Репутация: 1
Всего: 56

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

)

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

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

--------------------

Sergio

Дата 8.8.2008, 23:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: 0
Всего: 1

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

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

Есть нарисованая фигура напрмер вот такая:

Нужно её залить вот так:

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

Это сообщение отредактировал(а) Sergio - 9.8.2008, 13:27

Mayk

Дата 9.8.2008, 15:58 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

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

)

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

Сказали же.

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

)

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

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

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

Sergio

Дата 10.8.2008, 21:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 843
Регистрация: 28.7.2006
Где: Solar System-> Earth

Репутация: 0
Всего: 1

Цитата

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

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

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

Sartorius

Дата 10.8.2008, 21:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Код


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);
 }
}

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

Это сообщение отредактировал(а) Sartorius - 10.8.2008, 22:09

bsa

Дата 11.8.2008, 16:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 63
Всего: 196

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

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

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

std::queue

Код

#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();
   }
}

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »