Contour Tracing Algorithms

What follows are four of the most common contour tracing algorithms. The first two, namely: the Square Tracing algorithm and Moore-Neighbor Tracing are easy to implement and are therefore used frequently to trace the contour of a given pattern. Unfortunately, both of these algorithms have a number of weaknesses which cause them to fail in tracing the contour of a large class of patterns due to their special kind of connectivity.

The following algorithms will ignore any "holes"  present in the pattern. For example, if we're given a pattern like that of Figure 1 below, the contour traced by the algorithms will be similar to the one shown in Figure 2 (the blue pixels represent the contour). This could be acceptable in some applications but in other applications, like character recognition, we would want to trace the interior of the pattern as well in order to capture any holes which identify a certain character. (Figure 3 below shows  the "complete" contour of the pattern)
As a result, a "hole searching" algorithm should be used to first extract the holes in a given pattern and then apply a contour tracing algorithm on each hole in order to extract the complete contour.



Square Tracing Algorithm
Moore-Neighbor Tracing
Radial Sweep
Theo Pavlidis' Algorithm

All comments and questions are welcomed...