Thuật toán cho giao điểm của 2 dòng?

Question

Tôi có 2 dòng. Cả hai dòng có chứa 2 điểm X và Y. Điều này có nghĩa là cả hai đều có chiều dài.

Tôi thấy 2 công thức, một công thức sử dụng các yếu tố quyết định và một sử dụng đại số bình thường. Cách nào hiệu quả nhất để tính toán và công thức trông như thế nào?

Tôi đang gặp khó khăn khi sử dụng ma trận trong mã.

Đây là những gì tôi có cho đến nay, nó có thể hiệu quả hơn không?

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

Giả sử bạn có hai dòng có dạng Ax + By = C, bạn có thể tìm thấy nó khá dễ dàng:

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; 

Kéo từ here

Answer 2

Chúng đun sôi xuống cùng một công thức. Nếu nhìn vào nó như là một vấn đề đại số bình thường là dễ dàng hơn, làm điều đó.

Answer 3

Làm thế nào để tìm giao điểm của hai dòng/đoạn/ray với hình chữ nhật

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 + "]"; 
    } 
} 

mẫu đầy đủ được mô tả [tại đây] [1]

Answer 4

Gần đây tôi đã trở lại trên giấy để tìm một giải pháp cho vấn đề này bằng cách sử dụng đại số cơ bản. Dưới đây là giải pháp của tôi. Giải thích là trong các bình luận mã. Kiểm tra Github repository để kiểm tra.

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)); 
    } 
}