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 = "https://codereview.stackexchange.com/#";
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: %sn", 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. 🙂
