diff options
Diffstat (limited to 'libtracebitmap_trace.c')
-rw-r--r-- | libtracebitmap_trace.c | 192 |
1 files changed, 192 insertions, 0 deletions
diff --git a/libtracebitmap_trace.c b/libtracebitmap_trace.c new file mode 100644 index 0000000..090c55a --- /dev/null +++ b/libtracebitmap_trace.c @@ -0,0 +1,192 @@ +/* See LICENSE file for copyright and license details. */ +#include "libtracebitmap.h" + +#include <stdlib.h> +#include <unistd.h> + + +#define CLEARED 0 +#define SET 1 +#define NEGATIVE 2 +#define STATUS_MASK 0x03 + +#define TOP 0x10 +#define RIGHT 0x20 +#define BOTTOM 0x40 +#define LEFT 0x80 +#define EDGE_MASK 0xF0 + +#define INDEX(Y, X) ((size_t)(Y) * bitmap->width + (size_t)(X)) + + +static uint8_t +read_pixel(struct libtracebitmap_bitmap *bitmap, ssize_t y, ssize_t x) +{ + if (y < 0 || x < 0 || (size_t)y >= bitmap->height || (size_t)x >= bitmap->width) + return 0; + return bitmap->image[INDEX(y, x)]; +} + + +static int +test_pixel(struct libtracebitmap_bitmap *bitmap, ssize_t y, ssize_t x, uint8_t status) +{ + return (read_pixel(bitmap, y, x) & STATUS_MASK) == status; +} + + +static int +find_component(size_t *yp, size_t *xp, int *negativep, struct libtracebitmap_bitmap *bitmap) +{ + size_t y, x; + uint8_t status; + for (y = 0; y < bitmap->height; y++) { + for (x = 0; x < bitmap->width; x++) { + status = (bitmap->image[INDEX(y, x)] & STATUS_MASK); + if (status != CLEARED) { + *yp = y; + *xp = x; + *negativep = (status == NEGATIVE); + return 1; + } + } + } + return 0; +} + + +static int +trace_edges(struct libtracebitmap_bitmap *bitmap, size_t tl_y, size_t tl_x, int negative, + int (*new_stop)(size_t y, size_t x, void *user_data), void *user_data) +{ + uint8_t c = (negative ? NEGATIVE : SET); + uint8_t edge = TOP; + ssize_t y = (ssize_t)tl_y; + ssize_t x = (ssize_t)tl_x; + int r; + if ((r = new_stop((size_t)y, (size_t)x, user_data))) + return r; + do { + bitmap->image[INDEX(y, x)] |= edge; + switch (edge) { + case TOP: + if (test_pixel(bitmap, y - 1, x + 1, c)) { + if ((r = new_stop((size_t)y, (size_t)x + 1, user_data))) + return r; + x += 1; + y -= 1; + edge = LEFT; + } else if (test_pixel(bitmap, y, x + 1, c)) { + x += 1; + } else { + if ((r = new_stop((size_t)y, (size_t)x + 1, user_data))) + return r; + edge = RIGHT; + } + break; + case RIGHT: + if (test_pixel(bitmap, y + 1, x + 1, c)) { + if ((r = new_stop((size_t)y + 1, (size_t)x + 1, user_data))) + return r; + x += 1; + y += 1; + edge = TOP; + } else if (test_pixel(bitmap, y + 1, x, c)) { + y += 1; + } else { + if ((r = new_stop((size_t)y + 1, (size_t)x + 1, user_data))) + return r; + edge = BOTTOM; + } + break; + case BOTTOM: + if (test_pixel(bitmap, y + 1, x - 1, c)) { + if ((r = new_stop((size_t)y + 1, (size_t)x, user_data))) + return r; + x -= 1; + y += 1; + edge = RIGHT; + } else if (test_pixel(bitmap, y, x - 1, c)) { + x -= 1; + } else { + if ((r = new_stop((size_t)y + 1, (size_t)x, user_data))) + return r; + edge = LEFT; + } + break; + case LEFT: + if (test_pixel(bitmap, y - 1, x - 1, c)) { + if ((r = new_stop((size_t)y, (size_t)x, user_data))) + return r; + x -= 1; + y -= 1; + edge = BOTTOM; + } else if (test_pixel(bitmap, y - 1, x, c)) { + y -= 1; + } else { + if ((r = new_stop((size_t)y, (size_t)x, user_data))) + return r; + edge = TOP; + } + break; + default: + abort(); + } + } while (y != (ssize_t)tl_y || x != (ssize_t)tl_x || edge != TOP); + return 0; +} + + +static void +erase_traced_component(struct libtracebitmap_bitmap *bitmap, int negative) +{ + size_t y, x; + int inside; + uint8_t c; + for (y = 0; y < bitmap->height; y++) { + inside = 0; + for (x = 0; x < bitmap->width; x++) { + c = bitmap->image[INDEX(y, x)]; + bitmap->image[INDEX(y, x)] &= (uint8_t)~EDGE_MASK; + if (c & LEFT) + inside = 1; + if (inside) { + bitmap->image[INDEX(y, x)] &= (uint8_t)~STATUS_MASK; + if ((c & STATUS_MASK) != CLEARED) + bitmap->image[INDEX(y, x)] |= CLEARED; + else if (negative) + bitmap->image[INDEX(y, x)] |= SET; + else + bitmap->image[INDEX(y, x)] |= NEGATIVE; + } + if (c & RIGHT) + inside = 0; + } + } +} + + +int +libtracebitmap_trace( + struct libtracebitmap_bitmap *bitmap, + int (*new_component)(int negative, void *user_data), + int (*new_stop)(size_t y, size_t x, void *user_data), + int (*component_finished)(void *user_data), + void *user_data) +{ + size_t y, x; + int negative; + int r; + for (;;) { + if (!find_component(&y, &x, &negative, bitmap)) + return 0; + if ((r = new_component(negative, user_data))) + return r; + if ((r = trace_edges(bitmap, y, x, negative, new_stop, user_data))) + return r; + if ((r = component_finished(user_data))) + return r; + erase_traced_component(bitmap, negative); + } + return 0; +} |