# Test if two curves intersect before finding roots

I've read that one can quickly test whether two n-degree curves f(t) and g(t) intersect (without finding the roots of an implicitized n*n polynomial) by checking if the determinant of their Bezout matrix is zero. But I am confused about how to actually apply this to two parametric curves, since I have 4 equations instead of two: x1(t), y1(t), x2(t), y2(t) (this is assuming that the two equations can't be represented in explicit form, in my case I'm using two quadratic bezier curves for example). I was trying to see if I can test x1 against x2 and then y1 against y2 independently, but did not get a zero resultant for two intersecting curves (and thinking about it afterwards, it makes sense since the t parameter will not necessarily match between the two curves even if x and y intersect). Another idea I had was computing the Bezout resultant of x1(t)-x2(t) and y1(t)-y2(t) since that seems like it would correspond to the difference between the two curves, but I realized yet again that that wouldn't work since the t is independent between the two curves and these equations do not treat it as such. Can someone point me in the right direction?

Thanks

-
I'm afraid that the tag is not appropriate, as a simple detour via wikipedia would have told you. – José Figueroa-O'Farrill Aug 23 '10 at 17:57
From your question it seems that you have two parametric curves in the plane and you want to find their intersection points, am I right? Are the parametric equations polynomials? – damiano Aug 23 '10 at 18:38
yes, they're are actually quadratic bezier curves presented in parametric form: x(t)=A.X(t-1)^2+B.X(t-1)t+C.Xt^2, y(t)=A.Y(t-1)^2+B.Y(t-1)t+C.Y^2 – Alexander Tsepkov Aug 23 '10 at 19:06
Why isn't Bezier clipping (e.g. dx.doi.org/10.1016/0010-4485(90)90039-F ) suitable for your purposes? – J. M. Aug 23 '10 at 22:07
Well, the reason is that I already implemented a solver using implicitization, but would like to save time by only calling the quartic root finder when there actually are roots to find, preferably on the interval t=[0,1]. – Alexander Tsepkov Aug 24 '10 at 12:51

If you think about it, there does not seem to be a way around eliminating two variables: $$\exists t_1, t_2,\ x_1(t_1)=x_2(t_2)\ \&\ y_1(t_1)=y_2(t_2)$$ I.e., the $x$ and $y$ coordinates coincide, but each point is obtained at a different moment in time (or again, in terms of mobile points, the two trajectories intersect, but the two mobile points do not necessarily collide.)