Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 –  Alex 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]. –  Alex Aug 24 '10 at 12:51

1 Answer 1

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.)

Over the reals, it's the cylindrical algebraic decomposition that does that for you (explained for instance in the book by Basu-Pollack-Roy which is freely available). Any decent computer algebra system should be able to solve this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.