Wie um zu überprüfen, ob Liniensegment schneidet ein Rechteck?

Wenn Sie 2 Punkte, (x1, y1) und (x2, y2), repräsentieren zwei gegenüberliegenden Ecken eines Rechtecks, und 2 andere Punkte, (x3,y3) und (x4,y4), was einem Anteil von 2 Endpunkte eines Liniensegments, wie können Sie prüfen, ob das Liniensegment schneidet das Rechteck?

(The line segment gerade segment enthalten die zwischen den angegebenen Endpunkten. Es ist nicht eine unendliche Länge der Linie definiert durch die beiden Punkte.)

InformationsquelleAutor der Frage omega | 2013-04-24

  1. 24

    Eine sehr einfache Möglichkeit wäre die Verwendung von ein standard-Algorithmus für die überprüfung, ob zwei Liniensegmente sich schneiden um zu überprüfen, ob die Liniensegmente schneidet jede der vier Linien, bilden die Ecken der box. Es ist rechnerisch sehr effizient zu überprüfen, ob zwei Liniensegmente sich schneiden, so würde ich erwarten, dass dies könnte sehr schnell.

    Hoffe, das hilft!

    InformationsquelleAutor der Antwort templatetypedef

  2. 1

    Zu verstehen, wie die Ableitung der Formel für die Prüfung, ob ein line-segment schneidet ein Rechteck, es ist wichtig zu erinnern, die Eigenschaften der vector dot product.

    Stellen die line-segment als Einheit-Vektor und einem Abstand zwischen den line-segment-start-Punkt und den Ursprung. Hier einige C# - code zu berechnen, dass aus der PointF Variablen a_ptStart und a_ptEnd mit einem Vector:

    Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));

    Müssen Sie auch berechnen Sie den senkrechten Vektor und den Abstand vom Ursprung, für das Liniensegment. Drehen ein Einheitsvektor ist um 90°einfach. 

    Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));

    Vorausgesetzt, die vier Ecken des Rechtecks sind in Vector Variablen genannt vecRect1vecRect2vecRect3und vecRect4 berechnen Sie die Abstand zwischen den line-segment und alle vier Ecken des Ziel-bounding-rectangle:

    double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
    Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
    Math.Max(dPerpLineDist3, dPerpLineDist4)));

    Wenn alle Entfernungen positiv sind, oder alle Entfernungen, die negativ sind, dann ist das Rechteck ist auf der einen Seite oder der anderen, so gibt es keinen Schnittpunkt. (Null-Grad-Rechtecke sind als nicht sich mit line-segment.)

    if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
        || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
    /* no intersection */;

    Nächstes Projekt alle vier Ecken der target umschließende Rechteck auf der Linie-segment. Dies gibt uns den Abstand zwischen der Linie der Ursprung und der Projektion des Rechteck-Ecke über die Linie.

    double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
    Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
    Math.Max(dDistLine3, dDistLine4)));

    Wenn das Rechteck die Punkte fallen nicht in die line segment s soweit, dann gibt es keinen Schnittpunkt.

    if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
    /* no intersection */;

    Ich glaube, das ist ausreichend.

    InformationsquelleAutor der Antwort ulatekh

  3. 0

    Erhalten das Skalarprodukt von allen 4 Eckpunkten (die Ecken) mit dem Richtungsvektor der Strecke. Wenn alle 4 Werte dasselbe Vorzeichen haben, dann werden alle Scheitelpunkte liegen auf der gleichen Seite der Linie (nicht die Strecke, sondern die unendliche Linie) und damit die Linie nicht schneidet das Rechteck aus. Dieser Ansatz ist nur für 2D-Kreuzung-Erkennung. Dies kann verwendet werden, um durch filtern die meisten von Ihnen schnell (nur Multiplikationen und Ergänzungen). Sie haben zu tun, die weitere Prüfungen für Liniensegmente anstelle von Linien.

    InformationsquelleAutor der Antwort Srinivasan

Schreibe einen Kommentar