3
\$\begingroup\$

Inspired by this question, here's some C code to check if a point is "inside" of a shape on a simple black and white bitmap.

For this exercise:

  • Set bits form the "outlines" of a shape (and are never inside).
  • Unset bits may be inside or outside of a shape.
  • Unset bits with a path to the edge of the bitmap are "outside".
  • Unset bits with no path to the edge of the bitmap are "inside".
  • Paths may step diagonally between set bits.

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void die() { __debugbreak(); }
void die_if(bool condition) { if (condition) die(); }

struct bitmap
{
    size_t m_w;
    size_t m_h;
    bool* m_pixels;
};

struct bitmap bitmap_from_string(size_t width, size_t height, char const* str)
{
    die_if(!str);
    die_if(strlen(str) != width * height);

    bool* pixels = malloc(sizeof(bool) * width * height);
    die_if(!pixels);

    char const* src = str;
    bool* dst = pixels;

    char const set = '#';
    for (size_t i = 0; i != width * height; ++i)
        *dst++ = (*src++ == set ? true : false);

    return (struct bitmap){ width, height, pixels };
}

bool bitmap_is_in_bounds(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    return (x < bmp->m_w) && (y < bmp->m_h);
}

bool bitmap_at(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    return bmp->m_pixels[y * bmp->m_w + x];
}

bool bitmap_is_at_edge(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    return (x == 0 || y == 0 || x == (bmp->m_w - 1) || y == (bmp->m_h - 1));
}

void bitmap_free(struct bitmap* bmp)
{
    die_if(!bmp);

    free(bmp->m_pixels);
    bmp->m_pixels = NULL;
}

/* bitmap_is_in_shape
 *    A "shape" is composed of unset bits, fully enclosed (on axes and 
 * diagonally) by set bits (so there should not exist a path of unset bits from 
 * the start point to the edge of the bitmap).
 *    Start points on set bits are not considered to be "inside" a shape.
 */
bool bitmap_is_in_shape(struct bitmap* bmp, size_t x, size_t y)
{
    die_if(!bmp);
    die_if(!bitmap_is_in_bounds(bmp, x, y));

    /* trivial rejection */
    if (bitmap_at(bmp, x, y)) return false; /* on outline */
    if (bitmap_is_at_edge(bmp, x, y)) return false; /* at edge */

    /* depth first search */
    struct coords { size_t x, y; };

    size_t stack_size = 0;
    struct coords* stack = malloc(sizeof(struct coords) * bmp->m_w * bmp->m_h); /* coords to visit next */
    die_if(!stack);

    bool* visited = calloc(bmp->m_w * bmp->m_h, sizeof(bool)); /* points added to stack - indexed the same as bitmap pixels */
    die_if(!visited);
    
    visited[y * bmp->m_w + x] = true; /* start point already visited */

    /* for each neighbour... */
#define N(c_x, c_y) \
    X(c_x, c_y, -1, -1) \
    X(c_x, c_y, -1,  0) \
    X(c_x, c_y, -1, +1) \
    X(c_x, c_y,  0, -1) \
    X(c_x, c_y,  0, +1) \
    X(c_x, c_y, +1, -1) \
    X(c_x, c_y, +1,  0) \
    X(c_x, c_y, +1, +1)

    /* check visited list and push to stack */
#define X(c_x, c_y, o_x, o_y) \
    if (!visited[(size_t)(c_y + o_y) * bmp->m_w + (size_t)(c_x + o_x)]) \
    { \
        visited[(size_t)(c_y + o_y) * bmp->m_w + (size_t)(c_x + o_x)] = true; \
        stack[stack_size++] = (struct coords){ (size_t)(c_x + o_x), (size_t)(c_y + o_y) }; \
    }

    N(x, y); /* add neighbours */

    bool result = true;

    while (stack_size != 0)
    {
        struct coords c = stack[--stack_size]; /* pop */

        if (bitmap_at(bmp, c.x, c.y)) continue; /* on outline */
        if (bitmap_is_at_edge(bmp, c.x, c.y)) { result = false; break; } /* at edge */

        N(c.x, c.y); /* add neighbours */
    }

#undef X
#undef N

    free(stack);
    free(visited);

    return result;
}

