Graphics Reference
In-Depth Information
Figure 18.2.
Generating the proximate intervals.
does not contain 0. Note also how the rectangles got divided. In the first iteration
shown in Figure 18.2(b) we subdivided in the x-direction. In the next iteration in
Figure 18.2(c) we subdivided in the y-direction, and so on.
When Algorithm 18.4.1 stops we will have the list S of rectangles of width less
than d, which cover the curve we are after. (In the general algorithm, the rectangles
of S are called the “proximate intervals”). Next, we will approximate the curve in each
rectangle A of S and then piece these local solutions together to get complete answer.
Two facts that we use here are, first, that the curve intersects A in a set that is the
graph of a function, in this case a function of x and, second, that it intersects the
boundary of A in a finite set of points. To find the latter intersection points we run
Algorithm 18.4.1 again to find the intersection of the curve with each edge of the rec-
tangles. This amounts to many runs of Algorithm 18.4.1 with two constraints. One is
(
) = 0
fxy
,
and the other is of the form
x
=
constant
or
y
=
constant.
Each run will give us a set of one-dimensional solution intervals. For example, doing
this for rectangle [1/4,1/2] ¥ [0,1/4] in Figure 18.2(e) we would get two vertical inter-
vals around the points p and q . In our case the pieces of curve that we generate in
each rectangle will be straight line segments. These are then scanned to connect them
together correctly. This finishes the example.
The general implicit curve approximation algorithm, Algorithm 18.5.1, comes
from [Snyd92]. We assume that the implicit curve is a one-dimensional manifold
without boundary. The consequence of the no boundary part that we use is that the
curve has no endpoints in the interior of any interval. Step 1 has already been
Search WWH ::




Custom Search