两条线相交的算法？

Question

我有2行。两条线都包含 X 和 Y 两个点。这意味着它们都有长度。

我看到两个公式，一个使用行列式，一个使用普通代数。哪个计算效率最高？公式是什么样的？

我很难在代码中使用矩阵。

这就是我目前所拥有的，它可以更有效吗？

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

    //Line2
    float A2 = line2V2.Y - line2V1.Y;
    float B2 = line2V1.X - line2V2.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

假设您有两行 Ax + By = C 形式的行，您可以很容易地找到它：

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;

从 此处

Answer 2

我最近重新回到纸上，用基本代数找到了这个问题的解决方案。我们只需要求解两条直线形成的方程，如果存在有效解，则存在交点。

您可以检查我的 Github 存储库以获取扩展的实现处理 double 和 测试。

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
{
    //  Returns Point of intersection if do intersect otherwise default Point (null)
    public static Point FindIntersection(Line lineA, Line lineB, double tolerance = 0.001)
    {
        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) with overlapping
        if (Math.Abs(x1 - x2) < tolerance && Math.Abs(x3 - x4) < tolerance && Math.Abs(x1 - x3) < tolerance)
        {
            throw new Exception("Both lines overlap vertically, ambiguous intersection points.");
        }

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

        //equations of the form x=c (two vertical parallel lines)
        if (Math.Abs(x1 - x2) < tolerance && Math.Abs(x3 - x4) < tolerance)
        {   
            //return default (no intersection)
            return default(Point);
        }

        //equations of the form y=c (two horizontal parallel lines)
        if (Math.Abs(y1 - y2) < tolerance && Math.Abs(y3 - y4) < tolerance)
        {
            //return default (no intersection)
            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 (Math.Abs(x1 - x2) < tolerance)
        {
            //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 (Math.Abs(x3 - x4) < tolerance)
        {
            //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 (!(Math.Abs(-m1 * x + y - c1) < tolerance
                && Math.Abs(-m2 * x + y - c2) < tolerance))
            {
                //return default (no intersection)
                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 (no intersection)
        return default(Point);

    }

    // Returns true if given point(x,y) is inside the given line segment
    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);
    }
}

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

我在其他地方找到了解决方案并将其简化到我不知道它是如何工作的但它通过了我的所有测试

    public static void GetCastPoint(Vector2 from, Vector2 to, Vector2 pointToCast, out Vector2 result, out float signedCompletion)
{
    Vector2 direction = to - from;
    float magnitude = direction.sqrMagnitude;
    Vector2 distanceFromPoint = from - pointToCast;
    signedCompletion = -Vector2.Dot(direction, distanceFromPoint) / 
    magnitude;
    float completion = Mathf.Clamp01(signedCompletion);
    result = from + (direction * completion);
}