[Cyan]<PreISLCedar>Stolfi>GBOld>GBB09A.tex!1

We will devote this chapter to what may seem at first glance a rather specialized topic, namely the concept of {\it polygonal tracing} and the {\it convolution} of such tracings. The ideas to be presented are both interesting in themselves and have a numerous applications in computational geometry. But our main reason for including them at such an early stage is that they lead naturally to some not-so-obvious but very powerful concepts, like the two-sided plane and geometric duality, that will form a recurrent theme throughout the rest of the course.

We will begin by a very practical problem that arises in connection with computer graphics and typesetting, that of two-dimensional {\it shape description}. Currently much of high-quality computer printing is being produced by {\it raster devices}, which consider a page as a two-dimensional array of tiny dots or {\it pixels}, each to be painted either black or white. When using such devices, the information to be printed must be ultimately encoded as a two-dimensional array of bits, each specifying the color of the corresponding pixel.
\fig{3.5} % the letter "a" with an enlarged portion showing pixels, and corresponding part of bitmap.

This encoding allows complete freedom in the placement of characters, in the choice of fonts and symbols, and in the intermixing of text and figures; but it is not without its drawbacks. One of the most serious is the sheer size of the bit arrays: a page printed in a raster device of typical resolution contains over five million pixels, and a high-quality printer may use more than fifty thousand pixels for each of the letters in this sentence. The handling of such raster images makes heavy demands on computer memory and time. Human interaction in the creation and manipulation of such huge arrays is also clearly problematic. A final problem is that images encoded in this format cannot be easily rotated, scaled, or otherwise geometrically tarsnformed.

These problems make it desirable to represent the images to be printed in some other form, and only convert it to raster format just before printing. It turns out that many of the images printed in typesetting systems consist of collections of solid black ``patches’’, each covering a large number of pixels but having a relatively simple boundary. That is the case, for example, with most text (composed of characters and symbols) and technical line drawings (consisting of lines of varied width and shape, dots, and other geometrical figures).

\mfig4 % the outline of an "a" showing separate arcs.
It is therefore natural to represent each of those patches by a description of its idealized outline, with the convention that its interior should be painted black. The outline can be described as a simple polygon, as an algebraic or parametric curve (e.g., a circle), or by any other suitable method. For example, a widely used technique is to represent the outline as a {\it cubic spline}: a collection of one or more arcs, each of them a parametric cubic of the form $p(t)=at↑3+bt↑2+c+d$, where $t$ ranges from $0$ to $1$ and the coefficients $a, b, c$ and $d$ are planar vectors. Many of the characters on this page you are now reading were encoded in exactly this way.
\endmfig

The widespread use of this {\it outline method} for representing the shape of patches attests to its effectiveness. The outline description of a figure is independent of the resolution of the printing device, and in most cases it is more compact than the corresponding bit array. Operations such as scaling, rotation, and slanting of characters can be performed by simply applying them to the outlines. There are many algorithms for converting outline descriptions into bit arrays; some of these are efficient enough for the conversion to be performed at the printing device itself, concurrently with the actual printing of the image.

Yet, the outline method is not without its problems. Many of the basic shapes occuring in text characters and in technical drawings are most naturally described as lines of constant width whose midline follows some specified trajectory. This is the figure that would be painted if we were to follow the given trajectory with a circular ``brush’’, i.e., one which leaves a circular spot of constant radius every time it is placed down on the plane. An example is the ‘‘sausage’’ of the illustration below. By using brushes with non-circular shapes one can obtain interesting calligraphic effects with very little effort, like the varying width of the strokes in the letter ``o’’ shown below.\fig4% A curved line drawn with circular brush; a letter "o" with elliptical slanted brush.
Some startling effects can be obtained by allowing the brush to rotate or change shape as it moves along the trajectory; however, these extra degrees of freedom make the manipulation of brush-and-trajectory descriptions more complex and time-consuming, and the machinery we would need for their theoretical treatment would lead us too far beyond our goals. Therefore, we will restrict our discussion to the case in which {\it the brush shape and orientation is the same at all points of the trajectory}.

