Boundary fill algorithm in C not working (Computer Graphics - C Programming)

Question

I'm trying to implement the simple boundary fill method (using 4 connected approach) for filling a rectangle. I did it as follows (code below), but the rectangle is not getting filled properly: it stops filling when it reaches the half portion of the rectangle.

But the same code works fine when trying to fill a circle. Can anyone help me to figure out the problem?

Thanks in advance

#include <stdio.h>
#include <conio.h>
#include <graphics.h>

void boundfill(int xc, int yc, int r, int b) {
    int cur;
    cur = getpixel(xc, yc);
    if (cur != b && cur != r) {
        putpixel(xc, yc, r);
        delay(1);

        boundfill(xc + 1, yc, r, b);
        boundfill(xc - 1, yc, r, b);
        boundfill(xc, yc + 1, r, b);
        boundfill(xc, yc - 1, r, b);
    }
}

void main() {
    int gd = DETECT, gm;
    initgraph(&gd, &gm, "..\\bgi");

    rectangle(100, 100, 300, 300);
    boundfill(105, 105, 4, WHITE);

    getch();
    closegraph();
}

Output:

But when I use the following co-ordinates for rectangle, it is working fine. Given co-ordinates:

rectangle(50, 50, 100 ,100);
boundfill(55, 55, 4, WHITE);

For this the output is:

Answer 1

What platform are you using?

• is this 32 or 16 bit executable?

BGI is very old Borland gfx API still used for learning purposes if it is original Borland BGI then you are creating 16bit DOS app. There are also wrappers/emulators of BGI for Windows and Linux in that case it depend on your compiler settings.

What can be wrong:

1. heap/stack

   in 16bit DOS mode you can see just first 1 MB of memory space from which is 640KB available for whole system. In your program/project/compiler settings there are additional constraints like initial/maximum heap and stack size for your app. If set too low then you can have heap stack problems in that case it should throw an exception but in my experience I see a lot stranger things then missing exceptions.

   When you filling 100x100 pixel area you are recursing up to 10000 times and your recursion call (16bit case) contains:

   1 x return address segment+offset = 4 Byte
   4 x int16 operand = 8 Byte
   1 x int local variable = 2 Byte
   

   all together 14 Byte (on some C/C++ engines truncated to 16 Bytes) not counting additional data need for subcalls like putpixel ... Multiply it by recursion count and you are well above safety for sure on 16 bit DOS. To check this:

   • the filling should stop on the same spot each time (if no more processing is in your code)
   • if you add some variables into function header it should stop sooner then before
   • change of heap/stack limit should affect this also

   to repair this eliminate all unnecessary tings from recursion for example b,r are constant so they can be in global variable. If you set xc,yc back to original state before return then you can use &xc,&yc. Your cur local variable can be static. This will eliminate all allocations in your recursion only the return address remain.

2. gfx mode

   BGI is mostly used for 16 color modes on higher resolutions you are crossing 64KB barriers. If there is something wrong with your BGI driver it could hang up or stop drawing. In that case the stop will occur on the same place no matter the bullet #1. To avoid this change BGI driver, use different resolution or better emulator

Answer 2

Without additional information - this smells just like a stack overflow. My assumption is based on the following:

1. Your algorithm is excessively recursive.
2. The problem arises for a larger rectangle
3. The filling pattern you provided in consistent with the assumption that your program just preliminary "stopped" (crashed actually). That is, your recursion path is filling horizontally first, and then vertically.

Taking the discussion of the effectiveness of this specific filling algorithm aside, note that using recursive algorithms in general is justified only when the recursion depth has reasonable limitation.

For example, using recursion on balanced binary trees is ok, since such a tree depth (and hence recursion depth) grows logarithmically with the tree size. On the other hand using recursion for linked list operation isn't justified.

If you insist on using this specific algorithm, I believe you should get rid of recursion. You may put your starting point in a queue, and then in a loop pop a point from the queue, paint, and push its neighbors into the queue. Similar to BFS algorithm.