c#; 2D; line segment / circle intersection points; have code, need help!

Hi BaconU,

Look at the bottom of the site, that you posted. There they show how you can validate, if the intersection point is between P1 and P2 or not, that is, if it is in the line segment.

ike

First, look here:
http://mathworld.wolfram.com/Circle-LineIntersection.htmlhttp://mathworld.wolfram.com/Circle-LineIntersection.html

ike:

Sadly, my math chops are not the best.  As a result, I don't fully comprehend how to apply what they mean for the value of u in determining if the intersection points are on the line segment.

Here's their definition of u on the site:
(x3 - x1)(x2 - x1) + (y3 - y1)(y2 - y1) + (z3 - z1)(z2 - z1)
----------------------------------------------------------------------
(x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1) + (z2 - z1)(z2 - z1)

Since my library is 2D, here's the 2D version:
(x3 - x1)(x2 - x1) + (y3 - y1)(y2 - y1)
----------------------------------------------
(x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1)

And, converting their coodinate system into mine, I get:
u      = ((circle.centerX - p1.X) * (p2.X - p1.X) + (circle.centerY - p1.Y) * (p2.Y - p1.Y)) /
           ((p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y));

I've put this into my code right after the bb4ac definition.

According to the site, if this value is between 0 and 1, the line segment intersects.  Ok, that's straight forward enough.  But then they mention being less than the radius.  And that's what I don't get.  If u is between 0 and 1 how can it have any relationship to the radius?  If not u, what is supposed to be less than the radius?

If I'm supposed to use u to calculate the intersection points, I don't follow how they are saying to do so.

Dan:

The problem with the wolfram/mathworld link/info is that it is for infinite lines also.  this doesn't help me. :)

Here are some images of tests performed using this function for intersection detection between a circle and a polygon. The first image shows a successful intersection determination from the algorithm.
intersect-success.png

fail 1
intersect-fail1.png

fail 2 - note that for the intersection detection, I do no additional testing to determine if the circle is in the polygon - the intersections are completely calculated using the given method - this failure might lead one to believe I am doing so, but this is not the case
intersect-fail2.png

and here's my code as it stands right now

/// <param name="a">Point2d line starting point</param>
    /// <param name="b">Point2d line ending point</param>
    /// <param name="cirle">Point2d of a circle center</param>
    /// <param name="radius">double radius of circle</param>
    /// <returns>Point2d[] array</returns>
    static public Point2d[] IntersectionPoint(Point2d p1, Point2d p2, Point2d circle, double radius) {
      Point2d   dp    = new Point2d();
      Point2d[] sect;
      double    a,b,c;
      double    bb4ac;
      double    mu1;
      double    mu2;
      double    u;

      if(Calculate._Pauser) {
        Calculate._Pauser = false;
      }
      
      //  get X and Y distances of the line segment
      dp.X   = p2.X - p1.X;
      dp.Y   = p2.Y - p1.Y;
      
      //  I don't understand the math beyond this
      a      = dp.X * dp.X + dp.Y * dp.Y;
      b      = 2 * (dp.X * (p1.X - circle.X) + dp.Y * (p1.Y - circle.Y));
      c      = circle.X * circle.X + circle.Y * circle.Y;
      c     += p1.X * p1.X + p1.Y * p1.Y;
      c     -= 2 * (circle.X * p1.X + circle.Y * p1.Y);
      c     -= radius * radius;
      bb4ac  = b * b - 4 * a * c;

      u      = ((circle.X - p1.X) * (p2.X - p1.X) + (circle.Y - p1.Y) * (p2.Y - p1.Y)) / 
               ((p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y));

      //  u must be between 0 and 1 for the line segment to intersect
      if(u < 0 || u > 1) {
        return new Point2d[0];
      }

      //  if bb4ac is < 0, the line does not intersection
      if(bb4ac < 0 || Math.Abs(a) < Double.Epsilon) {
        //  no intersection
        return new Point2d[0];
      }
      //  if bb4ac is at 0, one intersection point
      else if(bb4ac >= -Double.Epsilon && bb4ac <= Double.Epsilon) {
        //  line intersects once
        sect = new Point2d[1];
        mu1  = -b / (2 * a);
        sect[0] = new Point2d(p1.X + mu1 * ( p2.X - p1.X ), p1.Y + mu1 * ( p2.Y - p1.Y ));
      }
      //  else bb4ac > 0, two intersection points
      else {
        mu1 = ( -b + Math.Sqrt(bb4ac) ) / ( 2 * a );
        mu2 = ( -b - Math.Sqrt(bb4ac) ) / ( 2 * a );

        sect = new Point2d[2];
        sect[0] = new Point2d(p1.X + mu1 * ( p2.X - p1.X ), p1.Y + mu1 * ( p2.Y - p1.Y ));
        sect[1] = new Point2d(p1.X + mu2 * ( p2.X - p1.X ), p1.Y + mu2 * ( p2.Y - p1.Y ));
      }

      return sect;
    }

Select allOpen in new window

well,  P1 and P2 define the line segment, P3 is the center of the circle, now

u =

(x3 - x1)(x2 - x1) + (y3 - y1)(y2 - y1) + (z3 - z1)(z2 - z1)
-----------------------------------------------------------
(x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1) + (z2 - z1)(z2 - z1)


if 0 <= u <= 1, then the closest point is between P1 and P2, then you must make the normal intersection test.
if not, then there is no intersection of the line segment

Start implementing this, then we take it from there

Great work, thanks for the contribution :)

ike