¿Cómo saber si una línea intersecta un plano en C#?

Question

Tengo dos puntos (un segmento de recta) y un rectángulo.Me gustaría saber cómo calcular si el segmento de recta interseca al rectángulo.

Answer 1

De mi clase de "Geometría":

public struct Line
{
    public static Line Empty;

    private PointF p1;
    private PointF p2;

    public Line(PointF p1, PointF p2)
    {
        this.p1 = p1;
        this.p2 = p2;
    }

    public PointF P1
    {
        get { return p1; }
        set { p1 = value; }
    }

    public PointF P2
    {
        get { return p2; }
        set { p2 = value; }
    }

    public float X1
    {
        get { return p1.X; }
        set { p1.X = value; }
    }

    public float X2
    {
        get { return p2.X; }
        set { p2.X = value; }
    }

    public float Y1
    {
        get { return p1.Y; }
        set { p1.Y = value; }
    }

    public float Y2
    {
        get { return p2.Y; }
        set { p2.Y = value; }
    }
}

public struct Polygon: IEnumerable<PointF>
{
    private PointF[] points;

    public Polygon(PointF[] points)
    {
        this.points = points;
    }

    public PointF[] Points
    {
        get { return points; }
        set { points = value; }
    }

    public int Length
    {
        get { return points.Length; }
    }

    public PointF this[int index]
    {
        get { return points[index]; }
        set { points[index] = value; }
    }

    public static implicit operator PointF[](Polygon polygon)
    {
        return polygon.points;
    }

    public static implicit operator Polygon(PointF[] points)
    {
        return new Polygon(points);
    }

    IEnumerator<PointF> IEnumerable<PointF>.GetEnumerator()
    {
        return (IEnumerator<PointF>)points.GetEnumerator();
    }

    public IEnumerator GetEnumerator()
    {
        return points.GetEnumerator();
    }
}

public enum Intersection
{
    None,
    Tangent,
    Intersection,
    Containment
}

public static class Geometry
{

    public static Intersection IntersectionOf(Line line, Polygon polygon)
    {
        if (polygon.Length == 0)
        {
            return Intersection.None;
        }
        if (polygon.Length == 1)
        {
            return IntersectionOf(polygon[0], line);
        }
        bool tangent = false;
        for (int index = 0; index < polygon.Length; index++)
        {
            int index2 = (index + 1)%polygon.Length;
            Intersection intersection = IntersectionOf(line, new Line(polygon[index], polygon[index2]));
            if (intersection == Intersection.Intersection)
            {
                return intersection;
            }
            if (intersection == Intersection.Tangent)
            {
                tangent = true;
            }
        }
        return tangent ? Intersection.Tangent : IntersectionOf(line.P1, polygon);
    }

    public static Intersection IntersectionOf(PointF point, Polygon polygon)
    {
        switch (polygon.Length)
        {
            case 0:
                return Intersection.None;
            case 1:
                if (polygon[0].X == point.X && polygon[0].Y == point.Y)
                {
                    return Intersection.Tangent;
                }
                else
                {
                    return Intersection.None;
                }
            case 2:
                return IntersectionOf(point, new Line(polygon[0], polygon[1]));
        }

        int counter = 0;
        int i;
        PointF p1;
        int n = polygon.Length;
        p1 = polygon[0];
        if (point == p1)
        {
            return Intersection.Tangent;
        }

        for (i = 1; i <= n; i++)
        {
            PointF p2 = polygon[i % n];
            if (point == p2)
            {
                return Intersection.Tangent;
            }
            if (point.Y > Math.Min(p1.Y, p2.Y))
            {
                if (point.Y <= Math.Max(p1.Y, p2.Y))
                {
                    if (point.X <= Math.Max(p1.X, p2.X))
                    {
                        if (p1.Y != p2.Y)
                        {
                            double xinters = (point.Y - p1.Y) * (p2.X - p1.X) / (p2.Y - p1.Y) + p1.X;
                            if (p1.X == p2.X || point.X <= xinters)
                                counter++;
                        }
                    }
                }
            }
            p1 = p2;
        }

        return (counter % 2 == 1) ? Intersection.Containment : Intersection.None;
    }

