2 라인의 교차점에 대한 알고리즘?

Question

두 줄이 있습니다. 두 줄은 X와 Y의 두 점을 포함합니다. 이것은 둘 다 길이를 가지고 있음을 의미합니다.

나는 2 개의 수식을 봅니다. 하나는 행렬식을 사용하고 다른 하나는 정규 대수를 사용합니다. 어느 것이 가장 효율적으로 계산되며 공식은 어떻게 생겼습니까?

코드에서 행렬을 사용하는 데 어려움을 겪고 있습니다.

이것은 내가 지금까지 가지고있는 것보다 효율적 일 수 있습니까?

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

, 당신은 아주 쉽게 찾을 수 있습니다 :

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; 

이 here

Answer 2

같은 수식을 사용합니다. 정상적인 대수학 문제로 보는 것이 더 쉽다면, 그렇게하십시오. 양식 Ax + By = C의 두 라인을 가지고 가정

Answer 3

에서 가져온 사각형

두 개의 라인/부문/광선의 교차점을 찾는 방법

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

전체 샘플 [여기] [1]

Answer 4

나는 최근에이 문제에 대한 해결책을 찾기 위해 종이에 기초 대수학을 사용했다. 아래 내 솔루션입니다. 설명은 코드 주석에 있습니다. Github repository을 검사하십시오.

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