1 /* pxl-outline.c: find the outlines of a bitmap image; each outline is made up of one or more pixels;
2 and each pixel participates via one or more edges. */
3
4 #ifdef HAVE_CONFIG_H
5 #include "config.h"
6 #endif /* Def: HAVE_CONFIG_H */
7
8 #include "message.h"
9 #include "types.h"
10 #include "bitmap.h"
11 #include "color.h"
12 #include "bitmap.h"
13 #include "logreport.h"
14 #include "xstd.h"
15 #include "pxl-outline.h"
16 #include <assert.h>
17
18 /* We consider each pixel to consist of four edges, and we travel along
19 edges, instead of through pixel centers. This is necessary for those
20 unfortunate times when a single pixel is on both an inside and an
21 outside outline.
22
23 The numbers chosen here are not arbitrary; the code that figures out
24 which edge to move to depends on particular values. See the
25 `TRY_PIXEL' macro in `edge.c'. To emphasize this, I've written in the
26 numbers we need for each edge value. */
27
28 typedef enum
29 {
30 TOP = 1, LEFT = 2, BOTTOM = 3, RIGHT = 0, NO_EDGE = 4
31 } edge_type;
32
33 /* This choice is also not arbitrary: starting at the top edge makes the
34 code find outside outlines before inside ones, which is certainly
35 what we want. */
36 #define START_EDGE top
37
38 typedef enum
39 {
40 NORTH = 0, NORTHWEST = 1, WEST = 2, SOUTHWEST = 3, SOUTH = 4,
41 SOUTHEAST = 5, EAST = 6, NORTHEAST = 7
42 } direction_type;
43
44 #define NUM_EDGES NO_EDGE
45
46 #define COMPUTE_DELTA(axis, dir) \
47 ((dir) % 2 != 0 \
48 ? COMPUTE_##axis##_DELTA ((dir) - 1) \
49 + COMPUTE_##axis##_DELTA (((dir) + 1) % 8) \
50 : COMPUTE_##axis##_DELTA (dir) \
51 )
52
53 #define COMPUTE_ROW_DELTA(dir) \
54 ((dir) == NORTH ? -1 : (dir) == SOUTH ? +1 : 0)
55
56 #define COMPUTE_COL_DELTA(dir) \
57 ((dir) == WEST ? -1 : (dir) == EAST ? +1 : 0)
58
59 static pixel_outline_type find_one_outline (bitmap_type, edge_type, unsigned short,
60 unsigned short, bitmap_type *, at_bool, at_bool, at_exception_type *);
61 static pixel_outline_type find_one_centerline (bitmap_type, direction_type,
62 unsigned short, unsigned short, bitmap_type *);
63 static void append_pixel_outline (pixel_outline_list_type *,
64 pixel_outline_type);
65 static pixel_outline_type new_pixel_outline (void);
66 static void free_pixel_outline (pixel_outline_type *);
67 static void concat_pixel_outline (pixel_outline_type *,
68 const pixel_outline_type*);
69 static void append_outline_pixel (pixel_outline_type *, at_coord);
70 static at_bool is_marked_edge (edge_type, unsigned short, unsigned short, bitmap_type);
71 static at_bool is_outline_edge (edge_type, bitmap_type, unsigned short, unsigned short,
72 color_type, at_exception_type *);
73 static at_bool is_unmarked_outline_edge (unsigned short, unsigned short, edge_type,
74 bitmap_type, bitmap_type, color_type, at_exception_type *);
75
76 static void mark_edge (edge_type e, unsigned short, unsigned short, bitmap_type *);
77 static edge_type opposite_edge(edge_type);
78
79 static at_bool is_marked_dir(unsigned short, unsigned short, direction_type, bitmap_type);
80 static at_bool is_other_dir_marked(unsigned short, unsigned short, direction_type, bitmap_type);
81 static void mark_dir(unsigned short, unsigned short, direction_type, bitmap_type *);
82 static at_bool next_unmarked_pixel(unsigned short *, unsigned short *,
83 direction_type *, bitmap_type, bitmap_type *);
84
85 at_bool is_valid_dir (unsigned short, unsigned short, direction_type, bitmap_type, bitmap_type);
86
87 static at_coord next_point(bitmap_type, edge_type *, unsigned short *, unsigned short *,
88 color_type, at_bool, bitmap_type, at_exception_type * );
89 static unsigned
90 num_neighbors(unsigned short, unsigned short, bitmap_type);
91
92 #define CHECK_FATAL() if (at_exception_got_fatal(exp)) goto cleanup;
93
94 /* We go through a bitmap TOP to BOTTOM, LEFT to RIGHT, looking for each pixel with an unmarked edge
95 that we consider a starting point of an outline. */
96
97 pixel_outline_list_type
find_outline_pixels(bitmap_type bitmap,color_type * bg_color,at_progress_func notify_progress,at_address progress_data,at_testcancel_func test_cancel,at_address testcancel_data,at_exception_type * exp)98 find_outline_pixels (bitmap_type bitmap, color_type *bg_color,
99 at_progress_func notify_progress, at_address progress_data,
100 at_testcancel_func test_cancel, at_address testcancel_data,
101 at_exception_type * exp)
102 {
103 pixel_outline_list_type outline_list;
104 unsigned short row, col;
105 bitmap_type marked = new_bitmap (BITMAP_WIDTH (bitmap), BITMAP_HEIGHT (bitmap));
106 unsigned int max_progress = BITMAP_HEIGHT (bitmap) * BITMAP_WIDTH (bitmap);
107
108 O_LIST_LENGTH (outline_list) = 0;
109 outline_list.data = NULL;
110
111 for (row = 0; row < BITMAP_HEIGHT (bitmap); row++)
112 {
113 for (col = 0; col < BITMAP_WIDTH (bitmap); col++)
114 {
115 edge_type edge;
116 color_type color;
117 at_bool is_background;
118
119 if (notify_progress)
120 notify_progress((at_real)(row * BITMAP_WIDTH(bitmap) + col) / ((at_real) max_progress * (at_real)3.0),
121 progress_data);
122
123 /* A valid edge can be TOP for an outside outline.
124 Outside outlines are traced counterclockwise */
125 color = GET_COLOR (bitmap, row, col);
126 if (!(is_background = (bg_color && COLOR_EQUAL(color, *bg_color)))
127 && is_unmarked_outline_edge (row, col, edge = TOP,
128 bitmap, marked, color, exp))
129 {
130 pixel_outline_type outline;
131
132 CHECK_FATAL (); /* FREE(DONE) outline_list */
133
134 LOG1 ("#%u: (counterclockwise)", O_LIST_LENGTH (outline_list));
135
136 outline = find_one_outline (bitmap, edge, row, col, &marked, false, false, exp);
137 CHECK_FATAL(); /* FREE(DONE) outline_list */
138
139 O_CLOCKWISE (outline) = false;
140 append_pixel_outline (&outline_list, outline);
141
142 LOG1 (" [%u].\n", O_LENGTH (outline));
143 }
144 else
145 CHECK_FATAL (); /* FREE(DONE) outline_list */
146
147 /* A valid edge can be BOTTOM for an inside outline.
148 Inside outlines are traced clockwise */
149 if (row!=0)
150 {
151 color = GET_COLOR (bitmap, row-1, col);
152 if (!(bg_color && COLOR_EQUAL(color, *bg_color))
153 && is_unmarked_outline_edge (row-1, col, edge = BOTTOM,
154 bitmap, marked, color, exp))
155 {
156 pixel_outline_type outline;
157
158 CHECK_FATAL(); /* FREE(DONE) outline_list */
159
160 /* This lines are for debugging only:*/
161 if (is_background)
162 {
163 LOG1 ("#%u: (clockwise)", O_LIST_LENGTH (outline_list));
164
165 outline = find_one_outline (bitmap, edge, row-1, col,
166 &marked, true, false, exp);
167 CHECK_FATAL(); /* FREE(DONE) outline_list */
168
169 O_CLOCKWISE (outline) = true;
170 append_pixel_outline (&outline_list, outline);
171
172 LOG1 (" [%u].\n", O_LENGTH (outline));
173 }
174 else
175 {
176 outline = find_one_outline (bitmap, edge, row-1, col,
177 &marked, true, true, exp);
178 CHECK_FATAL(); /* FREE(DONE) outline_list */
179 }
180 }
181 else
182 CHECK_FATAL(); /* FREE(DONE) outline_list */
183 }
184 if (test_cancel && test_cancel(testcancel_data))
185 {
186 free_pixel_outline_list(&outline_list);
187 goto cleanup;
188 }
189 }
190 }
191 cleanup:
192 free_bitmap (&marked);
193 flush_log_output ();
194 if (at_exception_got_fatal(exp))
195 free_pixel_outline_list(&outline_list);
196 return outline_list;
197 }
198
199
200 /* We calculate one single outline here. We pass the position of the starting pixel and the
201 starting edge. All edges we track along will be marked and the outline pixels are appended
202 to the coordinate list. */
203
204 static pixel_outline_type
find_one_outline(bitmap_type bitmap,edge_type original_edge,unsigned short original_row,unsigned short original_col,bitmap_type * marked,at_bool clockwise,at_bool ignore,at_exception_type * exp)205 find_one_outline (bitmap_type bitmap, edge_type original_edge,
206 unsigned short original_row, unsigned short original_col,
207 bitmap_type *marked, at_bool clockwise, at_bool ignore,
208 at_exception_type * exp)
209 {
210 pixel_outline_type outline;
211 unsigned short row = original_row, col = original_col;
212 edge_type edge = original_edge;
213 at_coord pos;
214
215 pos.x = col + ((edge == RIGHT) || (edge == BOTTOM) ? 1 : 0);
216 pos.y = BITMAP_HEIGHT (bitmap) - row - 1 + ((edge == TOP) || (edge == RIGHT) ? 1 : 0);
217
218 if (!ignore)
219 outline = new_pixel_outline ();
220 outline.color = GET_COLOR (bitmap, row, col);
221
222 do
223 {
224 /* Put this edge into the output list */
225 if (!ignore)
226 {
227 LOG2 (" (%d,%d)", pos.x, pos.y);
228 append_outline_pixel (&outline, pos);
229 }
230
231 mark_edge (edge, row, col, marked);
232 pos = next_point (bitmap, &edge, &row, &col, outline.color, clockwise, *marked, exp);
233 CHECK_FATAL();
234 }
235 while (edge != NO_EDGE);
236
237 cleanup:
238 if (at_exception_got_fatal(exp))
239 free_pixel_outline(&outline);
240 return outline;
241 }
242
is_valid_dir(unsigned short row,unsigned short col,direction_type dir,bitmap_type bitmap,bitmap_type marked)243 at_bool is_valid_dir (unsigned short row, unsigned short col, direction_type dir, bitmap_type bitmap, bitmap_type marked)
244 {
245
246 return (!is_marked_dir(row, col, dir, marked)
247 && COMPUTE_DELTA(ROW, dir)+row > 0
248 && COMPUTE_DELTA(COL, dir)+col > 0
249 && BITMAP_VALID_PIXEL(bitmap, COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col)
250 && COLOR_EQUAL(GET_COLOR(bitmap, COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col),
251 GET_COLOR(bitmap, row, col)));
252 }
253
254 pixel_outline_list_type
find_centerline_pixels(bitmap_type bitmap,color_type bg_color,at_progress_func notify_progress,at_address progress_data,at_testcancel_func test_cancel,at_address testcancel_data,at_exception_type * exp)255 find_centerline_pixels (bitmap_type bitmap, color_type bg_color,
256 at_progress_func notify_progress, at_address progress_data,
257 at_testcancel_func test_cancel, at_address testcancel_data,
258 at_exception_type * exp)
259 {
260 pixel_outline_list_type outline_list;
261 signed short row, col;
262 bitmap_type marked = new_bitmap(BITMAP_WIDTH(bitmap), BITMAP_HEIGHT (bitmap));
263 unsigned int max_progress = BITMAP_HEIGHT (bitmap) * BITMAP_WIDTH (bitmap);
264
265 O_LIST_LENGTH(outline_list) = 0;
266 outline_list.data = NULL;
267
268 for (row = 0; row < BITMAP_HEIGHT(bitmap); row++)
269 {
270 for (col = 0; col < BITMAP_WIDTH(bitmap); )
271 {
272 direction_type dir=EAST;
273 pixel_outline_type outline;
274 at_bool clockwise = false;
275
276 if (notify_progress)
277 notify_progress((at_real)(row * BITMAP_WIDTH(bitmap) + col) / ((at_real) max_progress * (at_real)3.0),
278 progress_data);
279
280 if (COLOR_EQUAL(GET_COLOR(bitmap, row, col), bg_color))
281 {
282 col++;
283 continue;
284 }
285
286 if (!is_valid_dir(row, col, dir, bitmap, marked)
287 || (!is_valid_dir(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, dir, bitmap, marked)
288 && num_neighbors(row, col, bitmap) > 2)
289 || num_neighbors(row, col, bitmap) > 4
290 || num_neighbors(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, bitmap) > 4
291 || (is_other_dir_marked(row, col, dir, marked)
292 && is_other_dir_marked(row+COMPUTE_DELTA(ROW, dir), col+COMPUTE_DELTA(COL, dir), dir, marked)))
293 {
294 dir = SOUTHEAST;
295 if (!is_valid_dir(row, col, dir, bitmap, marked)
296 || (!is_valid_dir(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, dir, bitmap, marked)
297 && num_neighbors(row, col, bitmap) > 2)
298 || num_neighbors(row, col, bitmap) > 4
299 || num_neighbors(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, bitmap) > 4
300 || (is_other_dir_marked(row, col, dir, marked)
301 && is_other_dir_marked(row+COMPUTE_DELTA(ROW, dir), col+COMPUTE_DELTA(COL, dir), dir, marked)))
302 {
303 dir = SOUTH;
304 if (!is_valid_dir(row, col, dir, bitmap, marked)
305 || (!is_valid_dir(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, dir, bitmap, marked)
306 && num_neighbors(row, col, bitmap) > 2)
307 || num_neighbors(row, col, bitmap) > 4
308 || num_neighbors(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, bitmap) > 4
309 || (is_other_dir_marked(row, col, dir, marked)
310 && is_other_dir_marked(row+COMPUTE_DELTA(ROW, dir), col+COMPUTE_DELTA(COL, dir), dir, marked)))
311 {
312 dir = SOUTHWEST;
313 if (!is_valid_dir(row, col, dir, bitmap, marked)
314 || (!is_valid_dir(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, dir, bitmap, marked)
315 && num_neighbors(row, col, bitmap) > 2)
316 || num_neighbors(row, col, bitmap) > 4
317 || num_neighbors(COMPUTE_DELTA(ROW, dir)+row, COMPUTE_DELTA(COL, dir)+col, bitmap) > 4
318 || (is_other_dir_marked(row, col, dir, marked)
319 && is_other_dir_marked(row+COMPUTE_DELTA(ROW, dir), col+COMPUTE_DELTA(COL, dir), dir, marked)))
320 {
321 col++;
322 continue;
323 }
324 }
325 }
326 }
327
328 LOG2("#%u: (%sclockwise) ", O_LIST_LENGTH(outline_list),
329 clockwise ? "" : "counter");
330
331 outline = find_one_centerline(bitmap, dir, row, col, &marked);
332
333 /* If the outline is open (i.e., we didn't return to the
334 starting pixel), search from the starting pixel in the
335 opposite direction and concatenate the two outlines. */
336
337 if (outline.open)
338 {
339 pixel_outline_type partial_outline;
340 at_bool okay = false;
341
342 if (dir == EAST)
343 {
344 dir = SOUTH;
345 if (!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
346 {
347 dir = SOUTHWEST;
348 if (!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
349 {
350 dir = SOUTHEAST;
351 okay=is_valid_dir(row, col, dir, bitmap, marked);
352 }
353 }
354 }
355 else if (dir == SOUTHEAST)
356 {
357 dir = SOUTHWEST;
358 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
359 {
360 dir = EAST;
361 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
362 {
363 dir = SOUTH;
364 okay=is_valid_dir(row, col, dir, bitmap, marked);
365 }
366 }
367 }
368 else if (dir == SOUTH)
369 {
370 dir = EAST;
371 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
372 {
373 dir = SOUTHEAST;
374 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
375 {
376 dir = SOUTHWEST;
377 okay=is_valid_dir(row, col, dir, bitmap, marked);
378 }
379 }
380 }
381 else if (dir == SOUTHWEST)
382 {
383 dir = SOUTHEAST;
384 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
385 {
386 dir = EAST;
387 if(!(okay=is_valid_dir(row, col, dir, bitmap, marked)))
388 {
389 dir = SOUTH;
390 okay=is_valid_dir(row, col, dir, bitmap, marked);
391 }
392 }
393 }
394 if (okay)
395 {
396 partial_outline =
397 find_one_centerline(bitmap, dir, row, col, &marked);
398 concat_pixel_outline(&outline, &partial_outline);
399 if (partial_outline.data)
400 free(partial_outline.data);
401 }
402 else
403 col++;
404 }
405
406 /* Outside outlines will start at a top edge, and move
407 counterclockwise, and inside outlines will start at a
408 bottom edge, and move clockwise. This happens because of
409 the order in which we look at the edges. */
410 O_CLOCKWISE(outline) = clockwise;
411 if (O_LENGTH(outline) > 1)
412 append_pixel_outline(&outline_list, outline);
413 LOG1("(%s)", (outline.open ? " open" : " closed"));
414 LOG1(" [%u].\n", O_LENGTH(outline));
415 if (O_LENGTH(outline) == 1)
416 free_pixel_outline(&outline);
417 }
418 }
419 if (test_cancel && test_cancel(testcancel_data))
420 {
421 if (O_LIST_LENGTH (outline_list) != 0)
422 free_pixel_outline_list (&outline_list);
423 goto cleanup;
424 }
425 cleanup:
426 free_bitmap(&marked);
427 flush_log_output();
428 return outline_list;
429 }
430
431
432 static pixel_outline_type
find_one_centerline(bitmap_type bitmap,direction_type search_dir,unsigned short original_row,unsigned short original_col,bitmap_type * marked)433 find_one_centerline(bitmap_type bitmap, direction_type search_dir,
434 unsigned short original_row, unsigned short original_col, bitmap_type *marked)
435 {
436 pixel_outline_type outline = new_pixel_outline();
437 direction_type original_dir = search_dir;
438 unsigned short row = original_row, col = original_col;
439 unsigned short prev_row, prev_col;
440 at_coord pos;
441
442 outline.open = false;
443 outline.color = GET_COLOR(bitmap, row, col);
444
445 /* Add the starting pixel to the output list, changing from bitmap
446 to Cartesian coordinates and specifying the left edge so that
447 the coordinates won't be adjusted. */
448 pos.x = col; pos.y = BITMAP_HEIGHT(bitmap) - row - 1;
449 LOG2 (" (%d,%d)", pos.x, pos.y);
450 append_outline_pixel(&outline, pos);
451
452 for ( ; ; )
453 {
454 prev_row = row; prev_col = col;
455
456 /* If there is no adjacent, unmarked pixel, we can't proceed
457 any further, so return an open outline. */
458 if (!next_unmarked_pixel(&row, &col, &search_dir,
459 bitmap, marked))
460 {
461 outline.open = true;
462 break;
463 }
464
465 /* If we've moved to a new pixel, mark all edges of the previous
466 pixel so that it won't be revisited. */
467 if (!(prev_row == original_row && prev_col == original_col))
468 mark_dir(prev_row, prev_col, search_dir, marked);
469 mark_dir(row, col, (search_dir+4)%8, marked);
470
471 /* If we've returned to the starting pixel, we're done. */
472 if (row == original_row && col == original_col)
473 break;
474
475 /* Add the new pixel to the output list. */
476 pos.x = col; pos.y = BITMAP_HEIGHT(bitmap) - row - 1;
477 LOG2 (" (%d,%d)", pos.x, pos.y);
478 append_outline_pixel(&outline, pos);
479 }
480 mark_dir(original_row, original_col, original_dir, marked);
481 return outline;
482 }
483
484
485 /* Add an outline to an outline list. */
486
487 static void
append_pixel_outline(pixel_outline_list_type * outline_list,pixel_outline_type outline)488 append_pixel_outline (pixel_outline_list_type *outline_list,
489 pixel_outline_type outline)
490 {
491 O_LIST_LENGTH (*outline_list)++;
492 XREALLOC (outline_list->data, outline_list->length * sizeof (pixel_outline_type));
493 O_LIST_OUTLINE (*outline_list, O_LIST_LENGTH (*outline_list) - 1) = outline;
494 }
495
496
497 /* Free the list of outline lists. */
498
499 void
free_pixel_outline_list(pixel_outline_list_type * outline_list)500 free_pixel_outline_list (pixel_outline_list_type *outline_list)
501 {
502 unsigned this_outline;
503
504 for (this_outline = 0; this_outline < outline_list->length; this_outline++)
505 {
506 pixel_outline_type o = outline_list->data[this_outline];
507 free_pixel_outline (&o);
508 }
509 outline_list->length = 0;
510
511 if (outline_list->data != NULL)
512 {
513 free (outline_list->data);
514 outline_list->data = NULL;
515 }
516
517 flush_log_output ();
518 }
519
520
521 /* Return an empty list of pixels. */
522
523
524 static pixel_outline_type
new_pixel_outline(void)525 new_pixel_outline (void)
526 {
527 pixel_outline_type pixel_outline;
528
529 O_LENGTH (pixel_outline) = 0;
530 pixel_outline.data = NULL;
531 pixel_outline.open = false;
532
533 return pixel_outline;
534 }
535
536 static void
free_pixel_outline(pixel_outline_type * outline)537 free_pixel_outline (pixel_outline_type * outline)
538 {
539 if (outline->data)
540 {
541 free (outline->data) ;
542 outline->data = NULL;
543 outline->length = 0;
544 }
545 }
546
547 /* Concatenate two pixel lists. The two lists are assumed to have the
548 same starting pixel and to proceed in opposite directions therefrom. */
549
550 static void
concat_pixel_outline(pixel_outline_type * o1,const pixel_outline_type * o2)551 concat_pixel_outline(pixel_outline_type *o1, const pixel_outline_type *o2)
552 {
553 int src, dst;
554 unsigned o1_length, o2_length;
555 if (!o1 || !o2 || O_LENGTH(*o2) <= 1) return;
556
557 o1_length = O_LENGTH(*o1);
558 o2_length = O_LENGTH(*o2);
559 O_LENGTH(*o1) += o2_length - 1;
560 /* Resize o1 to the sum of the lengths of o1 and o2 minus one (because
561 the two lists are assumed to share the same starting pixel). */
562 XREALLOC(o1->data, O_LENGTH(*o1) * sizeof(at_coord));
563 /* Shift the contents of o1 to the end of the new array to make room
564 to prepend o2. */
565 for (src = o1_length - 1, dst = O_LENGTH(*o1) - 1; src >= 0; src--, dst--)
566 O_COORDINATE(*o1, dst) = O_COORDINATE(*o1, src);
567 /* Prepend the contents of o2 (in reverse order) to o1. */
568 for (src = o2_length - 1, dst = 0; src > 0; src--, dst++)
569 O_COORDINATE(*o1, dst) = O_COORDINATE(*o2, src);
570 }
571
572
573 /* Add a point to the pixel list. */
574
575 static void
append_outline_pixel(pixel_outline_type * o,at_coord c)576 append_outline_pixel (pixel_outline_type *o, at_coord c)
577 {
578 O_LENGTH (*o)++;
579 XREALLOC (o->data, O_LENGTH (*o) * sizeof (at_coord));
580 O_COORDINATE (*o, O_LENGTH (*o) - 1) = c;
581 }
582
583
584 /* Is this really an edge and is it still unmarked? */
585
586 static at_bool
is_unmarked_outline_edge(unsigned short row,unsigned short col,edge_type edge,bitmap_type bitmap,bitmap_type marked,color_type color,at_exception_type * exp)587 is_unmarked_outline_edge (unsigned short row, unsigned short col,
588 edge_type edge, bitmap_type bitmap,
589 bitmap_type marked, color_type color, at_exception_type * exp)
590 {
591 return
592 (at_bool)(!is_marked_edge (edge, row, col, marked)
593 && is_outline_edge (edge, bitmap, row, col, color, exp));
594 }
595
596
597 /* We check to see if the edge of the pixel at position ROW and COL
598 is an outline edge */
599
600 static at_bool
is_outline_edge(edge_type edge,bitmap_type bitmap,unsigned short row,unsigned short col,color_type color,at_exception_type * exp)601 is_outline_edge (edge_type edge, bitmap_type bitmap,
602 unsigned short row, unsigned short col, color_type color,
603 at_exception_type * exp)
604 {
605 /* If this pixel isn't of the same color, it's not part of the outline. */
606 if (!COLOR_EQUAL (GET_COLOR (bitmap, row, col), color))
607 return false;
608
609 switch (edge)
610 {
611 case LEFT:
612 return (at_bool)(col == 0 || !COLOR_EQUAL (GET_COLOR (bitmap, row, col - 1), color));
613
614 case TOP:
615 return (at_bool)(row == 0 || !COLOR_EQUAL (GET_COLOR (bitmap, row - 1, col), color));
616
617 case RIGHT:
618 return (at_bool)(col == BITMAP_WIDTH (bitmap) - 1
619 || !COLOR_EQUAL(GET_COLOR (bitmap, row, col + 1), color));
620
621 case BOTTOM:
622 return (at_bool)(row == BITMAP_HEIGHT (bitmap) - 1
623 || !COLOR_EQUAL(GET_COLOR (bitmap, row + 1, col), color));
624
625 case NO_EDGE:
626 default:
627 LOG1 ("is_outline_edge: Bad edge value(%d)", edge);
628 at_exception_fatal(exp, "is_outline_edge: Bad edge value");
629 }
630
631 return false; /* NOT REACHED */
632 }
633
634
635 /* If EDGE is not already marked, we mark it; otherwise, it's a fatal error.
636 The position ROW and COL should be inside the bitmap MARKED. EDGE can be
637 NO_EDGE. */
638
639 static void
mark_edge(edge_type edge,unsigned short row,unsigned short col,bitmap_type * marked)640 mark_edge (edge_type edge, unsigned short row, unsigned short col, bitmap_type *marked)
641 {
642 *BITMAP_PIXEL (*marked, row, col) |= 1 << edge;
643 }
644
645
646 /* Mark the direction of the pixel ROW/COL in MARKED. */
647
648 static void
mark_dir(unsigned short row,unsigned short col,direction_type dir,bitmap_type * marked)649 mark_dir(unsigned short row, unsigned short col, direction_type dir, bitmap_type *marked)
650 {
651 *BITMAP_PIXEL(*marked, row, col) |= 1 << dir;
652 }
653
654
655 /* Test if the direction of pixel at ROW/COL in MARKED is marked. */
656
657 static at_bool
is_marked_dir(unsigned short row,unsigned short col,direction_type dir,bitmap_type marked)658 is_marked_dir(unsigned short row, unsigned short col, direction_type dir, bitmap_type marked)
659 {
660 return (at_bool)((*BITMAP_PIXEL(marked, row, col) & 1 << dir) != 0);
661 }
662
663
664 static at_bool
is_other_dir_marked(unsigned short row,unsigned short col,direction_type dir,bitmap_type marked)665 is_other_dir_marked(unsigned short row, unsigned short col, direction_type dir, bitmap_type marked)
666 {
667 return (at_bool)((*BITMAP_PIXEL(marked, row, col) & (255 - (1 << dir) - (1 << ((dir + 4) % 8))) ) != 0);
668 }
669
670
671 static at_bool
next_unmarked_pixel(unsigned short * row,unsigned short * col,direction_type * dir,bitmap_type bitmap,bitmap_type * marked)672 next_unmarked_pixel(unsigned short *row, unsigned short *col,
673 direction_type *dir, bitmap_type bitmap, bitmap_type *marked)
674 {
675 color_type color;
676 unsigned orig_row = *row, orig_col = *col;
677 direction_type orig_dir = *dir, test_dir = *dir;
678
679 color = GET_COLOR(bitmap, *row, *col);
680 do
681 {
682 if (is_valid_dir(orig_row, orig_col, test_dir, bitmap, *marked))
683 {
684 *row = orig_row + COMPUTE_DELTA(ROW, test_dir);
685 *col = orig_col + COMPUTE_DELTA(COL, test_dir);
686 *dir = test_dir;
687 break;
688 }
689
690 if (orig_dir == test_dir)
691 test_dir = (orig_dir + 2) % 8;
692 else if ((orig_dir + 2) % 8 == test_dir)
693 test_dir = (orig_dir + 6) % 8;
694 else if ((orig_dir + 6) % 8 == test_dir)
695 test_dir = (orig_dir + 1) % 8;
696 else if ((orig_dir + 1) % 8 == test_dir)
697 test_dir = (orig_dir + 7) % 8;
698 else if ((orig_dir + 7) % 8 == test_dir)
699 test_dir = (orig_dir + 3) % 8;
700 else if ((orig_dir + 3) % 8 == test_dir)
701 test_dir = (orig_dir + 5) % 8;
702 else if ((orig_dir + 5) % 8 == test_dir)
703 break;
704 }
705 while (1);
706 if ((*row != orig_row || *col != orig_col) &&
707 (!(is_other_dir_marked(orig_row,orig_col,test_dir,*marked)
708 &&is_other_dir_marked(orig_row + COMPUTE_DELTA(ROW, test_dir), orig_col + COMPUTE_DELTA(COL, test_dir),test_dir,*marked))))
709 return true;
710 else
711 return false;
712 }
713
714
715 /* Return the number of pixels adjacent to pixel ROW/COL that are black. */
716
717 static unsigned
num_neighbors(unsigned short row,unsigned short col,bitmap_type bitmap)718 num_neighbors(unsigned short row, unsigned short col, bitmap_type bitmap)
719 {
720 unsigned dir, count = 0;
721 color_type color = GET_COLOR(bitmap, row, col);
722 for (dir = NORTH; dir <= NORTHEAST; dir++)
723 {
724 int delta_r = COMPUTE_DELTA(ROW, dir);
725 int delta_c = COMPUTE_DELTA(COL, dir);
726 unsigned int test_row = row + delta_r;
727 unsigned int test_col = col + delta_c;
728 if (BITMAP_VALID_PIXEL(bitmap, test_row, test_col)
729 && COLOR_EQUAL(GET_COLOR(bitmap, test_row, test_col), color))
730 ++count;
731 }
732 return count;
733 }
734
735
736 /* Test if the edge EDGE at ROW/COL in MARKED is marked. */
737
738 static at_bool
is_marked_edge(edge_type edge,unsigned short row,unsigned short col,bitmap_type marked)739 is_marked_edge (edge_type edge, unsigned short row, unsigned short col, bitmap_type marked)
740 {
741 return
742 (at_bool)(edge == NO_EDGE ? false : (*BITMAP_PIXEL (marked, row, col) & (1 << edge)) != 0);
743 }
744
next_point(bitmap_type bitmap,edge_type * edge,unsigned short * row,unsigned short * col,color_type color,at_bool clockwise,bitmap_type marked,at_exception_type * exp)745 static at_coord next_point(bitmap_type bitmap, edge_type *edge, unsigned short *row, unsigned short *col,
746 color_type color, at_bool clockwise, bitmap_type marked,
747 at_exception_type * exp)
748 {
749 at_coord pos = {0, 0};
750
751 if (!clockwise)
752 switch(*edge)
753 {
754 case TOP:
755 /* WEST */
756 if((*col >=1
757 &&!is_marked_edge(TOP,*row,*col-1, marked)
758 && is_outline_edge(TOP,bitmap,*row,*col-1, color, exp)))
759 {
760 /**edge = TOP;*/
761 (*col)--;
762 pos.x = *col;
763 pos.y = BITMAP_HEIGHT (bitmap) - *row;
764 break;
765 }
766 CHECK_FATAL();
767 /* NORTHWEST */
768 if((*col >=1 && *row >= 1
769 && !is_marked_edge(RIGHT,*row-1,*col-1, marked)
770 && is_outline_edge(RIGHT,bitmap,*row-1,*col-1, color, exp)) &&
771 !(is_marked_edge(LEFT,*row-1,*col, marked) && is_marked_edge(TOP, *row,*col-1, marked)) &&
772 !(is_marked_edge(BOTTOM,*row-1,*col, marked) && is_marked_edge(RIGHT, *row,*col-1, marked)))
773 {
774 *edge = RIGHT;
775 (*col)--;
776 (*row)--;
777 pos.x = *col+1;
778 pos.y = BITMAP_HEIGHT (bitmap) - *row;
779 break;
780 }
781 CHECK_FATAL();
782 if ((!is_marked_edge(LEFT,*row,*col, marked)
783 && is_outline_edge(LEFT,bitmap,*row,*col, color, exp)))
784 {
785 *edge = LEFT;
786 pos.x = *col;
787 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
788 break;
789 }
790 CHECK_FATAL();
791 *edge = NO_EDGE;
792 break;
793 case RIGHT:
794 /* NORTH */
795 if((*row >=1
796 &&!is_marked_edge(RIGHT,*row-1,*col, marked)
797 && is_outline_edge(RIGHT,bitmap,*row-1,*col, color, exp)))
798 {
799 /**edge = RIGHT;*/
800 (*row)--;
801 pos.x = *col+1;
802 pos.y = BITMAP_HEIGHT (bitmap) - *row;
803 break;
804 }
805 CHECK_FATAL();
806 /* NORTHEAST */
807 if((*col+1 < BITMAP_WIDTH (marked) && *row >= 1
808 && !is_marked_edge(BOTTOM,*row-1,*col+1, marked)
809 && is_outline_edge(BOTTOM,bitmap,*row-1,*col+1, color, exp)) &&
810 !(is_marked_edge(LEFT,*row,*col+1, marked) && is_marked_edge(BOTTOM, *row-1,*col, marked)) &&
811 !(is_marked_edge(TOP,*row,*col+1, marked) && is_marked_edge(RIGHT, *row-1,*col, marked)))
812 {
813 *edge = BOTTOM;
814 (*col)++;
815 (*row)--;
816 pos.x = *col+1;
817 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
818 break;
819 }
820 CHECK_FATAL();
821 if ((!is_marked_edge(TOP,*row,*col, marked)
822 && is_outline_edge(TOP,bitmap,*row,*col, color, exp)))
823 {
824 *edge = TOP;
825 pos.x = *col;
826 pos.y = BITMAP_HEIGHT (bitmap) - *row;
827 break;
828 }
829 CHECK_FATAL();
830 *edge = NO_EDGE;
831 break;
832 case BOTTOM:
833 /* EAST */
834 if((*col+1 < BITMAP_WIDTH (marked)
835 && !is_marked_edge(BOTTOM,*row,*col+1, marked)
836 && is_outline_edge(BOTTOM,bitmap,*row,*col+1, color, exp)))
837 {
838 /**edge = BOTTOM;*/
839 (*col)++;
840 pos.x = *col+1;
841 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
842 break;
843 }
844 CHECK_FATAL();
845 /* SOUTHEAST */
846 if((*col+1 < BITMAP_WIDTH (marked) && *row+1 < BITMAP_HEIGHT (marked)
847 && !is_marked_edge(LEFT,*row+1,*col+1, marked)
848 && is_outline_edge(LEFT,bitmap,*row+1,*col+1, color, exp)) &&
849 !(is_marked_edge(TOP,*row+1,*col, marked) && is_marked_edge(LEFT, *row,*col+1, marked)) &&
850 !(is_marked_edge(RIGHT,*row+1,*col, marked) && is_marked_edge(BOTTOM,*row,*col+1, marked)))
851 {
852 *edge = LEFT;
853 (*col)++;
854 (*row)++;
855 pos.x = *col;
856 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
857 break;
858 }
859 CHECK_FATAL();
860 if ((!is_marked_edge(RIGHT,*row,*col, marked)
861 && is_outline_edge(RIGHT,bitmap,*row,*col, color, exp)))
862 {
863 *edge = RIGHT;
864 pos.x = *col+1;
865 pos.y = BITMAP_HEIGHT (bitmap) - *row;
866 break;
867 }
868 CHECK_FATAL();
869 *edge = NO_EDGE;
870 break;
871 case LEFT:
872 /* SOUTH */
873 if((*row+1 < BITMAP_HEIGHT (marked)
874 && !is_marked_edge(LEFT,*row+1,*col, marked)
875 && is_outline_edge(LEFT,bitmap,*row+1,*col, color, exp)))
876 {
877 /**edge = LEFT;*/
878 (*row)++;
879 pos.x = *col;
880 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
881 break;
882 }
883 CHECK_FATAL();
884 /* SOUTHWEST */
885 if((*col >= 1 && *row+1 < BITMAP_HEIGHT (marked)
886 && !is_marked_edge(TOP,*row+1,*col-1, marked)
887 && is_outline_edge(TOP,bitmap,*row+1,*col-1, color, exp)) &&
888 !(is_marked_edge(RIGHT,*row,*col-1, marked) && is_marked_edge(TOP, *row+1,*col, marked)) &&
889 !(is_marked_edge(BOTTOM, *row,*col-1, marked) && is_marked_edge(LEFT, *row+1,*col, marked)))
890 {
891 *edge = TOP;
892 (*col)--;
893 (*row)++;
894 pos.x = *col;
895 pos.y = BITMAP_HEIGHT (bitmap) - *row;
896 break;
897 }
898 CHECK_FATAL();
899 if ((!is_marked_edge(BOTTOM,*row,*col, marked)
900 && is_outline_edge(BOTTOM,bitmap,*row,*col, color, exp)))
901 {
902 *edge = BOTTOM;
903 pos.x = *col+1;
904 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
905 break;
906 }
907 CHECK_FATAL();
908 case NO_EDGE:
909 default:
910 *edge = NO_EDGE;
911 break;
912 }
913 else
914 switch(*edge)
915 {
916 case TOP:
917 if ((!is_marked_edge(LEFT,*row,*col, marked)
918 && is_outline_edge(LEFT,bitmap,*row,*col, color, exp)))
919 {
920 *edge = LEFT;
921 pos.x=*col;
922 pos.y=BITMAP_HEIGHT (bitmap) - *row - 1;
923 break;
924 }
925 CHECK_FATAL();
926 /* WEST */
927 if((*col >=1
928 &&!is_marked_edge(TOP,*row,*col-1, marked)
929 && is_outline_edge(TOP,bitmap,*row,*col-1, color, exp)))
930 {
931 /**edge = TOP;*/
932 (*col)--;
933 pos.x = *col;
934 pos.y = BITMAP_HEIGHT (bitmap) - *row;
935 break;
936 }
937 CHECK_FATAL();
938 /* NORTHWEST */
939 if((*col >=1 && *row >= 1
940 && !is_marked_edge(RIGHT,*row-1,*col-1, marked)
941 && is_outline_edge(RIGHT,bitmap,*row-1,*col-1, color, exp)))
942 {
943 *edge = RIGHT;
944 (*col)--;
945 (*row)--;
946 pos.x = *col+1;
947 pos.y = BITMAP_HEIGHT (bitmap) - *row;
948 break;
949 }
950 CHECK_FATAL();
951 *edge = NO_EDGE;
952 break;
953 case RIGHT:
954 if ((!is_marked_edge(TOP,*row,*col, marked)
955 && is_outline_edge(TOP,bitmap,*row,*col, color, exp)))
956 {
957 *edge = TOP;
958 pos.x = *col;
959 pos.y = BITMAP_HEIGHT (bitmap) - *row;
960 break;
961 }
962 CHECK_FATAL();
963 /* NORTH */
964 if((*row >=1
965 &&!is_marked_edge(RIGHT,*row-1,*col, marked)
966 && is_outline_edge(RIGHT,bitmap,*row-1,*col, color, exp)))
967 {
968 /**edge = RIGHT;*/
969 (*row)--;
970 pos.x = *col+1;
971 pos.y = BITMAP_HEIGHT (bitmap) - *row;
972 break;
973 }
974 CHECK_FATAL();
975 /* NORTHEAST */
976 if((*col+1 < BITMAP_WIDTH (marked) && *row >= 1
977 && !is_marked_edge(BOTTOM,*row-1,*col+1, marked)
978 && is_outline_edge(BOTTOM,bitmap,*row-1,*col+1, color, exp)))
979 {
980 *edge = BOTTOM;
981 (*col)++;
982 (*row)--;
983 pos.x = *col+1;
984 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
985 break;
986 }
987 CHECK_FATAL();
988 *edge = NO_EDGE;
989 break;
990 case BOTTOM:
991 if ((!is_marked_edge(RIGHT,*row,*col, marked)
992 && is_outline_edge(RIGHT,bitmap,*row,*col, color, exp)))
993 {
994 *edge = RIGHT;
995 pos.x = *col+1;
996 pos.y = BITMAP_HEIGHT (bitmap) - *row;
997 break;
998 }
999 CHECK_FATAL();
1000 /* EAST */
1001 if((*col+1 < BITMAP_WIDTH (marked)
1002 && !is_marked_edge(BOTTOM,*row,*col+1, marked)
1003 && is_outline_edge(BOTTOM,bitmap,*row,*col+1, color, exp)))
1004 {
1005 /**edge = BOTTOM;*/
1006 (*col)++;
1007 pos.x = *col+1;
1008 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
1009 break;
1010 }
1011 CHECK_FATAL();
1012 /* SOUTHEAST */
1013 if((*col+1 < BITMAP_WIDTH (marked) && *row+1 < BITMAP_HEIGHT (marked)
1014 && !is_marked_edge(LEFT,*row+1,*col+1, marked)
1015 && is_outline_edge(LEFT,bitmap,*row+1,*col+1, color, exp)))
1016 {
1017 *edge = LEFT;
1018 (*col)++;
1019 (*row)++;
1020 pos.x = *col;
1021 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
1022 break;
1023 }
1024 CHECK_FATAL();
1025 *edge = NO_EDGE;
1026 break;
1027 case LEFT:
1028 if ((!is_marked_edge(BOTTOM,*row,*col, marked)
1029 && is_outline_edge(BOTTOM,bitmap,*row,*col, color, exp)))
1030 {
1031 *edge = BOTTOM;
1032 pos.x = *col+1;
1033 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
1034 break;
1035 }
1036 CHECK_FATAL();
1037 /* SOUTH */
1038 if((*row+1 < BITMAP_HEIGHT (marked)
1039 && !is_marked_edge(LEFT,*row+1,*col, marked)
1040 && is_outline_edge(LEFT,bitmap,*row+1,*col, color, exp)))
1041 {
1042 /**edge = LEFT;*/
1043 (*row)++;
1044 pos.x = *col;
1045 pos.y = BITMAP_HEIGHT (bitmap) - *row - 1;
1046 break;
1047 }
1048 CHECK_FATAL();
1049 /* SOUTHWEST */
1050 if((*col >= 1 && *row+1 < BITMAP_HEIGHT (marked)
1051 && !is_marked_edge(TOP,*row+1,*col-1, marked)
1052 && is_outline_edge(TOP,bitmap,*row+1,*col-1, color, exp)))
1053 {
1054 *edge = TOP;
1055 (*col)--;
1056 (*row)++;
1057 pos.x = *col;
1058 pos.y = BITMAP_HEIGHT (bitmap) - *row;
1059 break;
1060 }
1061 CHECK_FATAL();
1062 case NO_EDGE:
1063 default:
1064 *edge = NO_EDGE;
1065 break;
1066 }
1067 cleanup:
1068 return(pos);
1069 }
1070