Page 149 - Geometric Modeling and Algebraic Geometry

150 F. Cazals et al.
Note that homeomorphic approximation is weaker and our algorithm actually
gives isotopy. In addition, our construction allows to identify singularities of P to
a subset of vertices of G while controlling the error on the geometric positions. We
can also color edges of G with the color of the ridge curve it is isotopic to. Once
this topological sketch is given, one can easily compute a more accurate geometrical
picture.

8.3.4 Method outline

Taking the square free part of P, we can assume P is square free. We can also assume
P has no part which is a horizontal segment — parallel to the u-axis. Otherwise this
means that a whole horizontal line is a component of P. In other words, the content
of P wrt u is a polynomial in v and we can study this factor separately and divide P
by this factor. Eventually, to get the whole topology of the curve, one has to merge
the components.
Our algorithms consists of the following five stages:
1. Isolating study points. Study point are isolated in 2D with rational univariate
representations (RUR). Study points within a common fiber are identified.
2. Regularization of the study boxes. We know the number of branches of the
curve going through each study point. The boxes of study points are reduced so
as to be able to define the number of branches coming from the bottom and from
the top.
3. Computing regular points in study fibers. In each fiber of a study point, the u-
coordinates of intersection points with P other than study points are computed.
4. Adding intermediate rational fibers. Add rational fibers between study points
fibers and isolate the u-coordinates of intersection points with P.
5. Performing connections. This information is enough to perform the connec-
tions. Consider the cylinder between two consecutive fibers, the number of
branches connected from above the lower fiber is the same than the number
of branches connected from below the higher fiber. Hence there is only one way
to perform connections with non-intersecting straight segments.

8.3.5 Step 1. Isolating study points
The method to identify these study points is to compute a RUR of the system defining
them. More precisely, we sequentially solve the following systems:
1. The system S u from which the sets S 1R and S 3R are distinguished by evaluating
the sign of δ(P 3 ).
2. The system S p for purple points.
3. The system S c for critical points.
4. The system S b for border points, that is intersections of P with the left and
right sides of the box D. Solving this system together with one of the previous
identifies border points which are also singular or critical.