0

I implemented iterative floodfill algorithm, but the problem is that the algorithm is checking pixels which was already visited by my while loop and pushed on Stack. My question is how can I check if the pixel was on the stack or what can i do to make him much faster?

void FloodfillStack(int x, int y, BITMAP *ekran,ALLEGRO_COLOR newColor, ALLEGRO_COLOR startPixelColor){

    if (y < 0 || y > ScreenHeight || x < 0 || x > ScreenWidth)
        return;

    bool visited[ScreenHeight][ScreenWidth] = {false};

    struct stackElement *top;
    top = NULL;
    push(&top, x,y);
    visited[x][y] = true;
    int newX, newY;
    while (pop(&top, &newX, &newY))
    {
        visited[newX][newY] = true;
        if ((y < 0 || y > ScreenHeight || x < 0 || x > ScreenWidth) || compareColors(al_get_pixel(ekran, newX,newY), startPixelColor) == false)
            continue;
            al_put_pixel(newX,newY, newColor);
            if(visited[newX+1][newY] == false)
                push(&top, newX+1,newY);
            if(visited[newX-1][newY] == false)
                push(&top, newX-1,newY);
            if(visited[newX][newY+1] == false)
                push(&top, newX,newY+1);
            if(visited[newX][newY-1] == false)
                push(&top, newX,newY-1);
    }
}
Alchemisz
  • 67
  • 1
  • 8
  • Can we see your custom stack implementation and how compareColors works? – templatetypedef May 24 '20 at 20:01
  • ok, i added it to post – Alchemisz May 24 '20 at 20:04
  • 1
    Is ScreenHeight inclusive or exclusive? Should you be using >= instead of >? – templatetypedef May 24 '20 at 20:22
  • 1
    you are trashing memory management in `push,pop` ... you allocate each new pixel position in stack ... why not use fixed size buffer instead (priority que)? I do not clearly see pixel access you are using so check if it is also not slow (some implemetations are ...) – Spektre May 24 '20 at 20:33
  • Note: in `push()`, the body of `if(*top == NULL){` and `}else{` do the same thing. – chux - Reinstate Monica May 24 '20 at 20:35
  • 2
    Typically when doing flood fill, you can save a lot of push/pop by pushing and popping horizontal sequences of pixels rather than single pixels – HAL9000 May 24 '20 at 22:57
  • 1
    @HAL9000 exactly here an example [Paint algorithm leaving white pixels at the edges when I color](https://stackoverflow.com/a/37810355/2521214) – Spektre May 25 '20 at 06:11

0 Answers0