Como saber se uma linha de interseção de um plano em C#?

Question

Eu tenho dois pontos (um segmento de linha) e um retângulo.Gostaria de saber como calcular se o segmento de recta intersecta o retângulo.

Answer 1

A partir do meu "Geometria" de classe:

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

Fazer http://mathworld.wolfram.com/Line-LineIntersection.html para a linha e de cada lado do retângulo.
Ou: http://mathworld.wolfram.com/Line-PlaneIntersection.html

Answer 3

desde que ele esteja ausente, eu vou adicioná-lo para a integralidade

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

observe que o método gira segmentos de linha, de modo a evitar a direcção-problemas relacionados com a

Answer 4

Se é 2d, em seguida, todas as linhas são o único avião.

Então, essa é básica 3-D de geometria.Você deve ser capaz de fazer isso com uma simples equação.

Confira esta página:

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

A segunda solução deve ser fácil de implementar, desde que você traduzir as coordenadas do retângulo a equação de um plano.

Além disso, verifique se o seu denominador não é zero (linha não se cruzam ou está contido no plano).

Answer 5

Classe de uso:

System.Drawing.Rectangle

Método:

IntersectsWith();

Answer 6

Eu odeio a navegação do MSDN docs (que está muito lento e estranho :-s), mas eu acho que eles devem ter algo semelhante para este método de Java...e que se ainda não, ruim para eles!XD (btw, ele funciona para todos os segmentos, não linhas).

Em qualquer caso, você pode inspecionar o código aberto Java SDK para ver como é implementado, talvez você vai aprender algum truque novo (eu estou sempre surpreso quando eu olhar o código de outras pessoas)

Answer 7

Não é possível verificar a linha contra cada lado do retângulo usando um simples segmento de linha fórmula.