Experience has shown that this {\it brush-trajectory} method for shape description is quite convenient to use; for example, the METAFONT system for font design developed by D. E. Knuth is entirely based upon it. Unfortunately, the brush-trajectory representation is much harder to convert into the bit array format. Consider this straightforward algorithm: we place the brush on successive positions along the trajectory, spaced closely enough that the motion appears continuous at the device’s resolution; and, for each position, we set to ``black’’ all bits of the array corresponding to pixels covered by the brush. This algorithm may set each bit a large number of times (about the diameter of the brush in pixels), and therefore is too inefficient for high-resolution devices. It is possible to improve its performance by ``painting’’ at each step only the pixels that were not covered by the preceding placement of the brush; but this usually requires each pixel to be set individually, so the improvement is not enough to make the algorithm competitive with those working with the outline representation.

Furthermore, there are many shapes that are better described by the outline method, and many algorithms that produce an outline representations from a bit arrays (like the ones that are obtained by digitizing an existing image from paper or film). These considerations suggest that we retain the brush-trajectory metaphor for the high-level description of shapes, but use the outline metaphor as the standard internal format, and as an intermediate step in the construction of the bit arrays.

The purpose of what has been said so far, and in particular of the last paragraph, is to motivate the problem we will be discussing for most of this chapter: that of converting a brush-trajectory description into the corresponding outline representation. The approach we will follow, and the main results we will see, are mostly due to Lyle Ramshaw. Most of this work is quite recent and in fact the particular development for polygonal trajectories we will follow is only a few weeks old. This may help explain, albeit not justify, the roughness of these notes.

\def\Thei{{1}} % Better use mnemonics, eg \TheSlope etc
\def\Theii{{2}}
\def\Theiii{{3}}
\def\Figi{F1} % Better use mnemonics, eg \FigBgCirXSmDisk
\def\Figii{F2}
\def\Figiii{F3}
\def\Figiv{F4}
\def\Figv{F5}
\def\Figvi{F6}
\def\Figvii{F7}
\def\Figviii{F8}
\def\Figix{F9}

To get a better understanding of the brush-trajectory metaphor, let’s begin with a simple example: a circular brush $\B$ of radius $r$ moving along a circular trajectory $\T$ of radius $R$, $R>r$.\figno(\Figi)3
When the center of the brush is at some point $t$ of $\T$, it will cover all points that are at distance $\leq r$ from $t$; the resulting shape will be a circular annulus, with inner radius $R-r$ and outer radius $R+r$. This set of points can also be expressed as
$$\B\oplus\T=\rset{b+t \relv b\in \B\,\, \and\,\, t\in \T}\eqno(1)$$
and it is clear that this formula holds for any brush $\B$ and trajectory $\T$, provided the brush does not rotate or change shape as it moves along the trajectory. Note that equation (1) is symmetrical in $\B$ and $\T$; that is, the resulting figure is the same, whether we move the brush along the trajectory or the trajectory along the brush!

For this observation to make sense, we must consider first what it means to move a figure along a ``trajectory’’ that contains interior points; we take this to mean simply that the brush is to be ``placed down’’ at all points of the trajectory, independently of whether they are on the boundary or in its interior. If in the previous example the trajectory were to be taken as the big circle {\it with its interior}, then the result would have been a full disk of radius $R+r$, with no hole.\figno(\Figii)5

\mfig4
\lemma{\Theii}{Every point on the boundary of $\B\oplus\T$ has the form $b+t$, where $b$ and $t$ are {\it boundary} points of $\B$ and $\T$.}
\proof{If $b$, say, is an interior point of $\B$, and $Sb̌\subset \B$ is an open ball centered at $b$, then for any point $t$ of the trajectory the point $b+t$ will be surrounded by the ball $Sb̌+t\subset \B\oplus\T$, i.e. $b+t$ will not be on the boundary of the resulting figure. A similar argument holds if $t$ is an interior point of $\T$.}
\endmfig

This lemma is quite interesting, for it establishes a connection between the brush-and-trajectory metaphor and the one based on outlines: it suggests that the outline of $\B\oplus\T$ can be computed from those of $\B$ and $\T$. Unfortunately, it holds only in one direction: even if $b$ and $t$ are boundary points of $\B$ and $\T$, $b+t$ may not be on the boundary of $\B\oplus\T$.

