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

<p>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.</p>

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

<p>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:</p>

<ol>
<li><p>Case where we can "trivially" determine they do <em>not</em> intersect.</p></li>
<li><p>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)</p></li>
<li><p>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.</p></li>
<li><p>One or more of the curves are closed, e.g.. A0==An. To make life simpler, we'll subdivide such curves and start again.</p></li>
<li><p>There are an infinite number of points of intersection because each is subset of a "parent" Bezier and they overlap.</p></li>
<li><p>We aren't certain about the above cases and need further investigation</p></li>
</ol>

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

<h3>Case 1</h3>

<p>As you hint in your question, if the respective bounding boxes of the control points of <em>A</em> and <em>B</em>), 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 <em>A</em> and <em>B</em> don't intersect. (e.g. as shown in Wikipedia:)</p>

<p><a href="https://i.sstatic.net/u4AxW.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/u4AxW.png" alt="enter image description here"></a></p>

<h3>Case 2</h3>

<p>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:</p>

<p>Consider just curve A:</p>

<p><a href="https://i.sstatic.net/2An9z.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2An9z.png" alt="&quot;Fat line&quot; bounds of a Bezier"></a></p>

<p>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}$).</p>

<p>If we do the same with curve B we get the following (possible) case:
<a href="https://i.sstatic.net/dX6l0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/dX6l0.png" alt="enter image description here"></a></p>

<p>If we find $A_0$ and $A_n$ are outside opposite bounds of B <em>and</em> 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.</p>

<h3>Case 6</h3>

<p>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 <a href="https://computergraphics.stackexchange.com/questions/1895/how-should-i-fill-a-shape-consisting-of-bezier-cures-and-straight-lines/1899#1899">particularly trivial for quadratic Beziers</a>: </p>

<p>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.</p>

<h3>Case 3 &amp; 5</h3>

<p>This is where it becomes slightly more tedious.</p>

<p>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.<br>
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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-01-29T15:23:46.557Z
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.
joojaa
CC BY-SA 3.0
2016-01-29T15:44:00.973Z
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.
Simon F
CC BY-SA 3.0
2016-01-29T15:54:48.087Z
Yes but worst case scenario is that the other bezier starts at the other.
joojaa
CC BY-SA 3.0
2016-01-29T16:01:40.370Z
You mean, for example, _An_ == _B0_.  Do you define that as an intersection or not?
Simon F
CC BY-SA 3.0
2016-01-29T16:08:39.820Z
No more like B0 is At somewhere on the curve. Or even a just minimally crossing
joojaa
CC BY-SA 3.0
2016-01-29T16:54:07.137Z
Thanks a lot for the effort but I think the problem is the 6th case. If you propose to subdivide the curves further then this is not better than the overlapping bboxes because it could happen than after many subdivisions we still wont be able to answer "yes" or "no" definitely. But in ordered not to end up in infinite loop or floating point rounding errors we would have to stop at some point, basically guessing.
Ecir Hana
CC BY-SA 3.0
2016-02-01T08:50:38.250Z
Oops! I'd renumbered the initial list but not the solution cases!
Simon F
CC BY-SA 3.0
2016-01-29T14:04:26.613Z
2016-02-11T08:42:57.343Z
2016-02-11T08:42:57.343Z
Simon F
<p>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.</p>

<p>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</p>

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

<p>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 <a href="https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method">simplex method</a> or <a href="https://en.wikipedia.org/wiki/Conjugate_gradient_method">conjugate gradient descent</a>. 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.</p>

CC BY-SA 3.0
2016-01-31T19:51:51.933Z
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$?
Ecir Hana
CC BY-SA 3.0
2016-01-31T22:00:52.463Z
@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.
Nathan Reed
CC BY-SA 3.0
2016-02-01T13:30:27.697Z
@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.
Simon F
CC BY-SA 3.0
2016-01-31T18:20:40.643Z
2016-01-31T18:20:40.643Z
Nathan Reed
<p>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.</p>

<p>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.</p>

<p>The closest thing I found so far is the "<a href="http://dl.acm.org/citation.cfm?id=49188" rel="noreferrer">bounding wedge</a>" 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.</p>

