2

I have two cubic bezier curve,

curve 1:- 1st anchor-point(a1x,a1y), 1st control-point(c1x,c1y), 2nd control-point(c2x,c2y), 2nd anchor-point(a2x,a2y)

curve 2:- 1st anchor-point(a3x,a3y), 1st control-point(c2x,c3y), 2nd control-point(c4x,c4y), 2nd anchor-point(a4x,a4y)

Now I want to find the intersection points between these two bezier curve;

How to do it? Any reference document with algorithm will help me;

Scarecrow
  • 4,057
  • 3
  • 30
  • 56
  • Does "Sylvester matrix" mean anything to you? If you want to dig deeper into Math then read this: https://mat.polsl.pl/sjpam/zeszyty/z6/Silesian_J_Pure_Appl_Math_v6_i1_str_155-176.pdf – Manuela Jan 02 '20 at 06:47

4 Answers4

9

There are two main methods to find a Bezier curve intersection:

  1. Recursive subdivision exploits the convex hull property of Bezier curves and usually checks the intersection of bounding boxes of its curve segments.

Code from book Graphics Gems IV with some textual description

  1. Numerical solution of the system of two cubic equations. It leads to a polynomial equation of the 9th order and may have 9 real roots (case of two S-shaped curves). Note that the solution is numerically unstable.

JS code and interactive demonstration And I think C++ code might be in Geometric Tools WildMagic library.

Theraot
  • 31,890
  • 5
  • 57
  • 86
MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks for the code. What does "numerically unstable" mean? – Agamemnus Dec 27 '14 at 20:25
  • 5
    "numerically unstable" means that solver sometimes might find false roots and miss true ones (due to limited precision of float numbers and accumulation of numerical errors) – MBo Dec 28 '14 at 08:39
1

A cubic bezier curve is just a cubic polynomial equation. If you want to find when two cubics intersect, then you want to find when the two cubics are equal, i.e.

a1x3 + b1x2 + c1x + d1 = a2x3 + b2x2 + c2x + d2

Then that's the same as finding the roots of the cubic equation

(a1 - a2)x3 + (b1 - b2)x2 + (c1 - c2)x + (d1 - d2) = 0

Cubic equations, like that can be solved analytically, see e.g. Cardano's method. Alternatively, a method such as Newton–Raphson can be used to iterate to the solution. Beware, though, cubics can have up to 3 points where they're equal to zero.

Stochastically
  • 7,616
  • 5
  • 30
  • 58
  • 4
    It is necessary to solve two equations simultaneously: for x and y coordinates. And Bezout' theorem claims that there are up to 9 roots (intersection points). – MBo Apr 17 '13 at 11:05
  • 3
    The left and right unknown parameters are not the same. So you can't make a cubic polynomial equation out of it. – 0kcats Jul 27 '16 at 22:54
  • ax1 s^3 + bx1 s^2 + cx1 s + dx1 = ax2 t^3 + bx2 t^2 + cx2 t + dx2 and ay1 s^3 + by1 s^2 + cy1 s + dy1 = ay2 t^3 + by2 t^2 + cy2 t + dy2 – 0kcats Aug 08 '16 at 19:24
0

My suggestion may be not very efficient but it can work. You can try comparing distances between points of two curves, and the closest two points would be your cross "points".

0

If some approximation is permitted, you could convert the bezier curves into lots of small straight lines and then compute intersections between pairs of them generated from both curves. This is a much easier problem to solve as you only have to solve linear equations and may provide sufficient performance and accuracy for your use case.

William Jarvis
  • 347
  • 3
  • 6