Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## RE: [Algorithms] Point/line collision

 RE: [Algorithms] Point/line collision From: Rockn-Roll - 2000-11-02 08:04:48 ```My brain is fried from work, so my only input is to work backward. Start with a simple case then increase the complexity. In 2D you can work with a single equation such as ax + by + c = 0 then insert into x and y the equation which you state is only a function of t; hence one equation with one unknown. When working with trig functions you may need to use identities such as sin^2(t) + cos^2(t) = 1 to put all trig terms into sin or cos functions then solve into a function using inverse trig function that you can code to give you t which you then test to see if it's in your time interval constraint. Some other helpful trig identities: sin(2t) = 2sin(t)cos(t) cos(2t) = cos^2(t) - sin^2(t) = 1 - 2sin^2(t) = 2cos^2(t) - 1 asin(t) + bcos(t) = sqr(a^2 + b^2)sin(t + H) where H is the angle in a triangle with adjacent side a and opposite side b. With trig functions the equations can get nasty real quick. If you want a quick and dirty numeric solution then use a Maclaurin series for sin(t): sin(t) = t - (t^3)/3! + (t^5)/5! - (t^7)/7! + (t^9)/9! ... and sin(t) = 1 - (t^2)/2! + (t^4)/4! - (t^6)/6! + (t^8)/8! ... ! means factorial (2!=2,3!=6,4!=24,5!=120,6!=720,7!=5040,8!=40320,9!=362880, etc) You usually just need to carry it out to 5 terms to get sufficient accuracy, or until (t^i)/i! < precision for largest expected value of t Rockn-Roll > -----Original Message----- > From: gdalgorithms-list-admin@... > [mailto:gdalgorithms-list-admin@...]On Behalf Of > Thomas Luzat > Sent: Monday, October 23, 2000 10:38 AM > To: gdalgorithms-list@... > Subject: [Algorithms] Point/line collision > > > I have some trouble solving the following problem of which I thought a > solution (analytical if possible) wouldn't be too hard... Let's assume a > line (in 2D): > > g(s) = x0 + x1 * s, s = [0..1] > > And a moving point which rotates around another moving point (p0): > > p(t) = p0 + v * t + Mrot(omega * t) * p1 > > Now I want to check the point p for collision with the line g > during a time > interval (t = [0..1]). This gives: > > p(t) = g(s) > p0 + v * t + Mrot(omega * t) * p1 = x0 + x1 * s > > Simplifying this a bit (p0 - x0 = a, omega = 1) gives: > > a + v * t + Mrot(t) * p1 - x1 * s = 0 > > And finally: > > a_x + v_x * t + p1_x * cos(t) - p1_y * sin(t) - x1_x * s = 0 > ^ a_y + v_y * t + p1_x * sin(t) + p1_y * cos(t) - x1_y * s = 0 > ^ 0 <= s, t <= 1 > > Now, how do I solve this? :-( > > > Thomas > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > ```

 [Algorithms] Point/line collision From: Thomas Luzat - 2000-10-23 17:42:46 ```I have some trouble solving the following problem of which I thought a solution (analytical if possible) wouldn't be too hard... Let's assume a line (in 2D): g(s) = x0 + x1 * s, s = [0..1] And a moving point which rotates around another moving point (p0): p(t) = p0 + v * t + Mrot(omega * t) * p1 Now I want to check the point p for collision with the line g during a time interval (t = [0..1]). This gives: p(t) = g(s) p0 + v * t + Mrot(omega * t) * p1 = x0 + x1 * s Simplifying this a bit (p0 - x0 = a, omega = 1) gives: a + v * t + Mrot(t) * p1 - x1 * s = 0 And finally: a_x + v_x * t + p1_x * cos(t) - p1_y * sin(t) - x1_x * s = 0 ^ a_y + v_y * t + p1_x * sin(t) + p1_y * cos(t) - x1_y * s = 0 ^ 0 <= s, t <= 1 Now, how do I solve this? :-( Thomas ```
 RE: [Algorithms] Point/line collision From: Rockn-Roll - 2000-11-02 08:04:48 ```My brain is fried from work, so my only input is to work backward. Start with a simple case then increase the complexity. In 2D you can work with a single equation such as ax + by + c = 0 then insert into x and y the equation which you state is only a function of t; hence one equation with one unknown. When working with trig functions you may need to use identities such as sin^2(t) + cos^2(t) = 1 to put all trig terms into sin or cos functions then solve into a function using inverse trig function that you can code to give you t which you then test to see if it's in your time interval constraint. Some other helpful trig identities: sin(2t) = 2sin(t)cos(t) cos(2t) = cos^2(t) - sin^2(t) = 1 - 2sin^2(t) = 2cos^2(t) - 1 asin(t) + bcos(t) = sqr(a^2 + b^2)sin(t + H) where H is the angle in a triangle with adjacent side a and opposite side b. With trig functions the equations can get nasty real quick. If you want a quick and dirty numeric solution then use a Maclaurin series for sin(t): sin(t) = t - (t^3)/3! + (t^5)/5! - (t^7)/7! + (t^9)/9! ... and sin(t) = 1 - (t^2)/2! + (t^4)/4! - (t^6)/6! + (t^8)/8! ... ! means factorial (2!=2,3!=6,4!=24,5!=120,6!=720,7!=5040,8!=40320,9!=362880, etc) You usually just need to carry it out to 5 terms to get sufficient accuracy, or until (t^i)/i! < precision for largest expected value of t Rockn-Roll > -----Original Message----- > From: gdalgorithms-list-admin@... > [mailto:gdalgorithms-list-admin@...]On Behalf Of > Thomas Luzat > Sent: Monday, October 23, 2000 10:38 AM > To: gdalgorithms-list@... > Subject: [Algorithms] Point/line collision > > > I have some trouble solving the following problem of which I thought a > solution (analytical if possible) wouldn't be too hard... Let's assume a > line (in 2D): > > g(s) = x0 + x1 * s, s = [0..1] > > And a moving point which rotates around another moving point (p0): > > p(t) = p0 + v * t + Mrot(omega * t) * p1 > > Now I want to check the point p for collision with the line g > during a time > interval (t = [0..1]). This gives: > > p(t) = g(s) > p0 + v * t + Mrot(omega * t) * p1 = x0 + x1 * s > > Simplifying this a bit (p0 - x0 = a, omega = 1) gives: > > a + v * t + Mrot(t) * p1 - x1 * s = 0 > > And finally: > > a_x + v_x * t + p1_x * cos(t) - p1_y * sin(t) - x1_x * s = 0 > ^ a_y + v_y * t + p1_x * sin(t) + p1_y * cos(t) - x1_y * s = 0 > ^ 0 <= s, t <= 1 > > Now, how do I solve this? :-( > > > Thomas > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list > ```