\mfig4
Let’s look again at the example of figure (\Figi), and try to follow some point $b$ on the boundary of the brush, e.g. at its very top, as the latter moves along the trajectory. It is clear that as long as the brush is moving vertically or diagonally, the ``trace’’ left by $b$ will be completely surrounded by the traces of the brush points in an immediate neighborhood of $b$. Therefore, the only points of the trace of $b$ that can be on the boundary of $\B\oplus\T$ are those corresponding to instants where the brush was moving horizontally.
\endmfig

By repeating the same argument for other points on the boundary of $\B$, we conclude that $b+t$ will be on the boundary of $\B\oplus\T$ only when the tangent to the trajectory at $t$ is parallel to the tangent to the brush at $b$. For each $t$, there will be exactly two antipodal points $b$ for which this happens; and these will give rise to exactly two points on the boundary of $\B\oplus\T$, one on each of its two circles. So, at least for the first example, we have got a complete characterization of the boundary points of $\B\oplus\T$: they are obtained by adding every boundary point of $\B$ with every boundary point of $\T$ subject to the condition that the tangents at these points have the same slope.

Now this is the kind of result that we are looking for. Clearly, the argument invoked to show that the tangents at $b$ and $t$ must be parallel does not use the fact that the curves in question were circles, so the same conclusion must be true for arbitrary curves. Let us then cede to the temptation, and adopt for our consideration\foot{1}{The original meaning of the word ‘‘theorem’’ was ‘‘something to be considered’’.} the following:

\theorem{{\Theiii} {\rm (Slope Theorem)}}{Let $\B$ and $\T$ be the figures defined by the outlines $B$ and $T$, and let $B\ast T$ be the set of all points $b+t$ such that $b\in B$, $t\in T$, and the tangents to $B$ and $T$ at those points are parallel. Then the figure described by $B\ast T$ is $\B\oplus\T$.}

As soon as we try it on other examples, our precious ``theorem’’ seems to come apart at every joint. Just to mention one problem, consider what happens in figure (\Figii), where the trajectory too is a full disk. The outlines $B$ and $T$ are the same as those of figure (\Figi), and therefore their convolution $B\ast T$ should also be the same. However, as we already remarked the resulting figure is now a solid disk of radius $R+r$, and the inner circle defining the annulus has mysteriously disappeared!

After contemplating this failure (and quite a few that are even worse), an honest mathematician would try to reformulate theorem {\Theiii} so as to exclude pathological cases and/or relate $B\ast T$ and $\B\oplus\T$ in some other way. However, if we were to follow this course of action, we would end up with a theorem weak and complicated to the point of being almost useless. Rather than doing so, or calling it quits and moving to some other topic, we will spend the next couple of sections ``fitting the shoe to the foot’’: i.e., trying to patch up the definitions of ``outline’’, ``tangent’’, ``interior’’, and ``convolution’’ so as to make theorem \Theiii, or something as near it as possible, true.

With regards to the example of figure (\Figii), we can claim that the problem is not with theorem \Theiii, but with the fact that the boundary of a figure does not contain enough information to distinguish a solid circle from an empty one. Therefore, we have to extend the definition of ``outline’’ so as to include this information.

\mfig5
One way of doing this was already used implicitly in the annulus of figure (\Figii). We considered the points within the inner circle as being ``outside’’ the annulus, in spite of they being entirely surrounded (twice) by its outline. This interpretation is compatible with the intuitive idea that whenever we cross any portion of the boundary, we move from the interior to the exterior or vice-versa. So, if we make the convention that points sufficiently far away are outside the figure, we can decide whether a point is inside or outside by counting how many times a ray coming out of that point crosses the outline, and checking whether this number is odd or even, respectively. If the point lies on the outline itself, it is of course neither inside nor outside, but on the boundary of the figure.
\endmfig

According to this idea, the outline of an empty circle should be that of an annulus of zero width, i.e., should consist of two copies of the same circle. Following the criterion above, we see that this outline has no interior points, only boundary ones. As before, the outline of a solid disk is just a single circle.

Even though this revised definition of outline can distinguish between solid and empty figures, it makes theorem {\Theiii} even less true. It still fails in the example of figure (\Figii): the convolution of the outlines still includes the inner circle $R-r$, corresponding to an annulus instead of the correct full disk of radius $R+r$. And now it fails also in example (\Figi): the double outline of $\T$ produces two copies each of the inner and outer circle in the convolution. The corresponding figure has {\it no} interior points, and is simply a pair of concentric, empty circles.\fig{3.3}