void test(bool expected, bool actual, char const* name)
{
    printf("%s: %s\n", name, (expected == actual ? "pass" : "FAIL"));
}

int main()
{
    {
        struct bitmap bmp = bitmap_from_string(1, 1, "#");

        test(false, bitmap_is_in_shape(&bmp, 0, 0), "one pixel - set");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(1, 1, " ");

        test(false, bitmap_is_in_shape(&bmp, 0, 0), "one pixel - unset");

        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(3, 3,
            "###"
            "# #"
            "###");

        test(false, bitmap_is_in_shape(&bmp, 0, 1), "three pixel - on outline"); 
        test(true, bitmap_is_in_shape(&bmp, 1, 1), "three pixel - bounded");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(3, 3,
            "###"
            "# #"
            "## ");

        test(false, bitmap_is_in_shape(&bmp, 0, 1), "three pixel - on outline"); 
        test(false, bitmap_is_in_shape(&bmp, 1, 1), "three pixel - middle w/ outlet");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(8, 4,
            "########"
            "###### #"
            "#      #"
            "########");
        
        test(true, bitmap_is_in_shape(&bmp, 1, 2), "corridor - start"); 
        test(true, bitmap_is_in_shape(&bmp, 6, 1), "corridor - end");
        test(false, bitmap_is_in_shape(&bmp, 3, 1), "corridor - on outline");
        
        bitmap_free(&bmp);
    }
    {
        struct bitmap bmp = bitmap_from_string(8, 4,
            "##### ##"
            "###### #"
            "# #    #"
            "########");
        
        test(true, bitmap_is_in_shape(&bmp, 1, 2), "corridor - room");
        test(false, bitmap_is_in_shape(&bmp, 3, 2), "corridor - start");
        test(false, bitmap_is_in_shape(&bmp, 6, 1), "corridor - end");
        test(false, bitmap_is_in_shape(&bmp, 3, 1), "corridor - on outline");
        
        bitmap_free(&bmp);
    }
}

Some things:

  • The X macro was fun to use... but feels a little messy. Especially adding the offset to the coordinates.

  • I like to use assert-type checks (die_if()) everywhere... but is it too much? Often there's a check in a higher-level function (e.g. bitmap_is_in_shape() checks that the bitmap isn't null) that makes all the following lower-level checks redundant (e.g. in bitmap_at() checks it again).

    Would having two versions of lower-level access functions (e.g. bitmap_at() and bitmap_at_unsafe()) be silly?

  • Any other C-ish things (especially more modern stuff) that's missing?

Any other feedback welcome. :)

\$\endgroup\$

2 Answers 2

Reset to default
4
\$\begingroup\$

This looks like a very reasonable attempt at solving the problem. You are using a flood fill instead of counting the number of shape edges crossed, and that avoids a whole lot of issues, although it therefore won't be very fast.

Unnecessary conversion from string to bitmap?

Converting the input string to an array of bool is not doing anything useful. Why not just let your algorithm work on the original string? You can do this easily by writing:

struct bitmap {
    size_t m_w;
    size_t m_h;
    char const* m_pixels;
};

bool bitmap_at(struct bitmap* bmp, size_t x, size_t y)
{
    return bmp->m_pixels[y * bmp->m_w + x] == '#';
}

Also note that a bitmap is usually understood to use only one bit per pixel, and that would reduce the amount of storage necessary by a factor 8.

Consider pre-processing the bitmap

It should not be very hard to modify your code to pre-process the bitmap once, so that it stores for every pixel whether it is in a shape or outside it. For example, you can use the algorithm you have, but have it flood-fill from the edge. At the end, all the visited pixels should be outside the shapes, the unvisited pixels are inside shapes.

Make functions that should not be public static

Helper functions that should not be called from other source files should be made static. This can help the compiler generate more optimal code, and will avoid possible linking errors if other parts of the program want to use the same function or variable name.