    public static Intersection IntersectionOf(PointF point, Line line)
    {
        float bottomY = Math.Min(line.Y1, line.Y2);
        float topY = Math.Max(line.Y1, line.Y2);
        bool heightIsRight = point.Y >= bottomY &&
                             point.Y <= topY;
        //Vertical line, slope is divideByZero error!
        if (line.X1 == line.X2)
        {
            if (point.X == line.X1 && heightIsRight)
            {
                return Intersection.Tangent;
            }
            else
            {
                return Intersection.None;
            }
        }
        float slope = (line.X2 - line.X1)/(line.Y2 - line.Y1);
        bool onLine = (line.Y1 - point.Y) == (slope*(line.X1 - point.X));
        if (onLine && heightIsRight)
        {
            return Intersection.Tangent;
        }
        else
        {
            return Intersection.None;
        }
    }

}

Answer 2

Hacer http://mathworld.wolfram.com/Line-LineIntersection.html para la línea y cada lado del rectángulo.
O: http://mathworld.wolfram.com/Line-PlaneIntersection.html

Answer 3

Como falta, lo agregaré para que esté completo.

public static Intersection IntersectionOf(Line line1, Line line2)
    {
        //  Fail if either line segment is zero-length.
        if (line1.X1 == line1.X2 && line1.Y1 == line1.Y2 || line2.X1 == line2.X2 && line2.Y1 == line2.Y2)
            return Intersection.None;

        if (line1.X1 == line2.X1 && line1.Y1 == line2.Y1 || line1.X2 == line2.X1 && line1.Y2 == line2.Y1)
            return Intersection.Intersection;
        if (line1.X1 == line2.X2 && line1.Y1 == line2.Y2 || line1.X2 == line2.X2 && line1.Y2 == line2.Y2)
            return Intersection.Intersection;

        //  (1) Translate the system so that point A is on the origin.
        line1.X2 -= line1.X1; line1.Y2 -= line1.Y1;
        line2.X1 -= line1.X1; line2.Y1 -= line1.Y1;
        line2.X2 -= line1.X1; line2.Y2 -= line1.Y1;

        //  Discover the length of segment A-B.
        double distAB = Math.Sqrt(line1.X2 * line1.X2 + line1.Y2 * line1.Y2);

        //  (2) Rotate the system so that point B is on the positive X axis.
        double theCos = line1.X2 / distAB;
        double theSin = line1.Y2 / distAB;
        double newX = line2.X1 * theCos + line2.Y1 * theSin;
        line2.Y1 = line2.Y1 * theCos - line2.X1 * theSin; line2.X1 = newX;
        newX = line2.X2 * theCos + line2.Y2 * theSin;
        line2.Y2 = line2.Y2 * theCos - line2.X2 * theSin; line2.X2 = newX;

        //  Fail if segment C-D doesn't cross line A-B.
        if (line2.Y1 < 0 && line2.Y2 < 0 || line2.Y1 >= 0 && line2.Y2 >= 0)
            return Intersection.None;

        //  (3) Discover the position of the intersection point along line A-B.
        double posAB = line2.X2 + (line2.X1 - line2.X2) * line2.Y2 / (line2.Y2 - line2.Y1);

        //  Fail if segment C-D crosses line A-B outside of segment A-B.
        if (posAB < 0 || posAB > distAB)
            return Intersection.None;

        //  (4) Apply the discovered position to line A-B in the original coordinate system.
        return Intersection.Intersection;
    }

tenga en cuenta que el método gira los segmentos de línea para evitar problemas relacionados con la dirección

Answer 4

Si es 2d, entonces todas las líneas están en el único plano.

Esta es la geometría tridimensional básica.Deberías poder hacer esto con una ecuación sencilla.

Mira esta página:

http://local.wasp.uwa.edu.au/~pbourke/geometry/planeline/.

La segunda solución debería ser fácil de implementar, siempre y cuando traduzcas las coordenadas de tu rectángulo a la ecuación de un plano.

Además, verifica que tu denominador no sea cero (la línea no se cruza o está contenida en el plano).

Answer 5

Clase de uso:

System.Drawing.Rectangle

Método:

IntersectsWith();

Answer 6

Odio navegar por los documentos de MSDN (son tremendamente lentos y raros :-s) pero creo que deberían tener algo similar a este método Java...y si no lo han hecho, ¡mal para ellos!XD (por cierto, funciona para segmentos, no para líneas).

En cualquier caso, puedes echar un vistazo al SDK de Java de código abierto para ver cómo se implementa, tal vez aprendas algún truco nuevo (siempre me sorprende cuando miro el código de otras personas).

Answer 7

¿No es posible comparar la línea con cada lado del rectángulo usando una fórmula simple de segmento de línea?