Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 28 Feb 2013
Offline Last Active Yesterday, 02:39 PM

Posts I've Made

In Topic: Predicting Collision time of Circle-Line segment

Yesterday, 08:40 AM

I don't think there's a single simple analytical formula to find the intersection of a moving circle and a line segment. There's just too many elements in play. There are cases where the path of the circle doesn't intersect the line but the circle does (either tangent to the line or intersects in 2 places), or the circle's path passes through the infinite line but not the line segment, and so on. There are simply too many cases to run through to get a single formula.


However, there are a lot of tricks you can use. Circle-line intersections and circle-circle intersections can be very quick since they are analytical formulas. If you define your line segment as parametric in a certain way, your desired t values will be between 0 and 1 and everything else will be outside that range. Which tricks you use really depend on your desired approach.

In Topic: Predicting Collision time of Circle-Line segment

27 April 2015 - 05:59 PM

You find the implicit line of the line segment \( ax+by+c=0 \), and since the circle's path is \( x(t) = a_xt^2+b_xt+c_x \) and \( y(t) = a_yt^2+b_yt+c_y \), you can substitute those into the line equation: \( a(a_xt^2+b_xt+c_x) + b(a_yt^2+b_yt+c_y) + c = 0 \). This can be easily factored into a quadratic equation with \(t\) as the independent variable. Solving the quadratic for \(t\), you can get the intersections of the circle's path and the static line segment. Since this is quadratic, you can get the possibility of two real roots (two intersections), one real root (curve is tangent to the line), or two complex roots (no intersections) depending on if the discriminant \(B^2 - 4AC\) is greater than zero, zero, or less than zero, respectively. The \(t\) values will be in terms of the circle's parametric path, so plugging \(t\) back in will yield the \((x,y)\) point of the intersection.

In Topic: Better way for geometry problem

27 April 2015 - 05:47 PM

I cannot have your line intersection method to work.

I'm getting really confused about all those 2d to 3d to homogeneous or 4d vectors or  (ax+by+c=0) lines.

Apparently it's so simple that I couldn't find any clear explanation and I feel really stupid to ask but...

Could you explain how from 4 3d points I can have the 2 implicit lines to do the cross product with ? Cause all I'm getting at the moment is the expected recturn vector of the cross product which as no connection with an intersection point.


Many thx.


Sorry, I missed the part that you wanted the 3D position. Using implicit lines is a 2D thing since a 3D line can't be represented as a single implicit equation. Homogeneous coordinates are a simple idea that make computational geometry much easier from a certain standpoint. If you've ever seen a 2D point (x,y) become a 3D point (x,y,1) or the graphics perspective divide (x,y,z,1) = (X/w,Y/w,Z/w,w), then that's using homogeneous coordinates. Barycentric coordinates are also a form of homogeneous coordinates as well if you've ever seen those. It's basically taking a problem into a higher-dimensional space and for some problems, it helps find better solutions. In the case of finding an intersection of implicit lines in 2D, it reduces that to a simple cross-product type operation.


I think you could find a simple solution given that all the points you want lie on the plane ABD. This reduces the 3D problem into a 2D-ish one. Since the plane is defined by the centers of the spheres, the circle resulting from the plane-sphere intersection will be the great circle.

In Topic: Better way for geometry problem

23 April 2015 - 12:44 PM

The easiest way I can think of is to use vector math to find BC (BA+AC=BC) and AD (AD = DB-BA) and get the intersection E from them. You can find the analogue to point C on the circle around D (call it G) to construct a line BG and F would be the intersection of BG and AD. 


I wrote an article that details a method that simply uses the cross product to determine the intersection of 2 lines. The lines need to be in an implicit form (ax+by+c=0) and the resulting point is in homogeneous coordinates (x*w,y*w,w), but those transformations are very simple. This method also doesn't yield any infinities if the lines are parallel, and no trigonometric functions are used.



In Topic: Predicting Collision time of Circle-Line segment

22 April 2015 - 05:16 PM

If you know the circle's parametric path through space, you can do a curve-line intersection test and find the parameter value of intersections.