Use assert()

Instead of writing your own function like die() and die_if(), just use the standard function assert(). Debuggers should be able to break when that function is called.

Another nice thing of assert() is that it is a macro that will do nothing if NDEBUG is defined, so you can use that to make a release build that does not have the overhead of the checks everywhere. That also means it's OK to use assert() a lot, as this will help find bugs faster during development.

However, don't use assert() for things that should always be checked, even in optimized release builds. For example, when checking whether malloc() succeeded. In those cases, I'd recommend writing an explicit check, and think a bit more about what action to take in case of failure. Do you really need to abort the program in such a case, or can you recover gracefully?

Useless ternary

In this line:

*dst++ = (*src++ == set ? true : false);

The ternary expression is totally useless. You are checking something that is already either true or false, so you can just write:

*dst++ = *src++ == set;

Avoid macros

The X-macro is not necessary. You can create an array with all the 8 offsets, and just use a regular for-loop to call the code that needs to be repeated. For example:

static const struct {
    int x;
    int y;
} offsets[8] = {
    {-1, -1},
    {-1, 0},
    ...
};

for (int i = 0; i < 8; i++) {
    int x = c_x + offsets[i].x;
    int y = c_y + offsets[i].y;
    size_t idx = y * bmp->m_w + x;

    if (!visited[idx]) {
        visited[idx] = true;
        stack[stack_size++] = (struct coords){x, y};
    }
}

Consider using recursion

Whenever you create a stack manually, ask yourself if you need to do it. Your computer is already managing a stack for you when you run the program, so maybe you can just use that? Split off the part of bitmap_is_in_shape() that recursively call itself:

static bool recurse(struct bitmap* bmp, bool* visited, size_t x, size_t y)
{
    if (bitmap_is_at_edge(bmp, x, y))
        return false;

    size_t idx = bmp->m_w * y + x;

    if (visited[idx] || bitmap_at(bmp, x, y))
        return true;
    else
        visited[idx] = true;

    static const struct {...} offsets[8] = {...};

    for (int i = 0; i < 8; i++) {
         // Recursively check neighbors, but exit as soon as we have reached the edge.
         if (!recurse(bmp, visited, x + offsets[i].x, y + offsets[i].y))
             return false;
    }

    return true;
}

bool bitmap_is_in_shape(struct bitmap* bmp, size_t x, size_t y)
{
    ...
    bool* visited = calloc(bmp->m_w * bmp->m_h, sizeof(bool));
    bool result = recurse(bmp, visited, x, y);
    free(visited);
    return result;
}

The drawback is that you could exceed the amount of stack space available, on the other hand it will probably use much less memory than you did when reserving an array of m_w * m_h elements.

