Reliable test for intersection of two Bezier curves

Question

Is there a test which reliably decides whether two Bezier curves intersect or not?

I don't need to know how many intersections there are or at what parameters they appear at. I just would like to know if there is some intersection or not. By "reliably" I mean that there should be no false positives or false negatives: for instance, checking if the bounding boxes overlap is not "sufficient" as they might overlap even if there is no curve intersection.

Alternatively, if it helps, I would be also interested in a weaker test: it would answer "yes" if the curves intersect (one or more times). If the curves don't intersect this test's answer would be "yes" or "no", meaning that false positives would be allowed.

An example of what I'm after: according to Rational polynomial parametric/rational polynomial parametric curve intersection, "If the two wedges do not overlap, the curves cannot intersect more than once". This would answer my question, were it "more than zero" instead.

Answer 1

I'd test the convex hulls of the control points for overlap.

• If there is no overlap, then the answer is definitely "no" because the curves stay inside the convex hull.
• If there is overlap in such a way that the endpoints of the first curve are not inside the convex hull for the second curve, and vice versa, and the direct connections of the endpoints intersect, then the answer is "yes"
• Otherwise (i.e., there is overlap, but one curve might sneak around the other) the asnwer is "maybe" and we can recurse: Subdivide both of the curves (or just one? But which one?) and check each combination. This looks like it might become exponential but in most real life situations only one of the four sub-pairs should ba a "maybe" case again.

It may be advisable to stop recursion at a certain depth (and answer "yes"). Otherwise, touching curves might cause "stack overflow". Also, if you limit yourself to a fixed number (three, say) of recursions, you can both be sure to bound the complexity while at the same time producing false positives at most (and presumably only in rare situations. The heuristic is that after a few subdivisions, the subcurves are so little bent (i.e., the convex hulls are very "thin" compared to their lengths) that we may expect either a "no" or a clear "yes".

Answer 2

I think you're asking for something impossible, so you'll have to compromise somewhere.

I assume that you will implement the algorithm using floating point arithmetic, and that's one of the big sources of trouble. Two curves can be arbitrarily close without intersecting, so you have to define what you mean by "intersection" in floating point arithmetic. I suggest that a reasonable definition of an intersection is a pair of points, one lying on each curve, whose distance apart is less than some small number $\varepsilon$. And, of course, $\varepsilon$ will need to be an order of magitude (or two) bigger than the error $\delta$ involved in calculating points on the curve. Using double precision arithmetic, and assuming your curves are of unit size, $\delta$ will be around $10^{-14}$, so $\varepsilon$ will need to be around $10^{-12}$, say.

Depending on your application, it might make sense to use a much larger value for $\varepsilon$. For engineering or manufacturing, $10^{-7}$ is probably good enough, and for graphics $10^{-5}$ might suffice. Once you have chosen $\varepsilon$, you know when you can stop the various subdivision processes that compute intersections.

There is a pretty thorough analysis of intersection algorithms in Tom Sederberg's notes. But most of the techniques are based on bounding volume tests and subdivision, which you don't seem to like.

In this chapter of his notes, and in a paper in Computer-Aided Design Volume 18, Issue 1, January–February 1986, Pages 58–63, Sederberg discusses intersection calculation by implicitization. This is much faster than subdivision-based techniques for curves of low degree (less that 5 or so). The idea is to obtain an implicit equation $F(x,y)=0$ for one of the curves. Then if the other curve has parametric equation $C(t)$, the intersection points are the roots of the polynomial equation $\phi(t) = F(C(t))=0$. In floating point arithmetic, $\phi(t)$ will never be zero, of course, so you still have to deal with the $\varepsilon$ problem I outlined above. And, in fact, in this scenario, the $\varepsilon$ problem is harder because the value of $\phi$ has no clear geometric meaning, so it's hard to decide how small a value indicates an "intersection".