9
$\begingroup$

How to reliably find out whether two planar Bezier curves intersect? By "reliably" I mean the test will answer "yes" only when the curves intersect, and "no" only when they don't intersect. I don't need to know what parameters the intersection was found at. I also would like to use floating-point numbers in the implementation.

I found several answers on StackOverflow which use the curves' bounding-boxes for the test: this is not what I'm after as such test may report intersection even if the curves don't intersect.

The closest thing I found so far is the "bounding wedge" by Sederberg and Meyers but it "only" distinguishes between at-most-one and two-or-more intersection, whereas I want to know if there is at-most-zero and one-or-more intersections.

$\endgroup$
  • $\begingroup$ Im not sure it exists as such, determining wetehr or theres a possibility for 0-1 or 2 or more is pretty trivial but the formulation does not really make it ieasy to make sure its 0 or 1 without actually checking. $\endgroup$ – joojaa Jan 28 '16 at 13:44
  • $\begingroup$ What is the runtime requirements? An solution that should be able to produce pretty accurate results would be to approximate both curves by a large number of short straight segments and then intersecting them in a pairwise fashion. But that costs much time and memory. $\endgroup$ – Dragonseel Jan 28 '16 at 14:05
  • $\begingroup$ @Dragonseel Well, I would be happy for any solution, really, but since you asked O(1) would be nice. But approximating the curves with line segments leads to the same problems as the test for bounding box overlap... $\endgroup$ – Ecir Hana Jan 28 '16 at 15:00
  • $\begingroup$ Interesting problem. I don't think there's an easy answer but I'd like to be wrong. Do you have a link for the Sederberg and Meyers paper? $\endgroup$ – Daniel M Gessel Jan 28 '16 at 15:21
  • $\begingroup$ @DanielMGessel Yes, see the edit above. $\endgroup$ – Ecir Hana Jan 28 '16 at 15:25
6
$\begingroup$

An alternative way to formulate the problem is to define a function that gives the distance between points on the two curves, as a function of the curves' parameters. Then attempt to find the global minimum of this function. If the curves intersect, the minimum will be zero; otherwise the minimum will be some positive distance.

To be explicit, given a pair of 2D curves defined by $c_1, c_2 : [0, 1] \to \mathbb{R}^2$, define the distance-squared as

$$ f(u,v) : [0,1]^2 \to \mathbb{R}_{\geq 0} \equiv \bigl|c_2(v) - c_1(u)\bigr|^2 $$

