Suppose that two ends of a cubic Bezier curve is connected by a straight line. Is there a simple way to find out whether this straight line intersects the Bezier curve (apart from the endpoints)? If it intersects then what will be the corresponding Bezier curve parameter's value?
[Math] Cubic Bezier curve and a straight line intersection
bezier-curve
Related Solutions
As you say, four points (without their associated "$t$" values) are not enough to define a planar cubic Bezier curve.
In fact, 6 points are needed. But, on the other hand, the 6 points have to satisfy certain conditions, or else the required curve does not exist. In your case, you know that the curve exists, because it was used to generate the points in the first place.
The full story is given in this paper: J. Kozak, M. Krajnc, Geometric interpolation by planar cubic polynomial curves, Comput. Aided Geom. Des., 24 (2007), pp. 67-78. You can get a copy of the paper at the authors website.
Another approach (instead of the clever techniques suggested in the paper) is to use brute-force numerical methods. Start with 6 points $X_1, \ldots, X_6$ and 6 parameter values $t_1, \ldots, t_6$. We can assume that $t_1 = 0$ and $t_6 = 1$, but $t_2, t_3, t_4, t_5$ are unknown.We want to find control points $P_1, P_2, P_3, P_4$ for our curve. Obviously we can set $P_1 = X_1$ and $P_4 = X_6$, but $P_2$ and $P_3$ are unknown. We can (numerically) find values of $t_2, t_3, t_4, t_5$ and $P_2$ and $P_3$ that minimize the quantity
$$ \sum_{i=2}^{i=5}\Vert C(t_i) - X_i \Vert^2 $$
where $C(t)$ is the Bezier curve with control points $P_1, P_2, P_3, P_4$. This is a fairly nasty non-linear problem, but a good numerical algorithm will usually converge to the desired solution, given a decent starting point.
Another numerical approach: with the same notation we used above, solve the equations: $$ C(t_i) = X_i \quad (i = 2,3,4,5)$$ Since the $X_i$ are 2D points, there are 8 equations here. We have 8 unknowns -- $t_2, t_3, t_4, t_5$ and the $x$ and $y$ coordinates of $P_2$ and $P_3$. The equations are non-linear, but a good numerical root-finding package should be able to handle them.
A much better approach is to get the Bezier curves from the CAD package. If the design guys won't give you the curves, you should charge them more money for your services, since they are making your life so much more difficult. Their choice -- curves or cash :-)
Suppose we let $\mathbf{P}(t)$ be the Bezier curve, and let the given point be $\mathbf{B}$.
In theory, we want to find a value of $t$ such that $\mathbf{P}(t) = \mathbf{B}$. If you write out the $x$ and $y$ components separately, this will give you two cubic equations, which should have a common root, $t$.
But, in floating point arithmetic, $\mathbf{B}$ will be some small distance away from the curve, and we need to accomodate this. So, a better approach is to find the point on the curve that is closest to $\mathbf{B}$. In other words, find the value of $t$ that minimises the distance from $\mathbf{B}$ to $\mathbf{P}(t)$. At the point where this happens, the vector $\mathbf{P}(t) - \mathbf{B}$ will be perpendicular to the curve tangent, so $$ (\mathbf{P}(t) - \mathbf{B}) \cdot \mathbf{P}'(t) = 0 $$ Since $\mathbf{P}(t)$ is cubic and $\mathbf{P}'(t)$ is quadratic, this is an equation of degree 5 in $t$, which you can solve using your favorite numerical root-finder. This is the brain-dead brute force approach.
Now a smarter way ...
If you look in these notes by Tom Sederberg, you will find some techniques for "inversion" of polynomial and rational curves, based on the use of resultants. Specifically, on page 200, you will find a formula for doing "inversion" of a cubic curve written in Bezier form, and there's a nice worked example on page 201. This is exactly what you need.
As I mentioned above, you will often meet cases where the given point $\mathbf{B}$ is not exactly on the curve. You can apply the inversion formula, anyway, and it will give you some value of $t$. I'm not 100% sure what point this value of $t$ represents. I don't think it's the point on the curve that's closest to $\mathbf{B}$, but it should be good enough if $\mathbf{B}$ is already very close to the curve.
Best Answer
Given 2D cubic Bezier segment $\mathcal{B}(t,A,B,C,D)=A\,(1-t)^3+3B\,(1-t)^2t+3C\,(1-t)t^2+D\,t^3$, $t\in[0,1]$ and line segment $\mathcal{L}(t,A,D)=A\,(1-s)+D\,s$, $s\in[0,1]$, the value of $t:\mathcal{B}(t,A,B,C,D)=\mathcal{L}(s,A,D),\ t\ne0, t\ne1$ is the same as the value of $t:\mathcal{B}(t,0,B-A,C-A,D-A)=\mathcal{L}(s,0,D-A)$. So, with a substitution $b=B-A,\ c=C-A,\ d=D-A$ we can solve a system of two equations with two unknowns $t,s$:
\begin{align} \mathcal{B}(t,0,b_x,c_x,d_x) &= \mathcal{L}(s,0,d_x) \\ \mathcal{B}(t,0,b_y,c_y,d_y) &= \mathcal{L}(s,0,d_y) \end{align}
which gives the value of parameter $t$ as
\begin{align} t &= \frac{b_x\,d_y-d_x\,b_y}{b_x\,d_y-c_x\,d_y-d_x\,b_y+d_x\,c_y} \end{align}
If $0<t<1$ than the intersection point of $\mathcal{B}$ and $\mathcal{L}$ is $X=\mathcal{B}(t,A,B,C,D)$.