CC BY-SA 3.0
2016-01-28T13:44:13.640Z
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.
joojaa
CC BY-SA 3.0
2016-01-28T14:05:10.967Z
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.
Dragonseel
CC BY-SA 3.0
2016-01-28T15:00:20.193Z
@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...
Ecir Hana
CC BY-SA 3.0
2016-01-28T15:25:10.350Z
@DanielMGessel Yes, see the edit above.
Ecir Hana
CC BY-SA 3.0
2016-01-29T09:41:23.870Z
Are the control points of your curves 2D or 3D (or, for that matter, greater)?
Simon F
CC BY-SA 3.0
2016-01-29T09:48:31.333Z
@SimonF 2D, sorry, see the edit.
Ecir Hana
CC BY-SA 3.0
2016-01-29T09:50:10.977Z
(Sigh. Caught by the comment edit timeout). You also say _"I also would like to use floating-point numbers in the implementation"_  I suspect that you might be limited on how "reliable" the test will be by whatever rounding goes on in floating point. For example, if there is a huge dynamic range in the control point values, you may lose too much precision.
Simon F
CC BY-SA 3.0
2016-01-29T09:55:32.927Z
@Eric: Being pedantic here:  By planar do you mean the _same_ plane?
Simon F
CC BY-SA 3.0
2016-01-29T09:58:28.413Z
@SimonF Yes, same plane.
Ecir Hana
CC BY-SA 3.0
2016-01-29T10:03:58.910Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/35018/discussion-between-simon-f-and-ecir-hana).
Simon F
<computational-geometry><bezier-curve><cad>
Reliable test for intersection of two Bezier curves
Ecir Hana
# Reliable test for intersection of two Bezier curves

(Asked by: username_0 on 2016-01-28)

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](http://dl.acm.org/citation.cfm?id=49188)" 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.

**Tags:** computational-geometry, bezier-curve, cad

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @username_2 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...  
> **username_0**: @DanielMGessel Yes, see the edit above.  
> **username_3**: Are the control points of your curves 2D or 3D (or, for that matter, greater)?  
> **username_0**: @username_3 2D, sorry, see the edit.  
> **username_3**: (Sigh. Caught by the comment edit timeout). You also say _"I also would like to use floating-point numbers in the implementation"_  I suspect that you might be limited on how "reliable" the test will be by whatever rounding goes on in floating point. For example, if there is a huge dynamic range in the control point values, you may lose too much precision.  
> **username_3**: @Eric: Being pedantic here:  By planar do you mean the _same_ plane?  
> **username_0**: @username_3 Yes, same plane.  
> **username_3**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/35018/discussion-between-username_3-f-and-username_0).  

---

## 2 answers

### Answer by username_3 on 2016-01-29. Score: 5

[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](https://i.sstatic.net/u4AxW.png)](https://i.sstatic.net/u4AxW.png)

### 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](https://i.sstatic.net/2An9z.png)](https://i.sstatic.net/2An9z.png)

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](https://i.sstatic.net/dX6l0.png)](https://i.sstatic.net/dX6l0.png)

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](https://computergraphics.stackexchange.com/questions/1895/how-should-i-fill-a-shape-consisting-of-bezier-cures-and-straight-lines/1899#1899):

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.

> **Comments:**
> **username_1**: 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.  
> **username_3**: 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.  
> **username_1**: Yes but worst case scenario is that the other bezier starts at the other.  
> **username_3**: You mean, for example, _An_ == _B0_.  Do you define that as an intersection or not?  
> **username_1**: No more like B0 is At somewhere on the curve. Or even a just minimally crossing  
> **username_0**: Thanks a lot for the effort but I think the problem is the 6th case. If you propose to subdivide the curves further then this is not better than the overlapping bboxes because it could happen than after many subdivisions we still wont be able to answer "yes" or "no" definitely. But in ordered not to end up in infinite loop or floating point rounding errors we would have to stop at some point, basically guessing.  
> **username_3**: Oops! I'd renumbered the initial list but not the solution cases!  

---

### Answer by username_4 on 2016-01-31. Score: 5

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](https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method) or [conjugate gradient descent](https://en.wikipedia.org/wiki/Conjugate_gradient_method). 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.

> **Comments:**
> **username_0**: 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$?  
> **username_4**: @username_0 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.  
> **username_3**: @username_4: I had considered that but, having spent much time writing code to find minima in texture compression formats, it all seemed a bit hideous.  

---

