Günter Rote:
Curve intersection by the Subdivision-Supercomposition Method
Technical report ACS-TR-361503-01,
May 2008, 12 pages.
Abstract
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.
Last update: May 14, 2008.