Algorithms for intersecting parametric and algebraic curves I

The problem of computing the intersection of parametric and algebraic curves arises in many applications of computer graphics and geometric and solid modeling. Previous algorithms are based on techniques from elimination theory or subdivision and iteration. The former is, however, restricted to low-degree curves. This is mainly due to issues of efficiency and numerical stability. In this article we use elimination theory and express the resultant of the equations of intersection as matrix determinant. The matrix itself rather than its symbolic determinant, a polynomial, is used as the representation. The problem of intersection is reduced to that of computing the eigenvalues and eigenvectors of a numeric matrix. The main advantage of this approach lies in its efficency and robustness . Moreover, the numerical accuracy of these operations is well understood. For almost all cases we are able to compute accurate answers in 64-bit IEEE floating-point arithmetic.