5.6.1.1 2-D planar case

We start with an intersection problem of a planar RPP curve and an implicit algebraic curve which is defined as:

Let us denote the degree of planar RPP curve by and the total degree of the implicit algebraic curve by . Furthermore we describe the implicit curve by

Substitution of and into the implicit form and multiplication of leads to a polynomial of degree up to

Therefore the problem of intersection is equivalent to finding the real roots of in . The most usual form of is the power basis. The coefficients can be evaluated symbolically by substitution and collection of terms. This can be readily done in a standard symbolic manipulation program such as MATHEMATICA [446], MAPLE [51] etc. This can be followed by numerical evaluation of the coefficients ideally in exact rational arithmetic. Symbolic manipulation programs are oriented to processing rational numbers exactly.

Example 5.6.1 Let the algebraic curve be an ellipse , and the parametric curve be a cubic Bézier curve with control points (0,1), (1, -4), (2,1) and (2,0) as illustrated in Fig. 5.12. The ellipse and Bézier curve are chosen to be tangent at (2,0).

Using a symbolic manipulation program and simplifying, we get in exact arithmetic mode:

Next we find the real roots of in using factoring over the integers, which leads to

where

Using a standard numerical solver for polynomials in floating point such as [134,135], we obtain the following numbers as solutions of

Alternately solving using the same routine leads to the following six complex and real roots

where , and is the imaginary unit.

Figure 5.12: Intersection of ellipse and cubic Bézier curve

Notice the sensitivity to errors for the 6 degree polynomial, especially for the double root . In floating point arithmetic, such roots may split into conjugate complex numbers. Obviously, complex roots are not usable as we require only the real intersection points. The consequence is lost roots, which implies an erroneous solution of the intersection problem.

An alternate basis for the representation of is the Bernstein basis, which leads to better stability for its real roots under perturbations of its coefficients than the power form [105] as we discussed in Sect. 1.3.3.

Setting in the above example of the ellipse and cubic Bézier curve, we have = 0, = -20, = , = , = , = 0, and = 0. Here the conversion is done exactly using rational arithmetic (given that the conversion itself is not in general numerically well conditioned [106]). By the use of linear precision property

we can construct a graph

which is now a degree Bézier curve as shown in Fig. 5.13. Now we can apply the IPP method introduced in Chap. 4 which converts the problem of finding roots of polynomials into a problem of finding the intersection of the Bézier curve with the parameter axis.

Figure 5.13: Intersection of a Bézier curve/straight line

Notice that in our example which implies that is a root. Also implies that is a double root.