Adding upstream version 1.2.2.upstream/1.2.2upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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);
+}