Algoritmo para la intersección de 2 líneas?

Question

Tengo 2 líneas. Ambas líneas contienen sus 2 puntos de X e Y. Esto significa que ambos tienen longitud.

Veo 2 fórmulas, una que usa determinantes y otra usa álgebra normal. ¿Cuál sería el más eficiente para calcular y cómo se ve la fórmula?

Me está costando usar matrices en el código.

Esto es lo que tengo hasta ahora, ¿puede ser más eficiente?

public static Vector3 Intersect(Vector3 line1V1, Vector3 line1V2, Vector3 line2V1, Vector3 line2V2) 
    { 
     //Line1 
     float A1 = line1V2.Y - line1V1.Y; 
     float B1 = line1V2.X - line1V1.X; 
     float C1 = A1*line1V1.X + B1*line1V1.Y; 

     //Line2 
     float A2 = line2V2.Y - line2V1.Y; 
     float B2 = line2V2.X - line2V1.X; 
     float C2 = A2 * line2V1.X + B2 * line2V1.Y; 

     float det = A1*B2 - A2*B1; 
     if (det == 0) 
     { 
      return null;//parallel lines 
     } 
     else 
     { 
      float x = (B2*C1 - B1*C2)/det; 
      float y = (A1 * C2 - A2 * C1)/det; 
      return new Vector3(x,y,0); 
     } 
    } 

Answer 1

Asumiendo que tiene dos líneas de la forma Ax + By = C, se puede encontrar con bastante facilidad:

float delta = A1*B2 - A2*B1; 
if(delta == 0) 
    throw new ArgumentException("Lines are parallel"); 

float x = (B2*C1 - B1*C2)/delta; 
float y = (A1*C2 - A2*C1)/delta; 

sacado de here

Answer 2

Se reducen a la misma fórmula. Si mirarlo como un problema de álgebra normal es más fácil, hazlo.

Answer 3

¿Cómo encontrar intersección de dos líneas/segmentos/ray con rectángulo

public class LineEquation{ 
    public LineEquation(Point start, Point end){ 
     Start = start; 
     End = end; 

     IsVertical = Math.Abs(End.X - start.X) < 0.00001f; 
     M = (End.Y - Start.Y)/(End.X - Start.X); 
     A = -M; 
     B = 1; 
     C = Start.Y - M*Start.X; 
    } 

    public bool IsVertical { get; private set; } 

    public double M { get; private set; } 

    public Point Start { get; private set; } 
    public Point End { get; private set; } 

    public double A { get; private set; } 
    public double B { get; private set; } 
    public double C { get; private set; } 

    public bool IntersectsWithLine(LineEquation otherLine, out Point intersectionPoint){ 
     intersectionPoint = new Point(0, 0); 
     if (IsVertical && otherLine.IsVertical) 
      return false; 
     if (IsVertical || otherLine.IsVertical){ 
      intersectionPoint = GetIntersectionPointIfOneIsVertical(otherLine, this); 
      return true; 
     } 
     double delta = A*otherLine.B - otherLine.A*B; 
     bool hasIntersection = Math.Abs(delta - 0) > 0.0001f; 
     if (hasIntersection){ 
      double x = (otherLine.B*C - B*otherLine.C)/delta; 
      double y = (A*otherLine.C - otherLine.A*C)/delta; 
      intersectionPoint = new Point(x, y); 
     } 
     return hasIntersection; 
    } 

    private static Point GetIntersectionPointIfOneIsVertical(LineEquation line1, LineEquation line2){ 
     LineEquation verticalLine = line2.IsVertical ? line2 : line1; 
     LineEquation nonVerticalLine = line2.IsVertical ? line1 : line2; 

     double y = (verticalLine.Start.X - nonVerticalLine.Start.X)* 
        (nonVerticalLine.End.Y - nonVerticalLine.Start.Y)/ 
        ((nonVerticalLine.End.X - nonVerticalLine.Start.X)) + 
        nonVerticalLine.Start.Y; 
     double x = line1.IsVertical ? line1.Start.X : line2.Start.X; 
     return new Point(x, y); 
    } 

