5.4.2.4 Implicitization

As we have discussed in Sect. 5.4.1, point/implicit curve intersection problem is conceptually very simple. Therefore it is natural to consider conversion of the curve equation from a parametric form to an implicit form. Sederberg et al. [371,372,374,378,380] used implicitization, which originates in classical algebraic geometry [437,217,2,413], to compute such intersections.

Let us consider two polynomial equations , of degree and respectively as follows:

where and . Or equivalently

Now we form the following matrix by generating auxiliary equations by multiplying (5.26) and (5.27) by appropriate monomials as follows:

where all blanks correspond to zeros. The resultant of the two polynomials (5.26), (5.27), which is denoted by , is the determinant of the above matrix [217]. The vanishing of the resultant, i.e. is a necessary and sufficient condition for the polynomials (5.26) and (5.27) to have a common root. In other words, all , values that satisfy lie on the parametric curve, and hence is the implicit form of the parametric equation , .

Evidently, has degree in , respectively. Furthermore, McKay and Wang [266] proved that the leading form , which consists of the terms with , is equal to , where is the greatest common divisor of and . Therefore, if , has the form , and thus the highest total degree of the implicit algebraic representation of the curve is . An alternate geometric way of visualizing this is to consider the maximum number of intersections of a straight line , with the planar parametric curve , which upon substitution into the (linear) equation of the line leads to the conclusion that the highest total degree is . Note that the curve , can be represented implicitly using resultants as . The exponent of arises in order to reflect the complex roots for the parameter of or for given or .

Once we have the implicit form, we check if in an exact arithmetic context to verify if is on the initial curve. Resultants can be computed exactly (in rational arithmetic) in symbolic manipulation programs such as MATHEMATICA [446], MAPLE [51], but the evaluation procedure tends to be slow for high degree cases.

Finally we may need to determine the corresponding parameter value on the parametric curve at the point . This process is called inversion. We set and in (5.28) and discard any row of the resultant matrix and solve for any of the ratio of ( ) which gives the parameter value [374]. The implicitization and inversion methods are efficient for low degree polynomials but there are no guarantees on accuracy and robustness, if these methods are implemented in floating point arithmetic. Subdivision methods are preferable for higher degrees, and as we have seen in Chap. 4 when coupled with rounded interval arithmetic, they become robust and accurate. Intersection of points and 3-D polynomial curves via implicitization involves a process of projection on -plane and finding by inversion and verification of .