Is task to find intersections of a line and a cubic Bezier curve really so hard?

I wrote formulas for parametric Bezier curves of different orders

Curve1[t_, p1_List, p2_List] := (1 - t) p1 + t p2;
Curve2[t_, p1_List, p2_List, p3_List] := (1 - t)^2 p1 +
2  t (1 - t) p2 + t^2 p3;
Curve3[t_, p1_List, p2_List, p3_List, p4_List] := (1 - t)^3 p1 +
3  t (1 - t)^2 p2 + 3 t^2 (1 - t)  p3 + t^3 p4;


Then I made equations and ran solver

equ = Curve3[t, {x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}] ==
Curve1[u, {v1, w1}, {v2, w2}]
equ = (equ[[1, 1]] == equ[[2, 1]]) && (equ[[1, 2]] == equ[[2, 2]])
sol = Solve[equ, {t, u}];


(output of first two statements)

$$\left\{t^3 \text{x4}+3 t^2 (1-t) \text{x3}+(1-t)^3 \text{x1}+3 t (1-t)^2 \text{x2},t^3 \text{y4}+3 t^2 (1-t) \text{y3}+(1-t)^3 \text{y1}+3 t (1-t)^2 \text{y2}\right\}=\{(1-u) \text{v1}+u \text{v2},(1-u) \text{w1}+u \text{w2}\}$$

$$t^3 \text{x4}+3 t^2 (1-t) \text{x3}+(1-t)^3 \text{x1}+3 t (1-t)^2 \text{x2}=(1-u) \text{v1}+u \text{v2}\land t^3 \text{y4}+3 t^2 (1-t) \text{y3}+(1-t)^3 \text{y1}+3 t (1-t)^2 \text{y2}=(1-u) \text{w1}+u \text{w2}$$

Unfortunately, Solver thinks forever.

Is it really so hard mathematical problem? Shouldn't it be just cubic equation-like problem?

• Yes, it is hard. Try GroebnerBasis[equ, {t, u}] Jan 13 at 14:09
• It generated something trmendous...
– Dims
Jan 13 at 14:13
• But why is it that more complex, that just cubic equation? Can't we just rotate coordinates so that OX is collinear to linear spline and just solve cubic equation?
– Dims
Jan 13 at 14:16
• I am looking for intersection of a straight line and a cubic spline. If I rotate and offset coordinate system so that line goes from (0,0) to (1,0), won't my problem be just solving a cubic equation?
– Dims
Jan 13 at 14:21
• Eliminate[equ, {u} ] /. Equal -> Subtract // Collect[#, t, Simplify] & evaluates the cubic equation in t. Wether it's solvable depends on all parameters p1,p2,p3,... Jan 13 at 14:24

You can solve it in 2 stages. First we solve the first equitation for u:

sol1 = Solve[equ[[1]], u]


Then we use this in the second equitation to get "t":

sol2 = Solve[equ[[2]] /. sol1, t]


Now we can get the solution for u:

solu = u /. sol1 /. solt


And the solution for t:

solt = t /. sol2


Note: solution pairs {t,u} are contained in: {solt[[i]],solu[[i]]}

• Great! But how to understand, why doesn't Mathematica do this automatically???
– Dims
Jan 13 at 19:07
• Interesting question! It would be great if you could ask "support@wolfram.com" and post their answer here. Jan 13 at 20:00
• I understood: these expressions are "raw" and very long; if I run Simplify agains them it also hangs.
– Dims
Jan 13 at 21:14
• If you can replace control points by numeric values it will become much simpler. Jan 13 at 21:22

Get a result with Solve in a second, substituting the coefficients of t und u and then reinsert.

Curve1[t_, p1_List, p2_List] = (1 - t) p1 + t p2;
Curve2[t_, p1_List, p2_List, p3_List] = (1 - t)^2 p1 +
2 t (1 - t) p2 + t^2 p3;
Curve3[t_, p1_List, p2_List, p3_List, p4_List] = (1 - t)^3 p1 +
3 t (1 - t)^2 p2 + 3 t^2 (1 - t) p3 + t^3 p4;
equ = Curve3[t, {x1, y1}, {x2, y2}, {x3, y3}, {x4, y4}] ==
Curve1[u, {v1, w1}, {v2, w2}];
(equ2 = {(equ[[1, 1]] - equ[[2, 1]]) ==
0, (equ[[1, 2]] - equ[[2, 2]]) == 0} // Expand) // TableForm

(*   {-v1 + u v1 - u v2 + x1 - 3 t x1 + 3 t^2 x1 - t^3 x1 + 3 t x2 -
6 t^2 x2 + 3 t^3 x2 + 3 t^2 x3 - 3 t^3 x3 + t^3 x4 ==
0, -w1 + u w1 - u w2 + y1 - 3 t y1 + 3 t^2 y1 - t^3 y1 + 3 t y2 -
6 t^2 y2 + 3 t^3 y2 + 3 t^2 y3 - 3 t^3 y3 + t^3 y4 == 0}   *)

CoefficientList[#, t] & /@ equ2[[All, 1]]

(*   {{-v1 + u v1 - u v2 + x1, -3 x1 + 3 x2, 3 x1 - 6 x2 + 3 x3, -x1 + 3 x2 - 3 x3 + x4},
{-w1 + u w1 - u w2 + y1, -3 y1 + 3 y2, 3 y1 - 6 y2 +3 y3, -y1 + 3 y2 - 3 y3 + y4}}   *)

equ3 = {-v1 + u (cuv) + x1 + t (ctx) + t^2 (ct2x) + t^3 (ct3x) ==
0, -w1 + u (cuw) + y1 + t (cty) + t^2 (ct2y) + t^3 (ct3y) == 0}

sol = Solve[equ3, {t, u}]

" A very large output ...."


Now resubstitute the cuv, ctx, ct2x, ct3x, cuw, cty, ct2y, ct3y.