Günter Rote:

Curve intersection by the Subdivision-Supercomposition Method

Technical report ACS-TR-361503-01, May 2008, 12 pages.


We present a subdivision algorithm for computing the intersection of spline curves. The complexity depends on geometric quantities that represent the hardness of the computation in a natural way, like the angle of the intersection. The main idea is the application of the super-composition technique, which considers unions of adjacent parameter intervals that are not siblings in the subdivision tree. This approach addresses the common difficulty of non-termination of the classical subdivision approach when the intersection coincides with a subdivision point, but it avoids the numerical overhead associated to alternative methods like a random shift of the parameter.

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: May 14, 2008.