Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Intersection between polynomial curve and parametric line


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 yahastu   Members   -  Reputation: 152

Like
0Likes
Like

Posted 30 May 2013 - 12:42 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.


Edited by yahastu, 30 May 2013 - 12:56 PM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13661

Like
1Likes
Like

Posted 30 May 2013 - 01:10 PM

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.



#3 yahastu   Members   -  Reputation: 152

Like
0Likes
Like

Posted 30 May 2013 - 02:16 PM

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, 30 May 2013 - 02:27 PM.


#4 Álvaro   Crossbones+   -  Reputation: 13661

Like
1Likes
Like

Posted 30 May 2013 - 02:56 PM

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, 30 May 2013 - 08:53 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS