Followers 0

# Intersection between polynomial curve and parametric line

## 3 posts in this topic

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
0

##### Share on other sites

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.

1

##### Share on other sites

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
0

##### Share on other sites

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
1

## Create an account

Register a new account