Graphics Reference
In-Depth Information
The Implicit Curve Approximation Algorithm:
Assume given a curve
C
in the plane defined by f (x,y) = 0, where f :
R
2
Æ
R
.
We assume further that
(1)
C
is a
(2)
C
meets vertical or horizontal lines transversally, that is, the intersection consists
of a finite set of points, possibly empty. Actually, this can be weakened and need
only hold for the boundary segments of the proximate intervals in Step 1 below.
one-dimensional manifold without boundary.
Inputs:
An interval A that contains the part of the curve
C
we are after.
An inclusion function F for f defined on intervals in I(A).
An approximation acceptance inclusion function H defined on I(A) which
specifies whether an interval is small enough so that the part of the curve
it contains can be classified appropriately topologically.
Output:
A linked list of polygonal curves that approximate
C
on A.
Step 1:
Use Algorithm 18.4.1 to compute the list of intervals in I(A) which satisfy H
and cover the curve.
Step 2:
Check each proximate interval for global paramet rizability. Any interval that
does not satisfy this property is subdivided further until it does.
Step 3:
Use Algorithm 18.4.1 again to find the intersection of
C
with the boundaries of
all the proximate intervals.
Step 4:
Ensure that the intersection intervals we get from Step 3 are disjoint in the global
paramet rization coordinate.
Step 5:
Determine the connection of the boundary intersections in each proximate interval.
An interval B does not contain any or just one intersection points can be
discarded. If B contains more than one intersection point, sort them in the global
paramet rization coordinate. For each successive pair of intersections in this
order use Algorithm 18.4.1 to see if the curve
C
intersects the line that is the
perpendicular bisector of the segment connecting the two points. If it does, then
the two intersections are connected in a list. In the end, each proximate interval
will have a list of point lists associated to it that correspond to the components
of the intersection of the curve with that interval.
Step 6:
Find the set of disjoint polygonal curve pieces that correspond to the different
components of
C
on A. Make sure that the points of all these curves are ordered
in a globally consistent manner.
e
e
which that
e
Algorithm 18.5.1.
The implicit curve approximation algorithm.
explained in Example 18.5.1. The intervals one gets are called the
proximate intervals
.
For Step 2, recall that, given an equation of the form f(x,y) = 0, the implicit function
theorem (Theorem 4.4.7 in [AgoM05]) asserts conditions under which one can solve
for one variable in terms of the other in the neighborhood of a solution. Being able
