5.6.2 Rational polynomial parametric/rational polynomial parametric curve intersection (Case D1)

(5.63) | |||

Setting leads to 3 nonlinear polynomial equations with 2 unknowns , (overconstrained system). There are several approaches to solve this intersection problem.

- The bounding
box and subdivision method followed by minimization that we
described in Sect. 5.4.2 can be applied to this
problem. If two bounding boxes intersect, and they are
of finite size, we can find roots using linear approximation.
However, in the presence of tangential intersection the following
cases may happen. The boxes intersect but the linear approximations
do not, and the curves intersect as illustrated in Fig.
5.14 (a) for planar curves. Similar behavior is observed
in (b) where polygon is used as the curve approximation.
*Hodographs*indicate the range of tangent directions of a Bézier curve. Sederberg and Meyers [379] construct a*bounding wedge*, which is a bounding angular sector of a hodograph, containing all tangent vectors of the given Bézier curve (see shaded triangle in Fig. 5.15). The bounding wedges are useful in predicting the number of intersection points of two curves. We first translate the bounding wedges of the two Bézier curves so that their vertices are coincident. If the two wedges do not overlap, the curves cannot intersect more than once. This is a sufficient condition but not a necessary condition. Figure 5.15 (a) shows non-overlapping wedges, while (b) shows overlapping wedges. In both figures, hodographs together with their control polygons for each Bézier curve are superposed on the corresponding wedges.If we combine the bounding box subdivision technique with the bounding wedge technique, we are able to locate the intersection points more effectively. For a precisely tangential intersection, this method would lead to infinite subdivision steps.

- Another
possible approach is to choose 2 equations to solve for
,
,
and then substitute the results into the third equation for
verification.
We can implicitize
and
to obtain
followed by the substitution of
and
into
yielding
. Then solve it for real roots in
and use the inversion algorithm to find
. Finally we
verify the solution by checking if
becomes
equal to
. This method needs to be
implemented in rational arithmetic for robustness.
- Hawat and Piegl [156] studied the application of a
*genetic algorithm*to the curve/curve intersection problems. First a number of points are selected on each curve in a random manner, then a pair of points from each curve are coupled. Finally the genetic algorithm is applied to create generations of couples that minimize the distance between them. The probabilistic nature of genetic algorithms is discussed in [267]. - Solve directly the overconstrained 3-equations with 2-unknowns system using the IPP algorithm described in Chap. 4. If the parametric curves are in integral/rational B-spline form, the first step is to subdivide the integral/rational B-spline curve into a number of integral/rational Bézier curves. This method guarantees a robust solution (no missing roots).