Radial Sweep

The Radial Sweep algorithm is a contour tracing algorithm that has been explained in some of the literature. Unlike its fancy name, the idea behind it is very simple. As a matter of fact, it turns out that the Radial Sweep algorithm is identical to Moore-Neighbor Tracing. So you must be asking: "Why did we bother to mention it here?". Well...

Moore-Neighbor tracing searches the Moore neighborhood of the current boundary pixel in a certain direction (we've chosen clockwise), until it finds a black pixel. It then declares that pixel as the current boundary pixel and proceeds as before.
The Radial Sweep algorithm does the exact same thing. On the other hand, it provides an interesting method for finding the next black pixel in the Moore neighborhood of a given boundary pixel.
The idea behind that method is the following:
every time you locate a new boundary pixel, make it your current pixel, P, and draw an imaginary line segment joining P to the previous boundary pixel. Then, rotate the segment about P in a clockwise direction until it hits a black pixel in P's Moore neighborhood. Rotating the segment is identical to checking each pixel in the Moore neighborhood of P.

We have provided the following animated demonstration in order to explain how the Radial Sweep algorithm works and how similar it is to Moore-Neighbor tracing.
 
 



So... When does the Radial Sweep algorithm terminate?
Let's examine the behavior of the algorithm when the following stopping criteria are used...

Stopping Criterion 1
Let the Radial Sweep algorithm terminate when it visits the start pixel for a second time.
The following is an animated demonstration explaining why it would be a good idea to change that stopping criterion.
 
 




A point worth mentioning is that the performance of the Radial Sweep algorithm is identical to that of Moore-Neighbor tracing when this stopping criterion is used in both.

In the Square Tracing algorithm and Moore-Neighbor tracing, we found that using Jacob's stopping criterion (proposed by Jacob Eliosoff ) greatly improved both algorithms' performance.
Jacob's stopping criterion requires that the algorithm terminates when it visits the start pixel for a second time in the same direction it did the first time around.
Unfortunately, we won't be able to use Jacob's stopping criterion in the Radial Sweep algorithm. The reason for this is the fact that the Radial Sweep algorithm doesn't define the concept of the "direction" in which it enters a boundary pixel. In other words, it's not clear (nor is it trivial to define) the "direction" in which a boundary pixel is entered in the algorithm.
Therefore, we will suggest another stopping criterion which doesn't depend on the direction in which you enter a certain pixel and will improve the performance of the Radial Sweep algorithm...

Stopping Criterion 2
Assume that each time a new boundary pixel, Pi, is found by the algorithm, it is inserted in the sequence of boundary pixels as such: P1, P2, P3, ..., Pi ; and is declared as the current boundary pixel.
(Assume P1 is the start pixel).
This means that we know the previous boundary pixel, Pi-1, of every current boundary pixel, Pi .
(As for the start pixel, we will assume that P0 is an imaginary pixel -not equivalent to ANY pixel on the grid- which comes before the start pixel in the sequence of boundary pixels).

With the above assumptions in mind, we can define our stopping criterion:
The algorithm terminates when:
a) the current boundary pixel, Pi, has appeared previously as pixel Pj (where  j < i ) in the sequence of boundary pixels,
AND
b)  Pi-1 =  Pj-1 .

In other words, the algorithm terminates when it visits a boundary pixel, P, for a second time provided that the boundary pixel before P (in the sequence of boundary pixels) the second time around, is the same pixel which was before P when P was first visited.

If this stopping criterion was satisfied and the algorithm didn't terminate, the Radial Sweep algorithm will proceed to trace the same boundary for a second time.
The performance of the Radial Sweep algorithm using this stopping criterion is similar to the perfomance of Moore-Neighbor tracing using Jacob's stopping criterion.
 
 

All comments and questions are welcomed...
abeer.ghuneim@mail.mcgill.ca