Sign in to follow this  
yahastu

Intersection between polynomial curve and parametric line

Recommended Posts

yahastu    154

I have a polynomial curve defined by a set of coefficients (a_0, a_1, a_2, ... a_N ):

 

y(x) = a_0 + a_1*x + a_2*x^2 + ... a_N*x^N

I also have a parametric line:

 

p(t) = a + b*t

I wish to find the value of "t" such that the parametric line intersects with the polynomial curve.

Clearly, the first step is to expand the parametric equation:

p_x(t) = a_x + b_x*t
p_y(t) = a_y + b_y*t

Plugging in, I get this nasty thing:

a_y + b_y*t = a_0 + a_1*(a_x + b_x*t) + a_2*(a_x+b_x*t)^2 + a_3*(a_x+b_x*t)^3 + ...

I have no idea how to solve this for "t".

I want a numerical solution that works for arbitrary N, so I'm not expecting to find a closed form solution...I'm fine using any linear algebra or minimization techniques to get the answer, I'm just not sure what the most effective method would be.

Edit: I'm thinking that perhaps the proper approach is via "curve implicization" to convert the polynomial curve into a parametric form, thereby making it easier to compute the intersection.  I found this paper and I think it may be possible to implicitize this polynomial curve by using Sylvester's matrix elimination method as briefly described here ( http://www.cs.cmu.edu/~hulya/Publications/IJCV03Paper.pdf , p107 )...but I'm still a bit confounded.

Edited by yahastu

Share this post


Link to post
Share on other sites
alvaro    21246

Start with your "nasty thing". It's actually not that nasty: Subtract one side from the other to obtain a polynomial in t whose roots are the solutions to your problem. Now use any technique to find roots of polynomials (Newton-Raphson is fast and easy to implement).

 

The "edit" section of your post sounds like you are making the problem waaay more complicated than it needs to be.

Share this post


Link to post
Share on other sites
yahastu    154

Thanks for your reply Alvaro.  If I can rearrange the nasty equation into a polynomial in t, then yes I can easily find the roots of it.  The difficulty is in automatically calculating the coefficients of this polynomial, given that it is a summation of terms such as "a_N*(a_x+b_x*t)^N" which would effect the coefficients for ALL terms less than N.

I think that implicitizing the equation might just come down to constructing an appropriate matrix and taking the determinant, after which point I'd have two parametric equations with two unknown parameters, should should be solvable...so I'm not sure which approach is actually easier

Edited by yahastu

Share this post


Link to post
Share on other sites
alvaro    21246

Of course you could treat this as a polynomial in a_x+b_x*t and then subtract a_x from the result and divide by b_x, if you think Newton's binomial formula is scary.

Edited by Álvaro

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this