Wie überprüft man, ob das Liniensegment ein Rechteck schneidet?

Wenn Sie zwei Punkte (x1, y1) und (x2, y2) haben, die zwei entgegengesetzte Ecken eines Rechtecks darstellen, und zwei weitere Punkte (x3, y3) und (x4, y4), die zwei Endpunkte darstellen Wie können Sie überprüfen, ob ein Liniensegment das Rechteck schneidet?Wie überprüft man, ob das Liniensegment ein Rechteck schneidet?

(Das Liniensegment ist nur das Segment zwischen den angegebenen Endpunkten enthalten ist. Es ist nicht eine unendliche Länge Linie durch diese beiden Punkte definiert.)

Quelle

2013-04-24 omega

möglich Duplikat von [Linien-Rechteck-Kollisionserkennung] (http://stackoverflow.com/questions/2368211/line-rectangle-collision-detection) – templatetypedef

Ihre Linie heißt Segment – kassak

Eine sehr einfache Möglichkeit wäre, a standard algorithm for checking whether two line segments intersect zu verwenden, ob die Leitung überprüfen Segmente schneidet eines der vier Liniensegmente, die die Ecken der Box bilden. Es ist rechnerisch sehr effizient zu überprüfen, ob sich zwei Liniensegmente schneiden, also würde ich erwarten, dass dies sehr schnell laufen könnte.

Hoffe, das hilft!

Quelle

2013-04-24 23:11:30 templatetypedef

+21

Es gibt einen Fall, der nicht von behandelt wird Die Idee von @templatetypedef: Der Fall, in dem die beiden Endpunkte des Liniensegments innerhalb des Rechtecks liegen. Aber dieser Fall ist leicht zu überprüfen: 'x1 lrineau

@lrineau Außer wenn es im Rechteck enthalten ist, schneidet es das Rechteck nicht. –

@MarkPing: Das hängt davon ab, ob Sie das Rechteck wie es ist oder nur die Grenze davon betrachten. – lrineau

Erhalten Sie das Skalarprodukt aller 4 Ecken (die Ecken des Rechtecks) mit dem Richtungsvektor des Liniensegments. Wenn alle 4 Werte des gleichen Vorzeichens haben, dann liegen alle Scheitelpunkte auf der gleichen Seite der Linie (nicht das Liniensegment, sondern die unendliche Linie) und daher schneidet die Linie das Rechteck nicht. Dieser Ansatz ist nur für die 2D-Kreuzungsdetektion geeignet. Dies kann verwendet werden, um die meisten von ihnen schnell zu filtern (nur mit Multiplikationen und Additionen). Sie müssen weitere Prüfungen für Liniensegmente anstelle von Linien durchführen.

Quelle

2015-06-04 19:27:12 Srinivasan

Ich habe darüber nachgedacht ... Es ist nicht korrekt. Alle Scheitelpunkte können auf der gleichen Seite der Linie liegen, aber immer noch Punktprodukte mit entgegengesetzten Vorzeichen erzeugen. Auch die Verwendung des Richtungsvektors berücksichtigt nicht, wo die Linie tatsächlich ist. Man kann zwei parallele Linien wählen: eine, die das Rechteck schneidet und eine, die das nicht tut. Da ihre Richtung die gleiche ist, werden die vier Punktprodukte die gleichen Werte für beide Linien erzeugen, was dem Satz klar widerspricht. Ich muss -1, obwohl die ursprüngliche Idee war nett. –

Um zu verstehen, wie man die Formel zum Testen, ob ein Liniensegment ein Rechteck schneidet, herleitet, ist es wichtig, sich an die Eigenschaften des vector dot product zu erinnern.

Stellen Sie das Liniensegment als Einheitsvektor und einen Abstand zwischen dem Startpunkt des Liniensegments und dem Ursprung dar. Hier einige C# -Code zu berechnen, dass von den PointF Variablen a_ptStart und a_ptEnd unter Verwendung einer 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));

Sie werden auch die senkrechte Vektor berechnen müssen, und seine Entfernung vom Ursprung, für das Liniensegment. Ein Einheitsvektor um 90 ° zu drehen ist easy.

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

die vier Ecken des Rechtecks Unter der Annahme, sind in Vector Variablen namens vecRect1, vecRect2, vecRect3 und vecRect4, berechnen die distance zwischen dem Liniensegment und alle vier Ecken des Begrenzungsrechteck des Ziels:

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 negativ sind, befindet sich das Rechteck auf der einen oder anderen Seite der Linie, also gibt es keinen Schnittpunkt. (Zero-Ausmaß Rechtecken werden als nicht mit einem Liniensegment zu schneiden.)

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

nächstes Projekt aller vier Ecken des Begrenzungsrechtecks des Ziels auf das Liniensegment. Dies gibt uns den Abstand zwischen dem Ursprung der Linie und der Projektion der Rechteckecke auf dieser Linie.

Wenn die Punkte des Rechtecks nicht in die Ausdehnung des Liniensegments fallen, dann gibt es keinen Schnittpunkt.

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

Ich glaube, dass ausreichend ist.

Quelle

2016-06-03 18:17:45 ulatekh

verallgemeinert diese Methode zu 3D? Angenommen, wir haben dieses Rechteck normal. Mit der Segmentrichtung und der Normalen können wir die dritte Richtung erhalten, die senkrecht zu beiden ist, so dass wir 'vecPerpLine' berechnen können. Rest verwendet Punktprodukte und Entfernungssubtraktionen. Das macht Sinn für mich. Jemand kann meine Idee kommentieren? – kotu

Wie überprüft man, ob das Liniensegment ein Rechteck schneidet?

Antwort

Verwandte Themen