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

We can define the intersection problem as:

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

1. 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.

2. 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.

3. 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].

4. 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).

Figure 5.14: Linear approximation of curves in finding intersections: (a) approximation by linear segments, (b) approximation by polygon

Figure 5.15: Bounding wedges