Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

Control Flow

2 (2.2%)

Arrays, Strings, Pointers, and References

8 (9%)

Functions

4 (4.5%)

Basic object-oriented programming

30 (33.7%)

A bit more advanced OOP (Composition, Operator overloading, Inheritance, Virtual Functions)

18 (20.2%)

Templates

8 (9%)

Other (Explain)

4 (4.5%)

Working with files?  (Streams)

15 (16.9%)

Total Members Voted: 89

[Normandy]

The "recently filled pixels" is usually denoted by a pixel of the same color as you're trying to fill. Most simple flood-fill algorithms do that since it's probably the easiest way to do it.

EDIT:

@ILikePie:
I don't see where you're getting that sentiment from. If we thought you were a moron, would we be helping you?

[Siquo]

Spoiler (click to show/hide)

No, I got it, PM back is being written

The problem with just using the color as "recently filled" is that you can have a barrier of the fill color. If you have white-red-white, and I fill the left white red, the other white should not fill. Or I don't understand what you just said

[qwertyuiopas]

How about this? It would compile if it had a main()...
I didn't go so far as to test it in OpenGL, but it probably works.

Spoiler: long (click to show/hide)

Code: [Select]

typedef struct
{
    unsigned char r, g, b;
} RGB;

typedef struct
{
    unsigned int width, height;
    RGB *data;
} canvas;

typedef struct
{
    unsigned int first;
    unsigned int next;
    unsigned int max;
    int *data;
} queue;

int init_queue(queue *Queue, unsigned int initial_size)
{
    if(!Queue || initial_size < 1)
      return 0;
    Queue->first = 0;
    Queue->next = 0;
    Queue->max = initial_size;
    Queue->data = malloc(initial_size*sizeof(unsigned int)*2);
    if(!Queue->data)
      return 0;
    return 1;
}

void queue_append(queue *q, int x, int y)
{
    if(q->next < q->max)
    {
        q->data[q->next*2] = x;
        q->data[q->next*2+1] = y;
        q->next++;
    }
    else
    {
        //realloc, unfortunately, does not have the ability to do partial copies...
        int *new = malloc(q->max*2*sizeof(unsigned int)*2);
        if(!new)
        {
            if(q->first > 0)
            {
                memmove(q->data, &(q->data[q->first*2]), (q->max-q->first)*2*sizeof(int));
                q->next -= q->first;
                q->first = 0;
            }
            else return;//cannot make space. What should happen depends on the program, here we will ignore the pixel and hope to get it later.
        }
        else
        {
            memcpy(new, &(q->data[q->first*2]), (q->max-q->first)*2*sizeof(int));
            free(q->data);
            q->data = new;
            q->next -= q->first;
            q->first = 0;
            q->max *= 2;
        }
        q->data[q->next*2] = x;
        q->data[q->next*2+1] = y;
        q->next++;
    }
}

int in_queue(queue *q, int x, int y)
{
    if(!q || x<0 || y<0)
      return 0;
    int i;
    for(i=q->first;i<q->next;i++)
    {
        if(q->data[i*2]==x && q->data[i*2+1]==y)
          return 1;
    }
    return 0;
}

int queue_next(queue *q, int *x, int *y)
{
    if(q->first == q->next)
      return 0;
    *x = q->data[q->first*2];
    *y = q->data[q->first*2+1];
    q->first++;
    if(q->first == q->next)
      q->first=q->next=0;
    return 1;
}

int in_bounds(int x, int y, canvas *c)
{
    if(!c || x < 0 || y < 0 || x >= c->width || y >= c->height)
      return 0;
    else
      return 1;
}

RGB get_colour(int x, int y, canvas *c)
{
    return c->data[y*c->width+x];
}

int is_colour(int x, int y, canvas *c, RGB *colour)
{
    return memcmp(&(c->data[y*c->width+x]), colour, sizeof(RGB)) == 0;
}

void set_colour(int x, int y, canvas *c, RGB *new)
{
    c->data[y*c->width+x] = *new;
}

void floodfill_add(queue *q, int x, int y, canvas *c, RGB *target)
{
    if(in_bounds(x, y, c) && is_colour(x, y, c, target) && !in_queue(q, x, y))
      queue_append(q, x, y);
}

void floodfill(int x, int y, canvas *Canvas, RGB *newcolour)
{
    //Check first for bad pointers, then bad locations.
    if(!Canvas || !newcolour || !Canvas->data || !in_bounds(x, y, Canvas))
      return;
    queue Queue;
    if(!init_queue(&Queue, 512))
      return;
    RGB target_colour = get_colour(x, y, Canvas);
    queue_append(&Queue, x, y);
    while(queue_next(&Queue, &x, &y))
    {
        set_colour(x, y, Canvas, newcolour);
        floodfill_add(&Queue, x+1, y, Canvas, &target_colour);
        floodfill_add(&Queue, x-1, y, Canvas, &target_colour);
        floodfill_add(&Queue, x, y+1, Canvas, &target_colour);
        floodfill_add(&Queue, x, y-1, Canvas, &target_colour);
    }
}


[DrPizza]

