• Create Account

#Actualyahastu

Posted 30 May 2013 - 12:56 PM

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.

#2yahastu

Posted 30 May 2013 - 12:43 PM

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.

#1yahastu

Posted 30 May 2013 - 12:42 PM

I have a parametric 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 parametric 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.

PARTNERS