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
curves. The complexity depends on geometric quantities that represent
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
siblings in the subdivision tree. This approach addresses the common
of non-termination of the classical subdivision approach when the
coincides with a subdivision point, but it avoids the numerical
associated to alternative methods like a random shift of the parameter.
Last update: May 14, 2008.