Help on Line Segment Intersection Algorithm

Question

Hi am Looking for a line segment intersection algorithm in c#. I am currently using http://alienryderflex.com/intersect/ this alogorithm;

but this algorihtm does not work when intersection point is anywhere on the line segment,( ie any end point of one line is on the other line).

Any one know better algoritm ?

 

public static bool lineSegmentIntersection(

                        double Ax, double Ay,

                        double Bx, double By,

                        double Cx, double Cy,

                        double Dx, double Dy,

                        ref double X, ref double Y)



        {

            double distAB, theCos, theSin, newX, ABpos;

            //  Fail if either line segment is zero-length.

            if (Ax == Bx && Ay == By || Cx == Dx && Cy == Dy) return false;

            //  Fail if the segments share an end-point.

            if (Ax == Cx && Ay == Cy || Bx == Cx && By == Cy

            || Ax == Dx && Ay == Dy || Bx == Dx && By == Dy)

            {

               return false;


            }


            //  (1) Translate the system so that point A is on the origin.

            Bx -= Ax; By -= Ay;

            Cx -= Ax; Cy -= Ay;

            Dx -= Ax; Dy -= Ay;


            //  Discover the length of segment A-B.

            distAB = Math.Sqrt(Bx * Bx + By * By);


            //  (2) Rotate the system so that point B is on the positive X axis.

            theCos = Bx / distAB;

            theSin = By / distAB;

            newX = Cx * theCos + Cy * theSin;

            Cy = Cy * theCos - Cx * theSin; Cx = newX;

            newX = Dx * theCos + Dy * theSin;

            Dy = Dy * theCos - Dx * theSin; Dx = newX;

            //  Fail if segment C-D doesn't cross line A-B.

            if (Cy < 0 && Dy < 0 || Cy >= 0 && Dy >= 0) return false;

            //  (3) Discover the position of the intersection point along line A-B.

            ABpos = Dx + (Cx - Dx) * Dy / (Dy - Cy);

            //  Fail if segment C-D crosses line A-B outside of segment A-B.

            if (ABpos < 0 || ABpos > distAB) return false;

            //  (4) Apply the discovered position to line A-B in the original coordinate system.

            X = (Ax + ABpos * theCos);

            Y = (Ay + ABpos * theSin);


            //  Success.

            return true;


        }

Answer 1

You could try this code.

Note: I used PointF to represent a point, so that it's easier to test it graphically, and I also created a little Segment struct to make it more readable. Should be pretty straightforward to change the method signature if needed.

Note2: There is a little quirk in one specific case: if the segments are collinear and overlapping, there are actually infinite solutions. I obviously pick a single point.

    public struct Segment {
      public PointF Start;
      public PointF End;
    }

    public PointF? Intersects (Segment AB, Segment CD) {
      double deltaACy = AB.Start.Y - CD.Start.Y;
      double deltaDCx = CD.End.X - CD.Start.X;
      double deltaACx = AB.Start.X - CD.Start.X;
      double deltaDCy = CD.End.Y - CD.Start.Y;
      double deltaBAx = AB.End.X - AB.Start.X;
      double deltaBAy = AB.End.Y - AB.Start.Y;

      double denominator = deltaBAx * deltaDCy - deltaBAy * deltaDCx;
      double numerator = deltaACy * deltaDCx - deltaACx * deltaDCy;

      if (denominator == 0) {
        if (numerator == 0) {
          // collinear. Potentially infinite intersection points.
          // Check and return one of them.
          if (AB.Start.X >= CD.Start.X && AB.Start.X <= CD.End.X) {
            return AB.Start;
          } else if (CD.Start.X >= AB.Start.X && CD.Start.X <= AB.End.X) {
            return CD.Start;
          } else {
            return null;
          }
        } else { // parallel
          return null;
        }
      }

      double r = numerator / denominator;
      if (r < 0 || r > 1) {
        return null;
      }

      double s = (deltaACy * deltaBAx - deltaACx * deltaBAy) / denominator;
      if (s < 0 || s > 1) {
        return null;
      }

      return new PointF ((float) (AB.Start.X + r * deltaBAx), (float) (AB.Start.Y + r * deltaBAy));
    }

HTH
--mc

 

Answer 2

You could try this code.

Note: I used PointF to represent a point, so that it's easier to test it graphically, and I also created a little Segment struct to make it more readable. Should be pretty straightforward to change the method signature if needed.

Note2: There is a little quirk in one specific case: if the segments are collinear and overlapping, there are actually infinite solutions. I obviously pick a single point.

  public struct Segment {
   public PointF Start;
   public PointF End;
  }

  public PointF? Intersects (Segment AB, Segment CD) {
   double deltaACy = AB.Start.Y - CD.Start.Y;
   double deltaDCx = CD.End.X - CD.Start.X;
   double deltaACx = AB.Start.X - CD.Start.X;
   double deltaDCy = CD.End.Y - CD.Start.Y;
   double deltaBAx = AB.End.X - AB.Start.X;
   double deltaBAy = AB.End.Y - AB.Start.Y;

   double denominator = deltaBAx * deltaDCy - deltaBAy * deltaDCx;
   double numerator = deltaACy * deltaDCx - deltaACx * deltaDCy;

   if (denominator == 0) {
    if (numerator == 0) {
     // collinear. Potentially infinite intersection points.
     // Check and return one of them.
     if (AB.Start.X >= CD.Start.X && AB.Start.X <= CD.End.X) {
      return AB.Start;
     } else if (CD.Start.X >= AB.Start.X && CD.Start.X <= AB.End.X) {
      return CD.Start;
     } else {
      return null;
     }
    } else { // parallel
     return null;
    }
   }

   double r = numerator / denominator;
   if (r < 0 || r > 1) {
    return null;
   }

   double s = (deltaACy * deltaBAx - deltaACx * deltaBAy) / denominator;
   if (s < 0 || s > 1) {
    return null;
   }

   return new PointF ((float) (AB.Start.X + r * deltaBAx), (float) (AB.Start.Y + r * deltaBAy));
  }

HTH
--mc

 

what if I need it in 3D