    public bool IntersectWithSegementOfLine(LineEquation otherLine, out Point intersectionPoint){ 
     bool hasIntersection = IntersectsWithLine(otherLine, out intersectionPoint); 
     if (hasIntersection) 
      return intersectionPoint.IsBetweenTwoPoints(otherLine.Start, otherLine.End); 
     return false; 
    } 

    public bool GetIntersectionLineForRay(Rect rectangle, out LineEquation intersectionLine){ 
     if (Start == End){ 
      intersectionLine = null; 
      return false; 
     } 
     IEnumerable<LineEquation> lines = rectangle.GetLinesForRectangle(); 
     intersectionLine = new LineEquation(new Point(0, 0), new Point(0, 0)); 
     var intersections = new Dictionary<LineEquation, Point>(); 
     foreach (LineEquation equation in lines){ 
      Point point; 
      if (IntersectWithSegementOfLine(equation, out point)) 
       intersections[equation] = point; 
     } 
     if (!intersections.Any()) 
      return false; 

     var intersectionPoints = new SortedDictionary<double, Point>(); 
     foreach (var intersection in intersections){ 
      if (End.IsBetweenTwoPoints(Start, intersection.Value) || 
       intersection.Value.IsBetweenTwoPoints(Start, End)){ 
       double distanceToPoint = Start.DistanceToPoint(intersection.Value); 
       intersectionPoints[distanceToPoint] = intersection.Value; 
      } 
     } 
     if (intersectionPoints.Count == 1){ 
      Point endPoint = intersectionPoints.First().Value; 
      intersectionLine = new LineEquation(Start, endPoint); 
      return true; 
     } 

     if (intersectionPoints.Count == 2){ 
      Point start = intersectionPoints.First().Value; 
      Point end = intersectionPoints.Last().Value; 
      intersectionLine = new LineEquation(start, end); 
      return true; 
     } 

     return false; 
    } 

    public override string ToString(){ 
     return "[" + Start + "], [" + End + "]"; 
    } 
} 

muestra completa se describe [aquí] [1]

Answer 4

Recientemente volví al papel para encontrar una solución a este problema usando álgebra básica. A continuación está mi solución. La explicación está en los comentarios del código. Compruebe Github repository para las pruebas.

public struct Line 
{ 
    public double x1 { get; set; } 
    public double y1 { get; set; } 

    public double x2 { get; set; } 
    public double y2 { get; set; } 
} 

public struct Point 
{ 
    public double x { get; set; } 
    public double y { get; set; } 
} 