\mfig5
Fortunately, there is a second way of defining outlines and interiors, one that works much better and is almost as natural as that considered above. In this definition, each closed curve that is part of an outline $A$ is assigned a {\it direction of traversal}. The {\it winding number} of a point $p$ in the plane with respect to $A$, denoted by $w(p,A)$, is defined by taking a ray coming out of $p$, and counting how many times the ray crosses $A$. Unlike the previous definition, we count a crossing as $+1$ if $A$ is at that point directed counterclockwise, and $-1$ if it is directed clockwise (as seen from $p$).
\endmfig

It can be shown that the winding number depends only on $p$ and $A$, and not on the particular ray used. Intuitively, the winding number is just the signed total of the complete turns made by the outline around the point $p$ (with each turn counted as $+1$ or $-1$ depending on its direction). The exterior of the figure described by the outline is, by definition, the set of those points with zero winding number. Points with nonzero winding numbers are interior. If a point $p$ lies on the outline itself, its winding number is undefined; in that case $p$ may be either in the interior or on the boundary of the figure (topologically speaking), depending on whether it is adjacent or not to its exterior.

According to these ideas, we can describe a solid circle, like the brush $\B$ in example (\Figi), by a single copy of its boundary, traversed in the counterclockwise direction; the winding number then is 1 inside the figure and 0 outside. The annulus of example (\Figi) can be described by a counterclockwise circle of radius $R+r$ and a clockwise one of radius $R-r$. The empty circle $\T$ can be described as the limiting case of an annulus of zero width, i.e. by two copies of a circle of radius $R$, traversed in two opposite directions; this will give zero winding number everywhere, except on the circle itself. \fig4

Are those changes effective in making theorem {\Theiii} work, at least for the examples (\Figi) and (\Figii)? The answer is ``yes’’, provided we take a further precaution: when matching points to compute the convolution, we require that the tangents at those points be parallel {\it and the directions of traversal be the same.} We can think of the tangents as being oriented in the same direction as the curve at the point of tangency; therefore, our rule is that we match points where the {\it oriented} tangents are parallel, i.e., they are pointing in the same direction. This gives also a rule for assigning a direction of traversal to the convolution: the direction at point $b+t$ is that of the tangents to $B$ and $T$ at $b$ and $t$.

Let’s consider example (\Figii) under this new interpretation. Now, each point $b\in B$ can be matched with exactly one point $t\in T$; therefore, $B\ast T$ consists of a single circle of radius $R+r$, oriented counterclockwise. The figure described by this outline is the solid disk of the same radius, which is exactly $\B\oplus\T$.\fig4

In example (\Figi), recall that the outline of the trajectory consists of two copies of a circle of radius $R$, oriented in opposite directions. The counterclockwise copy will give rise\foot1{Wise are the clocks that turn counterclockwise and despise the counterclocks that do otherwise.} in the convolution to a similarly oriented circle of radius $R+r$, as in example (\Figii). The other copy will give a different result: a point $b$ of the brush will match the point $t$ of the trajectory that is in a position ``antipodal’’ to that of $b$. If the coordinates of $b$ are $(0, r)$, $t$ will be $(0, -R)$; if $b$ is $(r, 0)$, $t$ will be $(-R, 0)$, and so forth. The result will be a circle of radius $R-r$, and it will be oriented clockwise. One can readily check that these two circles are a correct outline representation of the annulus $\B\oplus\T$.

As a further test, let’s consider what happens in example (\Figi) if the radius of the brush is larger than that of the trajectory, i.e. if $r>R$. From equation (1) (and from the intuitive interpretation) we would expect the resulting figure to be a black disk of radius $r+R$, instead of an annulus.\figno(\Figiii)4
And that is precisely what we get from the convolution of the outlines: $B\ast T$ still consists of two circles, one of radius $r+R$ and the other of radius $r-R$; however, now both are oriented counterclockwise, so the winding number of a point within the inner one is 2, not 0. Therefore, the figure described by $B\ast T$ is the whole disk of radius $r+R$.