For cubic curves, the function $f$ is then a sixth-degree polynomial in two variables. You can then apply numerical optimization techniques such as the simplex method or conjugate gradient descent. Unfortunately the function can have several local minima (it's not convex), so optimization isn't easy. There may well be more specialized optimization methods available for polynomials, but this isn't an area of expertise for me.

$\endgroup$
  • $\begingroup$ Why is it 6th degree polynomial, and not 3rd, if we are talking about cubic Beziers? And the two methods you linked to, are they amenable to finding solutions only in $[0,1]^2$, as opposed to whole $R^2$? $\endgroup$ – Ecir Hana Jan 31 '16 at 19:51
  • 1
    $\begingroup$ @EcirHana It's 6th degree because it's the squared distance. (You could square-root it, but then it's no longer polynomial, and will be non-smooth at the zeroes.) Note that the $[0,1]$ is the parameter space, not the space the splines live in, i.e. these are splines with endpoints. In any case, the methods will work fine in $\mathbb{R}^2$, but they only "travel downhill" from an initial guess and find a local minimum; something more is needed to examine the whole parameter region and find the global minimum. Constraining the parameter space is probably helpful there. $\endgroup$ – Nathan Reed Jan 31 '16 at 22:00
  • 1
    $\begingroup$ Nathan - nice formulation! I'm rusty, but: I think you can divide each bezier curve into at most 5 segments, by where $x$ or $y$ change direction in the curve. $x$, as a function of $c_i$ changes direction at most twice (roots of the derivative) breaking the curve into 3 segments, 2 of which may be divided again by changes in direction of $y$. Now you have, not straight segments, but segments that "don't curve too much". I think if you start your search at 25 points, chosen by segment pairs, you could be always find the global minima, but I can't quite see how to prove (or disprove) it. $\endgroup$ – Daniel M Gessel Feb 1 '16 at 3:47
  • $\begingroup$ @Nathan: I had considered that but, having spent much time writing code to find minima in texture compression formats, it all seemed a bit hideous. $\endgroup$ – Simon F Feb 1 '16 at 13:30
5
$\begingroup$

[Disclaimer: I think the following should work but have not actually coded it myself]

I couldn't think of a "trivial" method of producing a yes/no answer but the following would be a reasonable approach to a practical solution to the question.

Let's assume our curves are A(s) and B(t) with control points {A0, A1..An} and {B0,..Bm} respectively.

It seems to me that, given a pair of 2D Beziers for which we wish to determine do or don't intersect, there are six cases to consider:

  1. Case where we can "trivially" determine they do not intersect.

  2. Case where they intersect a finite number of times and we can "easily" determine they definitely intersect at least once (but we don't actually care where those intersections occur)

  3. One of the Beziers is degenerate, i.e. a point (which will occur if all the control points are identical). We can assume we've already handled the case where both are points.

  4. One or more of the curves are closed, e.g.. A0==An. To make life simpler, we'll subdivide such curves and start again.

  5. There are an infinite number of points of intersection because each is subset of a "parent" Bezier and they overlap.

  6. We aren't certain about the above cases and need further investigation

For the moment we'll ignore 3 and 4, but come back to them later.

Case 1

As you hint in your question, if the respective bounding boxes of the control points of A and B), don't intersect, then the curves can't intersect. Obviously this is a quick reject test but it's overly conservative. As you probably know, with a Bezier curve, the convex hull of its control points forms a (tighter) bound on the curve. We can thus use the separating axis technique to decide if the hulls of A and B don't intersect. (e.g. as shown in Wikipedia:)

enter image description here

Case 2

If the case 1 test fails, you could then check for the "trivial" existence of an intersection. Now there are probably better ways to do this, but the following, relatively cheap, approach occurred to me:

Consider just curve A:

"Fat line" bounds of a Bezier

We know the curve starts at $A_0$, terminates at $A_n$, and will lie inside the convex hull. For simplicity let us compute the direction of the line segment $\overline{A_0A_n} $ and the compute the bounds on either side (i.e. take dot products of the remaining control points against the perpendicular to $\overline{A_0A_n}$).

If we do the same with curve B we get the following (possible) case: enter image description here

If we find $A_0$ and $A_n$ are outside opposite bounds of B and that $B_0$ and $B_m$ are on the outsides of the bounds of A, then, by the continuity of Beziers, there must be at least one intersection.

Case 6

If we can't immediately show either of the above cases, then split each of the Beziers into two "halves", i.e. $A^1, A^2, B^1, B^2$. This is relatively straightforward (left as an exercise to the reader) but is particularly trivial for quadratic Beziers:

Recursively compare the 4 combinations: $(A^1,B^1), (A^2, B^1)...(A^2, B^2)$. Clearly if all pass case 1, there is no intersection. If any fail 1, then continue with the rest of the tests with that reduced subset.

Case 3 & 5

This is where it becomes slightly more tedious.

If "case 3" gets past the "case 1" test, it seems to me that you need to solve for an actual intersection. Given that there is a simple process to map the N control points of a Bezier, A(s), to the N-1 points of the Bezier, A'(s), representing its 1st derivative then (provided care is taken for the relatively rare, so-called "degenerate" situations where the 1st derivative does to zero), then Newton iteration (on one dimension) could be used to find potential solutions.
Note also that, since the control points of A'(s) are a bound on the derivative values, there is the potential to do early elimination of some cases.

Case 5 seems relatively unlikely, so perhaps only if after a few recursions there is no conclusive proof, one could try each end point of A against curve B and vice versa. This would only give a proof of intersection - not a proof of non-intersection.

$\endgroup$
  • $\begingroup$ Yes, but im personally more interested in the case where about the case where the Bm and/or B0 are Both within the volume of A's max and min bound but does not pierce it then you need to subdivide and in worst case scenario calculate the intersection point. Better ways would be to use the minimum bounding box also known as thick line approximation. $\endgroup$ – joojaa Jan 29 '16 at 15:23
  • $\begingroup$ Given that, with every binary subdivision, the difference between the curve and the segment connecting the end points goes down by reasonable factor (and, off the top of my head, I think it might have been 4x for quadratics) surely the bounds are going to converge to a "thin" ribbon fairly rapidly. $\endgroup$ – Simon F Jan 29 '16 at 15:44
  • $\begingroup$ Yes but worst case scenario is that the other bezier starts at the other. $\endgroup$ – joojaa Jan 29 '16 at 15:54
  • $\begingroup$ You mean, for example, An == B0. Do you define that as an intersection or not? $\endgroup$ – Simon F Jan 29 '16 at 16:01
  • $\begingroup$ No more like B0 is At somewhere on the curve. Or even a just minimally crossing $\endgroup$ – joojaa Jan 29 '16 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.