Computing curve intersection by means of simultaneous iterations. A new algorithm is proposed for computing the intersection of two plane curves given in rational parametric form [the general solution steps are described by J. Hoschek and D. Lasser, Fundamentals of computer aided geometric design (1993; Zbl 0788.68002)]. This approach avoids symbolic manipulations and is completely numerical. It relies on the Ehrlich-Aberth iteration complemented with some computational tools like the properties of Sylvester and Bézout matrices, a stopping criterion based on the concept of pseudo-zero, an inclusion result and the choice of initial approximations based on the Newton polygon. The algorithm is implemented as a Fortran 95 module. From the numerical experiments performed with a wide set of test problems it shows a better robustness and stability with respect to the Manocha-Demmel approach based on eigenvalue computation. In fact, the algorithm provides better approximations in terms of the relative error and performs successfully in many critical cases where the eigenvalue computation fails.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element