What? There is precisely nothing that can be done recursively that cannot be done in an iterative manner.

That's not a useful statement.

Every iterative function can be trivially transformed to a recursive one.

The reverse is not true, however. Converting a recursive function to an iterative one requires explicit maintenance of a stack. This is fiddly at best for simple recursive functions, and a complete pain in the ass for mutually recursive functions.

Now, every tail recursive function can be trivially transformed to an iterative one, but not all functions are tail recursive. You can sorta-kinda make them all tail recursive with CPS, but that has all sorts of complexities of its own.

Iteration may be faster in many circumstances, but oftentimes the recursive solution is simpler and easier to read, and this consideration is almost always the more important one.

[Siquo]

@querty Nice, except... (there I go)

You add every pixel 4 times, and all into the same queue. Which makes a 10 by 10 px fill a queue of 400*sizeof(RGB), and a 256 by 256 fill a size of 262144 RGB's. Whereas my solution continuously discards already written pixels. Which could be a performance hit in itself, but uses less memory at the same time.
FAKEEDIT: ok, my fault, you do an in-queue check so you don't get the 4-times multiplier, but you do iterate over the entire queue for every add, which is even worse, as you now iterate 262144+262143+262142+262141+ ... 3+2+1 times 2 over the queue to check if it's not already in...

[qwertyuiopas]

Except that they are removed once read, so it must only go over <perimeter> entries. For a 256x256 square, that will remain fairly low, under 2000, and for oddly shaped other things, it will depend on the shape, but still shouldn't be that bad.
The biggest issue I see is that often it will reallocate when a simple move would be adaquate.

Agh, and I forgot the most important one of all, the check to see that target colour != fill colour.

[Siquo]

Except that they are removed once read, so it must only go over <perimeter> entries. For a 256x256 square, that will remain fairly low, under 2000, and for oddly shaped other things, it will depend on the shape, but still shouldn't be that bad.
The biggest issue I see is that often it will reallocate when a simple move would be adaquate.

Agh, and I forgot the most important one of all, the check to see that target colour != fill colour.

Yep, you're right, didn't see that in queue_next, sorry et mea maxima culpa.

Good challenge by the way, ilikepie, I liked it
Targetcolor == fillcolor should return as soon as it's called, for every fillfunction.

[Normandy]

The last time I wrote a fill function was about a year and a half ago, and the article I read said to immediately return the floodFill() function if the chosen pixel's color is not equal to the previous color, or more importantly, equal to the fill color. There will be only three cases when the pixel's color will equal the flood fill color:

1) The pixel is already that color, and hence the flood fill doesn't need to act
2) The pixel was originally that color, and hence not part of the original flood fill region
3) The pixel was set that color by the flood-fill function, and thus has already been visited

Hence, the only checking you need to do is whether or not the pixel is equal to the original color or not equal to the flood filled color. I'm not sure this applies to hardware accelerated stuff because accessing RGB values directly requires a software buffer - but that's not of concern, and I'm way out of my league when talking about that.

As well, you may want to replace std::list by std::stack or std::queue, because the latter two are more idiomatic to what is actually happening. In the recursive floodFill() function, it's functionally the same as doing the iterative function using a stack instead of a queue (hence, the "stack"). When you do the queue version, you get a modified behavior.

[ILikePie]

Good challenge by the way, ilikepie, I liked it

Wait, wait, wait, wait... I think I missed something.

[Toady One]

Please try to keep it polite in here.  Siquo and Supermikhail have been warned for their insults.

[Siquo]

Duly noted, my apologies.

@iLikePie: well, thinking about the floodfill was fun to do

@normandy, Yeah, you're right. The fill only needs one colorcheck, and I didn't really look at what container was necessary. A stack would've been just as good. So far I just used map, list and vector, as they are the only three with really different access. Stack, queue, deque, etc. I've never really had a use for.

[Normandy]

Argh. Facepalm. Okay, I want to translate an image, right? Sounds simple: I have a large image, and want to move the borders of the image by a certain amount, sort of like panning a viewport. In fact, it's exactly like panning a viewport over a map. The problem: when I try something simple like this (this is in Java, but the concepts are more or less universal):

Code: [Select]

Graphics2D g2d = imgbuf.createGraphics();
AffineTransform atr = new AffineTransform();
atr.translate(-dx, -dy);
g2d.drawImage(imgbuf, atr, null);
It works, but only when translating down and/or right of the screen. Going up and/or left, because it overwrites the image data as it draws on the image, unexpected behavior happens. It completely aggravates me that it works in this one direction, but not the other.

Anyone have a solution to this quandary? Surely there is some hardware accelerated way for safely translating and blitting an image onto itself that doesn't involve copying the entire image buffer?

[Dakorma]

I had a small/vague question. How long does it take to learn how to make things like Minecraft?

[Normandy]

I've been programming as a hobby for four years now, and I'm just beginning to be able to pull off even vaguely complex programs now, if that's any indication of anything. Though to be fair, I am still in school (not in computer science) and my learning time is limited.

[eerr]

I had a small/vague question. How long does it take to learn how to make things like Minecraft?

with experiance in what? nothing??