public class LineIntersection 
{ 
public class LineIntersection 
{ 
    /// <summary> 
    /// Returns Point of intersection if do intersect otherwise default Point (null) 
    /// </summary> 
    /// <param name="lineA"></param> 
    /// <param name="lineB"></param> 
    /// <returns></returns> 
    public static Point FindIntersection(Line lineA, Line lineB) 
    { 
     double x1 = lineA.x1, y1 = lineA.y1; 
     double x2 = lineA.x2, y2 = lineA.y2; 

     double x3 = lineB.x1, y3 = lineB.y1; 
     double x4 = lineB.x2, y4 = lineB.y2; 

     //equations of the form x=c (two vertical lines) 
     if (x1 == x2 && x3 == x4 && x1 == x3) 
     { 
      throw new Exception("Both lines overlap vertically, ambiguous intersection points."); 
     } 

     //equations of the form y=c (two horizontal lines) 
     if (y1 == y2 && y3 == y4 && y1 == y3) 
     { 
      throw new Exception("Both lines overlap horizontally, ambiguous intersection points."); 
     } 

     //equations of the form x=c (two vertical lines) 
     if (x1 == x2 && x3 == x4) 
     { 
      return default(Point); 
     } 

     //equations of the form y=c (two horizontal lines) 
     if (y1 == y2 && y3 == y4) 
     { 
      return default(Point); 
     } 

     //general equation of line is y = mx + c where m is the slope 
     //assume equation of line 1 as y1 = m1x1 + c1 
     //=> -m1x1 + y1 = c1 ----(1) 
     //assume equation of line 2 as y2 = m2x2 + c2 
     //=> -m2x2 + y2 = c2 -----(2) 
     //if line 1 and 2 intersect then x1=x2=x & y1=y2=y where (x,y) is the intersection point 
     //so we will get below two equations 
     //-m1x + y = c1 --------(3) 
     //-m2x + y = c2 --------(4) 

     double x, y; 

     //lineA is vertical x1 = x2 
     //slope will be infinity 
     //so lets derive another solution 
     if (x1 == x2) 
     { 
      //compute slope of line 2 (m2) and c2 
      double m2 = (y4 - y3)/(x4 - x3); 
      double c2 = -m2 * x3 + y3; 

      //equation of vertical line is x = c 
      //if line 1 and 2 intersect then x1=c1=x 
      //subsitute x=x1 in (4) => -m2x1 + y = c2 
      // => y = c2 + m2x1 
      x = x1; 
      y = c2 + m2 * x1; 
     } 
     //lineB is vertical x3 = x4 
     //slope will be infinity 
     //so lets derive another solution 
     else if (x3 == x4) 
     { 
      //compute slope of line 1 (m1) and c2 
      double m1 = (y2 - y1)/(x2 - x1); 
      double c1 = -m1 * x1 + y1; 

      //equation of vertical line is x = c 
      //if line 1 and 2 intersect then x3=c3=x 
      //subsitute x=x3 in (3) => -m1x3 + y = c1 
      // => y = c1 + m1x3 
      x = x3; 
      y = c1 + m1 * x3; 
     } 
     //lineA & lineB are not vertical 
     //(could be horizontal we can handle it with slope = 0) 
     else 
     { 
      //compute slope of line 1 (m1) and c2 
      double m1 = (y2 - y1)/(x2 - x1); 
      double c1 = -m1 * x1 + y1; 

      //compute slope of line 2 (m2) and c2 
      double m2 = (y4 - y3)/(x4 - x3); 
      double c2 = -m2 * x3 + y3; 

      //solving equations (3) & (4) => x = (c1-c2)/(m2-m1) 
      //plugging x value in equation (4) => y = c2 + m2 * x 
      x = (c1 - c2)/(m2 - m1); 
      y = c2 + m2 * x; 

      //verify by plugging intersection point (x, y) 
      //in orginal equations (1) & (2) to see if they intersect 
      //otherwise x,y values will not be finite and will fail this check 
      if (!(-m1 * x + y == c1 
       && -m2 * x + y == c2)) 
      { 
       return default(Point); 
      } 
     } 

     //x,y can intersect outside the line segment since line is infinitely long 
     //so finally check if x, y is within both the line segments 
     if (IsInsideLine(lineA, x, y) && 
      IsInsideLine(lineB, x, y)) 
     { 
      return new Point() { x = x, y = y }; 
     } 

     //return default null (no intersection) 
     return default(Point); 

    } 

    /// <summary> 
    /// Returns true if given point(x,y) is inside the given line segment 
    /// </summary> 
    /// <param name="line"></param> 
    /// <param name="x"></param> 
    /// <param name="y"></param> 
    /// <returns></returns> 
    private static bool IsInsideLine(Line line, double x, double y) 
    { 
     return ((x >= line.x1 && x <= line.x2) 
        || (x >= line.x2 && x <= line.x1)) 
       && ((y >= line.y1 && y <= line.y2) 
        || (y >= line.y2 && y <= line.y1)); 
    } 
}