\$\endgroup\$
3
  • \$\begingroup\$ Good review. Still found more and a slightly different approach to the neighbors. \$\endgroup\$ Commented May 8, 2021 at 21:56
  • 1
    \$\begingroup\$ Thanks for the review. I was under the impression it was a good thing to have checks with the same behavior in both debug and release builds. (Otherwise I won't catch issues like failed memory allocation in release builds. Perhaps there's not much difference between die() and just crashing, but it's a lot easier to reason about what happens). \$\endgroup\$ Commented May 9, 2021 at 7:25
  • 1
    \$\begingroup\$ @user673679 You are right, you shouldn't use assert() in those cases. I've updated the answer. \$\endgroup\$ Commented May 9, 2021 at 7:55
4
\$\begingroup\$

@G.Sliepen already gave quite a few points to consider.
Still, there is a bit more, some points to elaborate, and some with a different interesting solution:

  1. As he said, your die() is equivalent to assert(0), and die_if(!expr) is equivalent to assert(expr) unless NDEBUG is defined.

    The diagnostic is probably not as nice, and the code is not removed in release-mode.

    While most of the checks should be replaced by assert(), a few don't indicate a programming error, and thus should always kill the program, but never break into the debugger. Which I would expect die() to do, after giving an appropriate error-message.

  2. Avoid sizeof(TYPE). Nearly always, you can use sizeof *pointer instead, which avoids repeating information and possibly getting it wrong. Or not getting it changed everywhere at once should that become necessary.

  3. Decide whether you want to pass your struct bitmap by value or by reference. Currently, there is no upside to passing it by reference, though you still do so sometimes.

  4. You could work with a single linear coordinate for most of your algorithm. It wouldn't change anything but free up resources and simplify some computations.

  5. If you put the start-point on the open stack, you don't have to mark its neighbors. One macro eliminated. Simplicity!

  6. Managing your open stack would be simpler if you used two pointers (stack and top) instead of (stack and size).

  7. A simple loop is much better than using macros to repeat the same code over and over.

    The other answer has one option using a lookup-table. Considering only 8 very short integers (they fit a nibble each) are needed, one (or two) 64-bit value and some bit-shifting lead to another quite performant solution.

  8. I'm sad to say but many of your comments are obvious.

    The problem is that they neither describe why you do something, nor summarize a bigger part of the picture. A single line, or even a few if they are that uncomplicated, are trivially understood without a comment which can be stale.

  9. While I understand that in C++ when member-functions grow too big, a prefix or suffix for member-variables can at least alleviate the confusion, importing that wart into C which only has free functions is needless clutter displacing more useful naming. Even in C++, the proper remedy is extracting functions and other refactorings leading to smaller functions.

Below just the modified core function, assuming all others accept struct bitmap by value. If you want to follow the suggestion of pre-processing and / or directly working with the source, feel free to start from here.

void die(const char* p) {
    if (p) fprintf(stderr, "Fatal Error: %s\n", p)
    exit(1);
}
bool bitmap_is_in_shape(struct bitmap bmp, size_t x, size_t y) {
    assert(bitmap_is_in_bounds(bmp, x, y));

    if (bitmap_at(bmp, x, y) || bitmap_is_at_edge(bmp, x, y)) return false;
    size_t* const stack = malloc(sizeof *stack * bmp.m_h * bmp.m_w);
    stack || die("Failed to allocate memory.");
    size_t* top = stack;

    bool *visited = calloc(bmp.m_h * bmp.m_w, sizeof *visited);
    visited || die("Failed to allocate memory.");

    *top++ = y * bmp.m_w + x;
    visited[y * bmp.m_w + x] = true;

    bool result = true;

    while (stack != top) {
        size_t linear = *--top;
        if (bitmap_is_at_edge(bmp, linear % bmp.m_w, linear / bmp.m_w)) {
            result = false;
            break;
        }
#if 1
        for (uint64_t which = 0x01011e021e0101ff; which; which >>= 8) {
            linear += (signed char)(which & 0xf0) / 16;
            linear += (signed char)((which << 4) & 0xf0) / 16 * bmp.m_w;
#else
        for (uint64_t x = 0x00000100010000ff, y = 0x0101fe02fe0101ff; y; x >>= 8, y >>= 8) {
            linear += (signed char)x;
            linear += (signed char)y * bmp.m_w;
#endif
            if (!visited[linear]) {
                visited[linear] = true;
                *top++ = linear;
            }
        }
    }

    free(stack);
    free(visited);

    return result;
}
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the review. __debugbreak() does actually kill the program if not running under a debugger. \$\endgroup\$ Commented May 9, 2021 at 7:32
  • \$\begingroup\$ Re. comments... yeah, I tend to find C fiddly enough that I want to summarize in English what each part of the code does. But maybe it's obvious to someone who's competent at C. :D \$\endgroup\$ Commented May 9, 2021 at 7:45
  • 1
    \$\begingroup\$ @user673679 I think it's OK to add a comment describing what a larger section of code does, but comments that just describe what a one-liner does, like c = stack[--stack_size]; /* pop */, are often redundant. \$\endgroup\$ Commented May 9, 2021 at 7:49
  • 1
    \$\begingroup\$ @user673679 Still kills it in the wrong way, as it implies a detected programming-error, instead of a somewhat expected lack of resources. \$\endgroup\$ Commented May 9, 2021 at 15:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.