Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Qt и кроссплатформенное программирование С/С++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.03.2020, 15:04   #1
Мaкс
Форумчанин
 
Регистрация: 12.06.2018
Сообщений: 831
По умолчанию Не работает алгоритм FloodFill.

Всем привет. Хочу сделать инструмент заливка для графического редактора. Застрял на алгоритме. Помогите, пожалуйста.
Примечания:
seachColor - цвет поиска (QColor), а fillColor - цвет заполнения.
display - переменная QImage.
Код:
void ToolFill::paintProcess(QPoint point) {
     /* Теория алгоритма из википедии:
     1. Присвоить Q пустую очередь.
     2. Если цвет элемента - не заменяемый цвет, возврат.
     3. Поместить элемент в Q.
     4. Для каждого N из элементов Q:
     5.  Если цвет N - заменяемый цвет:
     6.   Присвоить w и e тот же элемент, что и N.
     7.   Смещать w на запад до тех пор, пока цвет w не станет отличаться от цвета "заменяемый цвет" .
     8.   Смещать e на восток до тех пор, пока цвет e не станет отличаться от цвета "заменяемый цвет".
     9.   Всем элементам между w и e придать цвет заливки.
    10.   Для каждого n между w и e:
    11.    Если цвет элемента к северу от n - заменяемый цвет, поместить этот элемент в Q.
           Если цвет элемента к югу от n - заменяемый цвет, поместить этот элемент в Q.
    12. Продолжать цикл, пока в Q останутся элементы.
    13. Возврат. {разумеется, в пп. 7, 8, а также 11 можно встретить края массива}
    */
    QStack<QPoint> pixels;
    if(seachColor == fillColor) return;
    pixels.push(point);
    while(!pixels.empty()) {
        if(display->pixelColor(pixels.top()) == seachColor) {
            QPoint w, e;
            w = e = pixels.top();
            while(display->pixelColor(w) == seachColor) w.setX(w.x()-1);
            while(display->pixelColor(e) == seachColor) e.setX(e.x()+1);
            for(int ind = w.x(); ind <= e.x(); ind++) display->setPixelColor(ind, w.y(), fillColor);
            for(int width = w.x(); width <= e.x(); width++) {
                if(display->pixelColor(width, w.y()-1) == fillColor) pixels.push(QPoint(width, w.y()-1));
                if(display->pixelColor(width, w.y()+1) == fillColor) pixels.push(QPoint(width, w.y()+1));
            }
        }
    }
    update();
}
Т.е. вообще где то программа зациклилась. Зависает.
P.S. Я не могу сам что то сделать, потому что я его не очень понимаю на данный момент.

Последний раз редактировалось Мaкс; 28.03.2020 в 15:09.
Мaкс вне форума Ответить с цитированием
Старый 28.03.2020, 19:52   #2
waleri
Старожил
 
Регистрация: 13.07.2012
Сообщений: 6,493
По умолчанию

Я не вникал, но на первый взгляд - кто, когда и где будет убирать элементы из стека?
waleri на форуме Ответить с цитированием
Старый 28.03.2020, 19:55   #3
Мaкс
Форумчанин
 
Регистрация: 12.06.2018
Сообщений: 831
По умолчанию

Цитата:
Сообщение от waleri Посмотреть сообщение
Я не вникал, но на первый взгляд - кто, когда и где будет убирать элементы из стека?
Вот и я не очень понял, не вник.
Мaкс вне форума Ответить с цитированием
Старый 29.03.2020, 13:47   #4
Мaкс
Форумчанин
 
Регистрация: 12.06.2018
Сообщений: 831
По умолчанию

Помогите пожалуйста! Не могу понять логику алгоритма!

Последний раз редактировалось Мaкс; 29.03.2020 в 13:49.
Мaкс вне форума Ответить с цитированием
Старый 29.03.2020, 13:59   #5
Subst
Пользователь
 
Регистрация: 30.01.2020
Сообщений: 54
По умолчанию

Макс,
ну черт знает как там с алгоритмом по сути..
Но как тебе уже Валерий сказал, из стека не достаются элементы. Никогда.

Ты первым делом пихаешь туда инициализирующий Пиксель, а потом запускаешь цикл while (стек не пуст), в котором только добавляются в стек элементы. И никогда не достаются.

Явно, что-то пошло не так
Subst вне форума Ответить с цитированием
Старый 29.03.2020, 14:15   #6
Мaкс
Форумчанин
 
Регистрация: 12.06.2018
Сообщений: 831
По умолчанию

Да, Вы первую ошибку нашли. Есть и вторая. Где сравниваются пиксели w и e, там вместо fillColor нужно seachColor (По логике).
Рабочая версия:
Код:
void ToolFill::paintProcess(QPoint point) {
    QStack<QPoint> pixels;
    if(seachColor == fillColor) return;
    pixels.push(point);
    while(!pixels.empty()) {
        if(display->pixelColor(pixels.top()) == seachColor) {
            QPoint w, e;
            w = e = pixels.top();
            while(display->pixelColor(w) == seachColor) w.setX(w.x()-1);
            while(display->pixelColor(e) == seachColor) e.setX(e.x()+1);
            for(int ind = w.x(); ind <= e.x(); ind++) display->setPixelColor(ind, w.y(), fillColor);
            for(int width = w.x(); width <= e.x(); width++) {
                if(display->pixelColor(width, w.y()-1) == seachColor) pixels.push(QPoint(width, w.y()-1));
                if(display->pixelColor(width, w.y()+1) == seachColor) pixels.push(QPoint(width, w.y()+1));
            }
            /*for(int height = w.y(); height <= e.y(); height++) {
                if(display->pixelColor(w.x(), height-1) == fillColor) pixels.push(QPoint(w.x()-1, height));
                if(display->pixelColor(w.x(), height+1) == fillColor) pixels.push(QPoint(w.x()+1, height));
            }*/
        }
        pixels.pop();
    }
    update();
}
Хоть и не идеально быстро работает... Я очень рад.
Мaкс вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Не работает алгоритм поиска:(( godmym Помощь студентам 1 18.03.2017 22:41
Не работает FloodFill sunny-plum Мультимедиа в Delphi 6 08.12.2014 07:45
помогите закрасить треугольник,используя floodfill I_R_I_A_N_A Помощь студентам 0 04.05.2014 15:15
floodfill Акоб Паскаль, Turbo Pascal, PascalABC.NET 5 09.11.2011 16:18
Не закрашивается область. ( FloodFill) vedro-compota Мультимедиа в Delphi 5 05.06.2010 20:05