leads to 3
nonlinear polynomial equations with 2 unknowns
(overconstrained system). There are several approaches to solve this
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  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
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.
possible approach is to choose 2 equations to solve for
and then substitute the results into the third equation for
We can implicitize
followed by the substitution of
. Then solve it for real roots in
and use the inversion algorithm to find
. Finally we
verify the solution by checking if
. This method needs to be
implemented in rational arithmetic for robustness.
Hawat and Piegl  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 .
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).
Linear approximation of curves in finding intersections:
(a) approximation by linear segments, (b) approximation by polygon
Next: 5.6.3 Rational polynomial parametric/procedural
Up: 5.6 Curve/curve intersection
Previous: 220.127.116.11 3-D space curve