summaryrefslogtreecommitdiffstats
path: root/src/3rdparty/autotrace/pxl-outline.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/3rdparty/autotrace/pxl-outline.c887
1 files changed, 887 insertions, 0 deletions
diff --git a/src/3rdparty/autotrace/pxl-outline.c b/src/3rdparty/autotrace/pxl-outline.c
new file mode 100644
index 0000000..6bc5a56
--- /dev/null
+++ b/src/3rdparty/autotrace/pxl-outline.c
@@ -0,0 +1,887 @@
+/* pxl-outline.c: find the outlines of a bitmap image; each outline is made up of one or more pixels;
+ and each pixel participates via one or more edges. */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif /* Def: HAVE_CONFIG_H */
+
+#include "logreport.h"
+#include "types.h"
+#include "bitmap.h"
+#include "color.h"
+#include "bitmap.h"
+#include "xstd.h"
+#include "pxl-outline.h"
+#include <assert.h>
+
+/* We consider each pixel to consist of four edges, and we travel along
+ edges, instead of through pixel centers. This is necessary for those
+ unfortunate times when a single pixel is on both an inside and an
+ outside outline.
+
+ The numbers chosen here are not arbitrary; the code that figures out
+ which edge to move to depends on particular values. See the
+ `TRY_PIXEL' macro in `edge.c'. To emphasize this, I've written in the
+ numbers we need for each edge value. */
+
+typedef enum {
+ TOP = 1, LEFT = 2, BOTTOM = 3, RIGHT = 0, NO_EDGE = 4
+} edge_type;
+
+/* This choice is also not arbitrary: starting at the top edge makes the
+ code find outside outlines before inside ones, which is certainly
+ what we want. */
+#define START_EDGE top
+
+typedef enum {
+ NORTH = 0, NORTHWEST = 1, WEST = 2, SOUTHWEST = 3, SOUTH = 4,
+ SOUTHEAST = 5, EAST = 6, NORTHEAST = 7
+} direction_type;
+
+#define NUM_EDGES NO_EDGE
+
+#define COMPUTE_DELTA(axis, dir) \
+ ((dir) % 2 != 0 \
+ ? COMPUTE_##axis##_DELTA ((dir) - 1) \
+ + COMPUTE_##axis##_DELTA (((dir) + 1) % 8) \
+ : COMPUTE_##axis##_DELTA (dir) \
+ )
+
+#define COMPUTE_ROW_DELTA(dir) \
+ ((dir) == NORTH ? -1 : (dir) == SOUTH ? +1 : 0)
+
+#define COMPUTE_COL_DELTA(dir) \
+ ((dir) == WEST ? -1 : (dir) == EAST ? +1 : 0)
+
+static pixel_outline_type find_one_outline(at_bitmap *, edge_type, unsigned short, unsigned short, at_bitmap *, gboolean, gboolean, at_exception_type *);
+static pixel_outline_type find_one_centerline(at_bitmap *, direction_type, unsigned short, unsigned short, at_bitmap *);
+static void append_pixel_outline(pixel_outline_list_type *, pixel_outline_type);
+static pixel_outline_type new_pixel_outline(void);
+static void free_pixel_outline(pixel_outline_type *);
+static void concat_pixel_outline(pixel_outline_type *, const pixel_outline_type *);
+static void append_outline_pixel(pixel_outline_type *, at_coord);
+static gboolean is_marked_edge(edge_type, unsigned short, unsigned short, at_bitmap *);
+static gboolean is_outline_edge(edge_type, at_bitmap *, unsigned short, unsigned short, at_color, at_exception_type *);
+static gboolean is_unmarked_outline_edge(unsigned short, unsigned short, edge_type, at_bitmap *, at_bitmap *, at_color, at_exception_type *);
+
+static void mark_edge(edge_type e, unsigned short, unsigned short, at_bitmap *);
+/* static edge_type opposite_edge(edge_type); */
+
+static gboolean is_marked_dir(unsigned short, unsigned short, direction_type, at_bitmap *);
+static gboolean is_other_dir_marked(unsigned short, unsigned short, direction_type, at_bitmap *);
+static void mark_dir(unsigned short, unsigned short, direction_type, at_bitmap *);
+static gboolean next_unmarked_pixel(unsigned short *, unsigned short *, direction_type *, at_bitmap *, at_bitmap *);
+
+gboolean is_valid_dir(unsigned short, unsigned short, direction_type, at_bitmap *, at_bitmap *);
+
+static at_coord next_point(at_bitmap *, edge_type *, unsigned short *, unsigned short *, at_color, gboolean, at_bitmap *, at_exception_type *);
+static unsigned num_neighbors(unsigned short, unsigned short, at_bitmap *);
+
+#define CHECK_FATAL() if (at_exception_got_fatal(exp)) goto cleanup;
+
+/* We go through a bitmap TOP to BOTTOM, LEFT to RIGHT, looking for each pixel with an unmarked edge
+ that we consider a starting point of an outline. */
+
+pixel_outline_list_type find_outline_pixels(at_bitmap * bitmap, at_color * bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp)
+{
+ pixel_outline_list_type outline_list;
+ unsigned short row, col;
+ at_bitmap *marked = at_bitmap_new(AT_BITMAP_WIDTH(bitmap), AT_BITMAP_HEIGHT(bitmap), 1);
+ unsigned int max_progress = AT_BITMAP_HEIGHT(bitmap) * AT_BITMAP_WIDTH(bitmap);
+
+ O_LIST_LENGTH(outline_list) = 0;
+ outline_list.data = NULL;
+
+ for (row = 0; row < AT_BITMAP_HEIGHT(bitmap); row++) {
+ for (col = 0; col < AT_BITMAP_WIDTH(bitmap); col++) {
+ edge_type edge;
+ at_color color;
+ gboolean is_background;
+
+ if (notify_progress)
+ notify_progress((gfloat) (row * AT_BITMAP_WIDTH(bitmap) + col) / ((gfloat) max_progress * (gfloat) 3.0), progress_data);
+
+ /* A valid edge can be TOP for an outside outline.
+ Outside outlines are traced counterclockwise */
+ at_bitmap_get_color(bitmap, row, col, &color);
+ if (!(is_background = (gboolean) (bg_color && at_color_equal(&color, bg_color)))
+ && is_unmarked_outline_edge(row, col, edge = TOP, bitmap, marked, color, exp)) {
+ pixel_outline_type outline;
+
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+
+ LOG("#%u: (counterclockwise)", O_LIST_LENGTH(outline_list));
+
+ outline = find_one_outline(bitmap, edge, row, col, marked, FALSE, FALSE, exp);
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+
+ O_CLOCKWISE(outline) = FALSE;
+ append_pixel_outline(&outline_list, outline);
+
+ LOG(" [%u].\n", O_LENGTH(outline));
+ } else
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+
+ /* A valid edge can be BOTTOM for an inside outline.
+ Inside outlines are traced clockwise */
+ if (row != 0) {
+ at_bitmap_get_color(bitmap, row - 1, col, &color);
+ if (!(bg_color && at_color_equal(&color, bg_color))
+ && is_unmarked_outline_edge(row - 1, col, edge = BOTTOM, bitmap, marked, color, exp)) {
+ pixel_outline_type outline;
+
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+
+ /* This lines are for debugging only: */
+ if (is_background) {
+ LOG("#%u: (clockwise)", O_LIST_LENGTH(outline_list));
+
+ outline = find_one_outline(bitmap, edge, row - 1, col, marked, TRUE, FALSE, exp);
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+
+ O_CLOCKWISE(outline) = TRUE;
+ append_pixel_outline(&outline_list, outline);
+
+ LOG(" [%u].\n", O_LENGTH(outline));
+ } else {
+ outline = find_one_outline(bitmap, edge, row - 1, col, marked, TRUE, TRUE, exp);
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+ }
+ } else
+ CHECK_FATAL(); /* FREE(DONE) outline_list */
+ }
+ if (test_cancel && test_cancel(testcancel_data)) {
+ free_pixel_outline_list(&outline_list);
+ goto cleanup;
+ }
+ }
+ }
+cleanup:
+ at_bitmap_free(marked);
+ if (at_exception_got_fatal(exp))
+ free_pixel_outline_list(&outline_list);
+ return outline_list;
+}
+
+/* We calculate one single outline here. We pass the position of the starting pixel and the
+ starting edge. All edges we track along will be marked and the outline pixels are appended
+ to the coordinate list. */
+
+static pixel_outline_type find_one_outline(at_bitmap * bitmap, edge_type original_edge, unsigned short original_row, unsigned short original_col, at_bitmap * marked, gboolean clockwise, gboolean ignore, at_exception_type * exp)
+{
+ pixel_outline_type outline;
+ unsigned short row = original_row, col = original_col;
+ edge_type edge = original_edge;
+ at_coord pos;
+
+ pos.x = col + ((edge == RIGHT) || (edge == BOTTOM) ? 1 : 0);
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1 + ((edge == TOP) || (edge == RIGHT) ? 1 : 0);
+
+ if (!ignore)
+ outline = new_pixel_outline();
+ at_bitmap_get_color(bitmap, row, col, &outline.color);
+
+ do {
+ /* Put this edge into the output list */
+ if (!ignore) {
+ LOG(" (%d,%d)", pos.x, pos.y);
+ append_outline_pixel(&outline, pos);
+ }
+
+ mark_edge(edge, row, col, marked);
+ pos = next_point(bitmap, &edge, &row, &col, outline.color, clockwise, marked, exp);
+ CHECK_FATAL();
+ }
+ while (edge != NO_EDGE);
+
+cleanup:
+ if (at_exception_got_fatal(exp))
+ free_pixel_outline(&outline);
+ return outline;
+}
+
+gboolean is_valid_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * bitmap, at_bitmap * marked)
+{
+
+ at_color c;
+
+ if ((COMPUTE_DELTA(ROW, dir) + row < 0) || (COMPUTE_DELTA(COL, dir) + col < 0))
+ return FALSE; // Must not call at_bitmap_get_color() with negative row or col.
+
+ at_bitmap_get_color(bitmap, COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, &c);
+ return ((gboolean) (!is_marked_dir(row, col, dir, marked)
+ && COMPUTE_DELTA(ROW, dir) + row > 0 && COMPUTE_DELTA(COL, dir) + col > 0 && AT_BITMAP_VALID_PIXEL(bitmap, COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col)
+ && at_bitmap_equal_color(bitmap, row, col, &c)));
+}
+
+pixel_outline_list_type find_centerline_pixels(at_bitmap * bitmap, at_color bg_color, at_progress_func notify_progress, gpointer progress_data, at_testcancel_func test_cancel, gpointer testcancel_data, at_exception_type * exp)
+{
+ pixel_outline_list_type outline_list;
+ signed short row, col;
+ at_bitmap *marked = at_bitmap_new(AT_BITMAP_WIDTH(bitmap), AT_BITMAP_HEIGHT(bitmap), 1);
+ unsigned int max_progress = AT_BITMAP_HEIGHT(bitmap) * AT_BITMAP_WIDTH(bitmap);
+
+ O_LIST_LENGTH(outline_list) = 0;
+ outline_list.data = NULL;
+
+ for (row = 0; row < AT_BITMAP_HEIGHT(bitmap); row++) {
+ for (col = 0; col < AT_BITMAP_WIDTH(bitmap);) {
+ direction_type dir = EAST;
+ pixel_outline_type outline;
+ gboolean clockwise = FALSE;
+
+ if (notify_progress)
+ notify_progress((gfloat) (row * AT_BITMAP_WIDTH(bitmap) + col) / ((gfloat) max_progress * (gfloat) 3.0), progress_data);
+
+ if (at_bitmap_equal_color(bitmap, row, col, &bg_color)) {
+ col++;
+ continue;
+ }
+
+ if (!is_valid_dir(row, col, dir, bitmap, marked)
+ || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked)
+ && num_neighbors(row, col, bitmap) > 2)
+ || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked)
+ && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) {
+ dir = SOUTHEAST;
+ if (!is_valid_dir(row, col, dir, bitmap, marked)
+ || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked)
+ && num_neighbors(row, col, bitmap) > 2)
+ || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked)
+ && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) {
+ dir = SOUTH;
+ if (!is_valid_dir(row, col, dir, bitmap, marked)
+ || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked)
+ && num_neighbors(row, col, bitmap) > 2)
+ || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked)
+ && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) {
+ dir = SOUTHWEST;
+ if (!is_valid_dir(row, col, dir, bitmap, marked)
+ || (!is_valid_dir(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, dir, bitmap, marked)
+ && num_neighbors(row, col, bitmap) > 2)
+ || num_neighbors(row, col, bitmap) > 4 || num_neighbors(COMPUTE_DELTA(ROW, dir) + row, COMPUTE_DELTA(COL, dir) + col, bitmap) > 4 || (is_other_dir_marked(row, col, dir, marked)
+ && is_other_dir_marked(row + COMPUTE_DELTA(ROW, dir), col + COMPUTE_DELTA(COL, dir), dir, marked))) {
+ col++;
+ continue;
+ }
+ }
+ }
+ }
+
+ LOG("#%u: (%sclockwise) ", O_LIST_LENGTH(outline_list), clockwise ? "" : "counter");
+
+ outline = find_one_centerline(bitmap, dir, row, col, marked);
+
+ /* If the outline is open (i.e., we didn't return to the
+ starting pixel), search from the starting pixel in the
+ opposite direction and concatenate the two outlines. */
+
+ if (outline.open) {
+ pixel_outline_type partial_outline;
+ gboolean okay = FALSE;
+
+ if (dir == EAST) {
+ dir = SOUTH;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTHWEST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTHEAST;
+ okay = is_valid_dir(row, col, dir, bitmap, marked);
+ }
+ }
+ } else if (dir == SOUTHEAST) {
+ dir = SOUTHWEST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = EAST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTH;
+ okay = is_valid_dir(row, col, dir, bitmap, marked);
+ }
+ }
+ } else if (dir == SOUTH) {
+ dir = EAST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTHEAST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTHWEST;
+ okay = is_valid_dir(row, col, dir, bitmap, marked);
+ }
+ }
+ } else if (dir == SOUTHWEST) {
+ dir = SOUTHEAST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = EAST;
+ if (!(okay = is_valid_dir(row, col, dir, bitmap, marked))) {
+ dir = SOUTH;
+ okay = is_valid_dir(row, col, dir, bitmap, marked);
+ }
+ }
+ }
+ if (okay) {
+ partial_outline = find_one_centerline(bitmap, dir, row, col, marked);
+ concat_pixel_outline(&outline, &partial_outline);
+ if (partial_outline.data)
+ free(partial_outline.data);
+ } else
+ col++;
+ }
+
+ /* Outside outlines will start at a top edge, and move
+ counterclockwise, and inside outlines will start at a
+ bottom edge, and move clockwise. This happens because of
+ the order in which we look at the edges. */
+ O_CLOCKWISE(outline) = clockwise;
+ if (O_LENGTH(outline) > 1)
+ append_pixel_outline(&outline_list, outline);
+ LOG("(%s)", (outline.open ? " open" : " closed"));
+ LOG(" [%u].\n", O_LENGTH(outline));
+ if (O_LENGTH(outline) == 1)
+ free_pixel_outline(&outline);
+ }
+ }
+ if (test_cancel && test_cancel(testcancel_data)) {
+ if (O_LIST_LENGTH(outline_list) != 0)
+ free_pixel_outline_list(&outline_list);
+ goto cleanup;
+ }
+cleanup:
+ at_bitmap_free(marked);
+ return outline_list;
+}
+
+static pixel_outline_type find_one_centerline(at_bitmap * bitmap, direction_type search_dir, unsigned short original_row, unsigned short original_col, at_bitmap * marked)
+{
+ pixel_outline_type outline = new_pixel_outline();
+ direction_type original_dir = search_dir;
+ unsigned short row = original_row, col = original_col;
+ unsigned short prev_row, prev_col;
+ at_coord pos;
+
+ outline.open = FALSE;
+ at_bitmap_get_color(bitmap, row, col, &outline.color);
+
+ /* Add the starting pixel to the output list, changing from bitmap
+ to Cartesian coordinates and specifying the left edge so that
+ the coordinates won't be adjusted. */
+ pos.x = col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1;
+ LOG(" (%d,%d)", pos.x, pos.y);
+ append_outline_pixel(&outline, pos);
+
+ for (;;) {
+ prev_row = row;
+ prev_col = col;
+
+ /* If there is no adjacent, unmarked pixel, we can't proceed
+ any further, so return an open outline. */
+ if (!next_unmarked_pixel(&row, &col, &search_dir, bitmap, marked)) {
+ outline.open = TRUE;
+ break;
+ }
+
+ /* If we've moved to a new pixel, mark all edges of the previous
+ pixel so that it won't be revisited. */
+ if (!(prev_row == original_row && prev_col == original_col))
+ mark_dir(prev_row, prev_col, search_dir, marked);
+ mark_dir(row, col, (direction_type) ((search_dir + 4) % 8), marked);
+
+ /* If we've returned to the starting pixel, we're done. */
+ if (row == original_row && col == original_col)
+ break;
+
+ /* Add the new pixel to the output list. */
+ pos.x = col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - row - 1;
+ LOG(" (%d,%d)", pos.x, pos.y);
+ append_outline_pixel(&outline, pos);
+ }
+ mark_dir(original_row, original_col, original_dir, marked);
+ return outline;
+}
+
+/* Add an outline to an outline list. */
+
+static void append_pixel_outline(pixel_outline_list_type * outline_list, pixel_outline_type outline)
+{
+ O_LIST_LENGTH(*outline_list)++;
+ XREALLOC(outline_list->data, outline_list->length * sizeof(pixel_outline_type));
+ O_LIST_OUTLINE(*outline_list, O_LIST_LENGTH(*outline_list) - 1) = outline;
+}
+
+/* Free the list of outline lists. */
+
+void free_pixel_outline_list(pixel_outline_list_type * outline_list)
+{
+ unsigned this_outline;
+
+ for (this_outline = 0; this_outline < outline_list->length; this_outline++) {
+ pixel_outline_type o = outline_list->data[this_outline];
+ free_pixel_outline(&o);
+ }
+ free(outline_list->data);
+ outline_list->data = NULL;
+ outline_list->length = 0;
+}
+
+/* Return an empty list of pixels. */
+
+static pixel_outline_type new_pixel_outline(void)
+{
+ pixel_outline_type pixel_outline;
+
+ O_LENGTH(pixel_outline) = 0;
+ pixel_outline.data = NULL;
+ pixel_outline.open = FALSE;
+
+ return pixel_outline;
+}
+
+static void free_pixel_outline(pixel_outline_type * outline)
+{
+ free(outline->data);
+ outline->data = NULL;
+ outline->length = 0;
+}
+
+/* Concatenate two pixel lists. The two lists are assumed to have the
+ same starting pixel and to proceed in opposite directions therefrom. */
+
+static void concat_pixel_outline(pixel_outline_type * o1, const pixel_outline_type * o2)
+{
+ int src, dst;
+ unsigned o1_length, o2_length;
+ if (!o1 || !o2 || O_LENGTH(*o2) <= 1)
+ return;
+
+ o1_length = O_LENGTH(*o1);
+ o2_length = O_LENGTH(*o2);
+ O_LENGTH(*o1) += o2_length - 1;
+ /* Resize o1 to the sum of the lengths of o1 and o2 minus one (because
+ the two lists are assumed to share the same starting pixel). */
+ XREALLOC(o1->data, O_LENGTH(*o1) * sizeof(at_coord));
+ /* Shift the contents of o1 to the end of the new array to make room
+ to prepend o2. */
+ for (src = o1_length - 1, dst = O_LENGTH(*o1) - 1; src >= 0; src--, dst--)
+ O_COORDINATE(*o1, dst) = O_COORDINATE(*o1, src);
+ /* Prepend the contents of o2 (in reverse order) to o1. */
+ for (src = o2_length - 1, dst = 0; src > 0; src--, dst++)
+ O_COORDINATE(*o1, dst) = O_COORDINATE(*o2, src);
+}
+
+/* Add a point to the pixel list. */
+
+static void append_outline_pixel(pixel_outline_type * o, at_coord c)
+{
+ O_LENGTH(*o)++;
+ XREALLOC(o->data, O_LENGTH(*o) * sizeof(at_coord));
+ O_COORDINATE(*o, O_LENGTH(*o) - 1) = c;
+}
+
+/* Is this really an edge and is it still unmarked? */
+
+static gboolean is_unmarked_outline_edge(unsigned short row, unsigned short col, edge_type edge, at_bitmap * bitmap, at_bitmap * marked, at_color color, at_exception_type * exp)
+{
+ return (gboolean) (!is_marked_edge(edge, row, col, marked)
+ && is_outline_edge(edge, bitmap, row, col, color, exp));
+}
+
+/* We check to see if the edge of the pixel at position ROW and COL
+ is an outline edge */
+
+static gboolean is_outline_edge(edge_type edge, at_bitmap * bitmap, unsigned short row, unsigned short col, at_color color, at_exception_type * exp)
+{
+ /* If this pixel isn't of the same color, it's not part of the outline. */
+ if (!at_bitmap_equal_color(bitmap, row, col, &color))
+ return FALSE;
+
+ switch (edge) {
+ case LEFT:
+ return (gboolean) (col == 0 || !at_bitmap_equal_color(bitmap, row, col - 1, &color));
+ case TOP:
+ return (gboolean) (row == 0 || !at_bitmap_equal_color(bitmap, row - 1, col, &color));
+
+ case RIGHT:
+ return (gboolean) (col == AT_BITMAP_WIDTH(bitmap) - 1 || !at_bitmap_equal_color(bitmap, row, col + 1, &color));
+
+ case BOTTOM:
+ return (gboolean) (row == AT_BITMAP_HEIGHT(bitmap) - 1 || !at_bitmap_equal_color(bitmap, row + 1, col, &color));
+
+ case NO_EDGE:
+ g_assert_not_reached();
+ default:
+ g_assert_not_reached();
+ }
+ return FALSE; /* NOT REACHED */
+}
+
+/* If EDGE is not already marked, we mark it; otherwise, it's a fatal error.
+ The position ROW and COL should be inside the bitmap MARKED. EDGE can be
+ NO_EDGE. */
+
+static void mark_edge(edge_type edge, unsigned short row, unsigned short col, at_bitmap * marked)
+{
+ *AT_BITMAP_PIXEL(marked, row, col) |= 1 << edge;
+}
+
+/* Mark the direction of the pixel ROW/COL in MARKED. */
+
+static void mark_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked)
+{
+ *AT_BITMAP_PIXEL(marked, row, col) |= 1 << dir;
+}
+
+/* Test if the direction of pixel at ROW/COL in MARKED is marked. */
+
+static gboolean is_marked_dir(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked)
+{
+ return (gboolean) ((*AT_BITMAP_PIXEL(marked, row, col) & 1 << dir) != 0);
+}
+
+static gboolean is_other_dir_marked(unsigned short row, unsigned short col, direction_type dir, at_bitmap * marked)
+{
+ return (gboolean) ((*AT_BITMAP_PIXEL(marked, row, col) & (255 - (1 << dir) - (1 << ((dir + 4) % 8)))) != 0);
+}
+
+static gboolean next_unmarked_pixel(unsigned short *row, unsigned short *col, direction_type * dir, at_bitmap * bitmap, at_bitmap * marked)
+{
+ unsigned short orig_row = *row, orig_col = *col;
+ direction_type orig_dir = *dir, test_dir = *dir;
+
+ do {
+ if (is_valid_dir(orig_row, orig_col, test_dir, bitmap, marked)) {
+ *row = orig_row + COMPUTE_DELTA(ROW, test_dir);
+ *col = orig_col + COMPUTE_DELTA(COL, test_dir);
+ *dir = test_dir;
+ break;
+ }
+
+ if (orig_dir == test_dir)
+ test_dir = (direction_type) ((orig_dir + 2) % 8);
+ else if ((orig_dir + 2) % 8 == test_dir)
+ test_dir = (direction_type) ((orig_dir + 6) % 8);
+ else if ((orig_dir + 6) % 8 == test_dir)
+ test_dir = (direction_type) ((orig_dir + 1) % 8);
+ else if ((orig_dir + 1) % 8 == test_dir)
+ test_dir = (direction_type) ((orig_dir + 7) % 8);
+ else if ((orig_dir + 7) % 8 == test_dir)
+ test_dir = (direction_type) ((orig_dir + 3) % 8);
+ else if ((orig_dir + 3) % 8 == test_dir)
+ test_dir = (direction_type) ((orig_dir + 5) % 8);
+ else if ((orig_dir + 5) % 8 == test_dir)
+ break;
+ }
+ while (1);
+ if ((*row != orig_row || *col != orig_col) && (!(is_other_dir_marked(orig_row, orig_col, test_dir, marked)
+ && is_other_dir_marked(orig_row + COMPUTE_DELTA(ROW, test_dir), orig_col + COMPUTE_DELTA(COL, test_dir), test_dir, marked))))
+ return TRUE;
+ else
+ return FALSE;
+}
+
+/* Return the number of pixels adjacent to pixel ROW/COL that are black. */
+
+static unsigned num_neighbors(unsigned short row, unsigned short col, at_bitmap * bitmap)
+{
+ unsigned dir, count = 0;
+ at_color color;
+
+ at_bitmap_get_color(bitmap, row, col, &color);
+ for (dir = NORTH; dir <= NORTHEAST; dir++) {
+ int delta_r = COMPUTE_DELTA(ROW, dir);
+ int delta_c = COMPUTE_DELTA(COL, dir);
+ unsigned int test_row = row + delta_r;
+ unsigned int test_col = col + delta_c;
+ if (AT_BITMAP_VALID_PIXEL(bitmap, test_row, test_col)
+ && at_bitmap_equal_color(bitmap, test_row, test_col, &color))
+ ++count;
+ }
+ return count;
+}
+
+/* Test if the edge EDGE at ROW/COL in MARKED is marked. */
+
+static gboolean is_marked_edge(edge_type edge, unsigned short row, unsigned short col, at_bitmap * marked)
+{
+ return (gboolean) (edge == NO_EDGE ? FALSE : (*AT_BITMAP_PIXEL(marked, row, col) & (1 << edge)) != 0);
+}
+
+static at_coord next_point(at_bitmap * bitmap, edge_type * edge, unsigned short *row, unsigned short *col, at_color color, gboolean clockwise, at_bitmap * marked, at_exception_type * exp)
+{
+ at_coord pos = { 0, 0 };
+
+ if (!clockwise)
+ switch (*edge) {
+ case TOP:
+ /* WEST */
+ if ((*col >= 1 && !is_marked_edge(TOP, *row, *col - 1, marked)
+ && is_outline_edge(TOP, bitmap, *row, *col - 1, color, exp))) {
+ /**edge = TOP;*/
+ (*col)--;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* NORTHWEST */
+ if ((*col >= 1 && *row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col - 1, marked)
+ && is_outline_edge(RIGHT, bitmap, *row - 1, *col - 1, color, exp)) && !(is_marked_edge(LEFT, *row - 1, *col, marked) && is_marked_edge(TOP, *row, *col - 1, marked)) && !(is_marked_edge(BOTTOM, *row - 1, *col, marked) && is_marked_edge(RIGHT, *row, *col - 1, marked))) {
+ *edge = RIGHT;
+ (*col)--;
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ if ((!is_marked_edge(LEFT, *row, *col, marked)
+ && is_outline_edge(LEFT, bitmap, *row, *col, color, exp))) {
+ *edge = LEFT;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case RIGHT:
+ /* NORTH */
+ if ((*row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col, marked)
+ && is_outline_edge(RIGHT, bitmap, *row - 1, *col, color, exp))) {
+ /**edge = RIGHT;*/
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* NORTHEAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row >= 1 && !is_marked_edge(BOTTOM, *row - 1, *col + 1, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row - 1, *col + 1, color, exp)) && !(is_marked_edge(LEFT, *row, *col + 1, marked) && is_marked_edge(BOTTOM, *row - 1, *col, marked)) && !(is_marked_edge(TOP, *row, *col + 1, marked) && is_marked_edge(RIGHT, *row - 1, *col, marked))) {
+ *edge = BOTTOM;
+ (*col)++;
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ if ((!is_marked_edge(TOP, *row, *col, marked)
+ && is_outline_edge(TOP, bitmap, *row, *col, color, exp))) {
+ *edge = TOP;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case BOTTOM:
+ /* EAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked)
+ && !is_marked_edge(BOTTOM, *row, *col + 1, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row, *col + 1, color, exp))) {
+ /**edge = BOTTOM;*/
+ (*col)++;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* SOUTHEAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(LEFT, *row + 1, *col + 1, marked)
+ && is_outline_edge(LEFT, bitmap, *row + 1, *col + 1, color, exp)) && !(is_marked_edge(TOP, *row + 1, *col, marked) && is_marked_edge(LEFT, *row, *col + 1, marked)) && !(is_marked_edge(RIGHT, *row + 1, *col, marked) && is_marked_edge(BOTTOM, *row, *col + 1, marked))) {
+ *edge = LEFT;
+ (*col)++;
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ if ((!is_marked_edge(RIGHT, *row, *col, marked)
+ && is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) {
+ *edge = RIGHT;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case LEFT:
+ /* SOUTH */
+ if ((*row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(LEFT, *row + 1, *col, marked)
+ && is_outline_edge(LEFT, bitmap, *row + 1, *col, color, exp))) {
+ /**edge = LEFT;*/
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* SOUTHWEST */
+ if ((*col >= 1 && *row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(TOP, *row + 1, *col - 1, marked)
+ && is_outline_edge(TOP, bitmap, *row + 1, *col - 1, color, exp)) && !(is_marked_edge(RIGHT, *row, *col - 1, marked) && is_marked_edge(TOP, *row + 1, *col, marked)) && !(is_marked_edge(BOTTOM, *row, *col - 1, marked) && is_marked_edge(LEFT, *row + 1, *col, marked))) {
+ *edge = TOP;
+ (*col)--;
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ if ((!is_marked_edge(BOTTOM, *row, *col, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) {
+ *edge = BOTTOM;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ case NO_EDGE:
+ default:
+ *edge = NO_EDGE;
+ break;
+ } else
+ switch (*edge) {
+ case TOP:
+ if ((!is_marked_edge(LEFT, *row, *col, marked)
+ && is_outline_edge(LEFT, bitmap, *row, *col, color, exp))) {
+ *edge = LEFT;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* WEST */
+ if ((*col >= 1 && !is_marked_edge(TOP, *row, *col - 1, marked)
+ && is_outline_edge(TOP, bitmap, *row, *col - 1, color, exp))) {
+ /**edge = TOP;*/
+ (*col)--;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* NORTHWEST */
+ if ((*col >= 1 && *row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col - 1, marked)
+ && is_outline_edge(RIGHT, bitmap, *row - 1, *col - 1, color, exp))) {
+ *edge = RIGHT;
+ (*col)--;
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case RIGHT:
+ if ((!is_marked_edge(TOP, *row, *col, marked)
+ && is_outline_edge(TOP, bitmap, *row, *col, color, exp))) {
+ *edge = TOP;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* NORTH */
+ if ((*row >= 1 && !is_marked_edge(RIGHT, *row - 1, *col, marked)
+ && is_outline_edge(RIGHT, bitmap, *row - 1, *col, color, exp))) {
+ /**edge = RIGHT;*/
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* NORTHEAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row >= 1 && !is_marked_edge(BOTTOM, *row - 1, *col + 1, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row - 1, *col + 1, color, exp))) {
+ *edge = BOTTOM;
+ (*col)++;
+ (*row)--;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case BOTTOM:
+ if ((!is_marked_edge(RIGHT, *row, *col, marked)
+ && is_outline_edge(RIGHT, bitmap, *row, *col, color, exp))) {
+ *edge = RIGHT;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ /* EAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked)
+ && !is_marked_edge(BOTTOM, *row, *col + 1, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row, *col + 1, color, exp))) {
+ /**edge = BOTTOM;*/
+ (*col)++;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* SOUTHEAST */
+ if ((*col + 1 < AT_BITMAP_WIDTH(marked) && *row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(LEFT, *row + 1, *col + 1, marked)
+ && is_outline_edge(LEFT, bitmap, *row + 1, *col + 1, color, exp))) {
+ *edge = LEFT;
+ (*col)++;
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ *edge = NO_EDGE;
+ break;
+ case LEFT:
+ if ((!is_marked_edge(BOTTOM, *row, *col, marked)
+ && is_outline_edge(BOTTOM, bitmap, *row, *col, color, exp))) {
+ *edge = BOTTOM;
+ pos.x = *col + 1;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* SOUTH */
+ if ((*row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(LEFT, *row + 1, *col, marked)
+ && is_outline_edge(LEFT, bitmap, *row + 1, *col, color, exp))) {
+ /**edge = LEFT;*/
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row - 1;
+ break;
+ }
+ CHECK_FATAL();
+ /* SOUTHWEST */
+ if ((*col >= 1 && *row + 1 < AT_BITMAP_HEIGHT(marked)
+ && !is_marked_edge(TOP, *row + 1, *col - 1, marked)
+ && is_outline_edge(TOP, bitmap, *row + 1, *col - 1, color, exp))) {
+ *edge = TOP;
+ (*col)--;
+ (*row)++;
+ pos.x = *col;
+ pos.y = AT_BITMAP_HEIGHT(bitmap) - *row;
+ break;
+ }
+ CHECK_FATAL();
+ case NO_EDGE:
+ default:
+ *edge = NO_EDGE;
+ break;
+ }
+cleanup:
+ return (pos);
+}