This paper treats the problem of how one can best compute the points of intersection of two planar rational curves. Three different algorithms are compared: the well known Bezier subdivision algorithm, a subdivision algorithm based on interval arithmetic, and the implicitization approach. Implementation considerations are discussed, with particular focus on how to make the implicitization method robust and fast. Report is made on a test in which the algorithms solved hundreds of randomly generated problems to eight digits of accuracy. The implicitization algorithm was faster than the others by a factor of five for degree two curves; by a factor of four for cubic curves," by a factor of three for quartic curves; and the interval method was faster for quintic curves by a factor of two.
geometry, rational curves, curve intersection
Several algorithms have been proposed recently for computing the points of intersection of two planar rational curves. This paper focuses on three such algorithms, presenting implementation techniques and comparing their relative performance. The first algorithm is the well known Bezier subdivision algorithm described by Lane and Riesenfeld I and we shall refer to it as Bez_Sub. The second is a subdivision algorithm due to Koparkar and Mudur 2, based on interval arithmetic, which we shall refer to as Int_Sub, and the third is an algebraic approach derived by Sederberg 3A, which we dub Implic.
The second section of this paper describes each of these algorithms. The third section discusses implementation, and the fourth section presents the results of a performance test.
This paper is worded in terms of rational Bezier curves, and the reader is assumed to have a basic knowledge thereof. An excellent tutorial on the subject is given in Bohm et al s . These algorithms can apply to B-spline curves if they are first converted to a series of Bezier curves.