1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I'm afraid that the tag is not appropriate, as a simple detour via wikipedia would have told you. $\endgroup$ Commented Aug 23, 2010 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – damiano
    Commented Aug 23, 2010 at 18:38
  • $\begingroup$ 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 $\endgroup$ Commented Aug 23, 2010 at 19:06
  • $\begingroup$ Why isn't Bezier clipping (e.g. dx.doi.org/10.1016/0010-4485(90)90039-F ) suitable for your purposes? $\endgroup$ Commented Aug 23, 2010 at 22:07
  • $\begingroup$ 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]. $\endgroup$ Commented Aug 24, 2010 at 12:51

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .