c# - puntos - libros de geometria computacional

¿Algoritmo para 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 ambas tienen longitud.

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

Estoy teniendo dificultades para 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

Cómo encontrar la intersección de dos líneas / segmentos / rayo 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 2

Hace poco volví al papel para encontrar una solución a este problema utilizando el álgebra básica. Solo resuelva las ecuaciones formadas por las dos líneas y si existe una solución válida, entonces hay una intersección.

Verifique en este repositorio de Github la implementation extendida para manejar posibles problemas de precisión con el doble y las tests .

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)
        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)
        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 lines)
        if (Math.Abs(x1 - x2) < tolerance && Math.Abs(x3 - x4) < tolerance)
        {
            return default(Point);
        }

        //equations of the form y=c (two horizontal lines)
        if (Math.Abs(y1 - y2) < tolerance && Math.Abs(y3 - y4) < tolerance)
        {
            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(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);

    }

    // 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

Suponiendo que tiene dos líneas del formulario Ax + By = C , puede encontrarlo 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;

Tirado de here