Wie Sie wissen, wenn Sie eine Linie schneidet ein Rechteck

    public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
    {
        return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
               LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
               (r.Contains(p1) && r.Contains(p2));
    }

    private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
    {
        float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
        float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);

        if( d == 0 )
        {
            return false;
        }

        float r = q / d;

        q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
        float s = q / d;

        if( r < 0 || r > 1 || s < 0 || s > 1 )
        {
            return false;
        }

        return true;
    }

InformationsquelleAutor der Antwort HABJAN

Brute-force-Algorithmus...

Prüfen Sie zunächst, ob das rect, ist das Links oder rechts von der Linie Endpunkte:

• Etablieren, die ganz Links und ganz rechts die X-Werte der Linie Endpunkte: XMIN und XMAX
• Wenn Rect.Links > XMAX, dann keinen Schnittpunkt.
• Wenn Rect.Recht < XMIN, dann keinen Schnittpunkt.

Dann, wenn die oben war nicht genug, um auszuschließen, Kreuzung, prüfen Sie, ob das Rechteck oberhalb oder unterhalb der Linie Endpunkte:

• Etablieren, die obersten und untersten Y-Werte der Zeile Endpunkte: YMAX und YMIN
• Wenn Rect.Unten > YMAX, dann keinen Schnittpunkt.
• Wenn Rect.Top < YMIN, dann keinen Schnittpunkt.

Dann, wenn die oben war nicht genug, um auszuschließen, Kreuzung, müssen Sie die Gleichung der Linie, die y = m * x + bum zu sehen, ob das Rechteck wird über der Zeile:

• Etablieren, der Linie Y-Wert bei Rect.Links und Rect.Rechts: LINEYRECTLEFT und LINEYRECTRIGHT
• Wenn Rect.Unten > LINEYRECTRIGHT && Rect.Unten > LINEYRECTLEFT, dann keinen Schnittpunkt.

Dann, wenn die oben war nicht genug, um auszuschließen, Kreuzung, die Sie brauchen, um zu überprüfen, ob die rect-unter der Zeile:

• Wenn Rect.Top < LINEYRECTRIGHT && Rect.Top < LINEYRECTLEFT, dann keinen Schnittpunkt.

Dann, wenn Sie hier erhalten:

• Kreuzung.

N. B. ich bin sicher, es gibt eine elegantere algebraische Lösung, aber die Ausführung dieser Schritte geometrisch mit Stift und Papier wird leicht zu Folgen.

Einige ungetestete und nicht kompilierter code zu gehen:

public struct Line
{
    public int XMin { get { ... } }
    public int XMax { get { ... } }

    public int YMin { get { ... } }
    public int YMax { get { ... } }

    public Line(Point a, Point b) { ... }

    public float CalculateYForX(int x) { ... }
}

public bool Intersects(Point a, Point b, Rectangle r)
{
    var line = new Line(a, b);

    if (r.Left > line.XMax || r.Right < line.XMin)
    {
        return false;
    }

    if (r.Top < line.YMin || r.Bottom > line.YMax)
    {
        return false;
    }

    var yAtRectLeft = line.CalculateYForX(r.Left);
    var yAtRectRight = line.CalculateYForX(r.Right);

    if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight)
    {
        return false;
    }

    if (r.Top < yAtRectLeft && r.Top < yAtRectRight)
    {
        return false;
    }

    return true;
}

InformationsquelleAutor der Antwort Johann Gerell

Dieser code hat eine bessere Leistung:

    public static bool SegmentIntersectRectangle(
        double rectangleMinX,
        double rectangleMinY,
        double rectangleMaxX,
        double rectangleMaxY,
        double p1X,
        double p1Y,
        double p2X,
        double p2Y)
    {
        //Find min and max X for the segment
        double minX = p1X;
        double maxX = p2X;

        if (p1X > p2X)
        {
            minX = p2X;
            maxX = p1X;
        }

        //Find the intersection of the segment's and rectangle's x-projections
        if (maxX > rectangleMaxX)
        {
            maxX = rectangleMaxX;
        }

        if (minX < rectangleMinX)
        {
            minX = rectangleMinX;
        }

        if (minX > maxX) //If their projections do not intersect return false
        {
            return false;
        }

        //Find corresponding min and max Y for min and max X we found before
        double minY = p1Y;
        double maxY = p2Y;

        double dx = p2X - p1X;

        if (Math.Abs(dx) > 0.0000001)
        {
            double a = (p2Y - p1Y)/dx;
            double b = p1Y - a*p1X;
            minY = a*minX + b;
            maxY = a*maxX + b;
        }

        if (minY > maxY)
        {
            double tmp = maxY;
            maxY = minY;
            minY = tmp;
        }

        //Find the intersection of the segment's and rectangle's y-projections
        if (maxY > rectangleMaxY)
        {
            maxY = rectangleMaxY;
        }

        if (minY < rectangleMinY)
        {
            minY = rectangleMinY;
        }

        if (minY > maxY) //If Y-projections do not intersect return false
        {
            return false;
        }

        return true;
    }

Können Sie auch überprüfen, wie es funktioniert in JS demo: http://jsfiddle.net/77eej/2/

Wenn Sie zwei Punkte haben und Rect-Sie können diese Funktion aufrufen, so:

    public static bool LineIntersectsRect(Point p1, Point p2, Rect r)
    {
        return SegmentIntersectRectangle(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
    }

InformationsquelleAutor der Antwort Wojtpl2

Einfachsten computational geometry Technik ist nur zu Fuß durch die Segmente des Polygons und sehen, ob es schneidet mit einem von Ihnen, als er muss dann auch die Schnittmenge des Polygons.

Der einzige Nachteil dieser Methode (und auch die meisten CG) ist, dass wir müssen vorsichtig sein, über Grenzfälle. Was, wenn die Linie überquert das Rechteck auf einen Punkt - wir zählen, wie Kreuzung oder nicht? Achten Sie darauf, in Ihrer Umsetzung.

Bearbeiten: Das typische Werkzeug für die Linie-schneidet-segment-Berechnung ist ein LeftOf(Ray, Point) - test, der gibt zurück, ob der Punkt ist auf der linken Seite des Strahls. Gegeben eine Linie l (die wir verwenden, als ray) und ein segment mit Punkte a und b die Linie schneidet das segment, wenn ein Punkt Links und einem Punkt nicht:

(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))

Wieder, Sie müssen aufpassen, für Rand-Fällen, wenn der Punkt auf der Linie, sondern hängt davon ab, wie Sie wollen, um tatsächlich zu definieren Kreuzung.

InformationsquelleAutor der Antwort ceyko