wie kann man feststellen, ob ein Punkt in einem Rechteck liegt? [Duplikat]

Wählen Sie einen Punkt, der definitiv außerhalb des Rechtecks ​​liegt. Dann erstellen Sie ein Segment von diesem Punkt zu dem fraglichen Punkt. Lösen Sie die linearen Gleichungen für Schnittpunkte zwischen diesem Segment und den Segmenten, aus denen das Rechteck besteht. Wenn Sie genau einen Schnittpunkt erhalten, befindet sich der Punkt innerhalb des Rechtecks. Ansonsten (0 oder 2 Kreuzungen) ist es draußen.

Dies ist trivial, um praktisch jedes Polygon zu erweitern - eine ungerade Anzahl von Schnittpunkten bedeutet, dass der Punkt innerhalb des Polygons liegt, und eine gerade Zahl bedeutet, dass er außerhalb liegt.

Bearbeiten: Es ist vielleicht nicht sofort offensichtlich, also betone ich, dass der Punkt, den wir außerhalb des Rechtecks ​​(Polygons) auswählen, völlig willkürlich ist. Wir können den Punkt auswählen, den wir wollen, solange wir sicher sind, dass er außerhalb des Polygons liegt. Um unsere Berechnungen einfach zu halten, wählen wir (P , unendlich) (wobei P x die x-Koordinate des Punktes P ist, der wir sind) Testen) - das heißt, was wir erschaffen, ist im Wesentlichen ein vertikaler Strahl. Das vereinfacht das Testen ein bisschen, weil wir nur gegen einen Endpunkt testen müssen, um eine Kreuzung zu finden. Es vereinfacht auch das Lösen der linearen Gleichungen bis zu dem Punkt, an dem sie kaum mehr als lineare Gleichungen zu lösen sind. Wir müssen wirklich nur die Y-Koordinate für die Linie bei P _x berechnen und sehen, ob sie größer als P ist. Das Lösen der linearen Gleichung ergibt sich somit zu:

1. überprüft, ob dieser X-Wert innerhalb des Bereichs von X-Werten für das Segment
liegt
2. falls ja, schließe den X-Wert in die Gleichung der Zeile
ein
3. Testen, ob der resultierende Y-Wert größer als P y

Wenn diese passieren, haben wir eine Kreuzung. Beachten Sie auch, dass die Tests parallel ausgeführt werden können (praktisch, wenn wir dies auf einer parallelen Hardware wie einer GPU machen).

Einfache Lösung, die in N Dimensionen für konvexe Polyeder funktioniert, von denen ein 2-dimensionales Rechteck ein Sonderfall ist:

1. Repräsentiert das Polyeder als Schnittpunkt von Halbräumen, die jeweils durch einen Einheitsnormalenvektor und den Abstand der Oberflächenhyperebene vom Ursprung entlang der Normalen definiert sind.
2. Nimm für jedes dieser Halbräume das Skalarprodukt des fraglichen Punktes mit dem definierenden Normalenvektor. Der Punkt befindet sich genau dann im Halbraum, wenn das Skalarprodukt kleiner als [oder gleich dem definierenden Abstand ist.
3. Der Punkt befindet sich genau dann innerhalb des Polyeders, wenn er sich in jedem der Halbräume befindet.

Bei einem Rechteck, das als gegen den Uhrzeigersinn gerichtete Folge von Kanten definiert ist, wird in Schritt 1 die Kanten jeweils um 90 Grad im Uhrzeigersinn gedreht, um die Normalen zu erhalten. Anschließend wird die Normale mit der Linie mit der Kante geschnitten Ursprung.

Vorausgesetzt, Schritt 1 ist abgeschlossen, dauert das Testen eines Punktes höchstens 8 Multiplikationen, 4 Additionen und 4 Vergleiche.

Wenn Sie möchten, können Sie den Prozess ein wenig optimieren, da Sie Rechtecke haben (und somit entgegengesetzte Seiten entgegengesetzte Normalen haben). Jetzt betrachten Sie nur 2 Normalen statt 4 und eine Reihe von Skalarproduktwerten, die Punkte angeben, die zwischen den gegenüberliegenden Seiten liegen. So, jetzt sind Sie auf 4 Multiplikationen, 2 Additionen und 4 Vergleiche.

Sie können auch Glück haben, wenn der erste Test, den Sie machen, zeigt, dass der Punkt außerhalb des Rechtecks ​​liegt. In diesem Fall sind es nur 2 Multiplikationen, 1 Addition und 1-2 Vergleiche.

Dies ist bei weitem nicht die beste Lösung ... Aber wenn Sie die Punkte in fortlaufender Reihenfolge haben, rufen Sie sie a , b , c und d mit einem x und ay-Feld, Sie können verwende das Kreuzprodukt der Vektoren zwischen deinem Punkt p und jedem der aufeinanderfolgenden Paare.

Wenn Sie immer das gleiche Vorzeichen für das Ergebnis erhalten (d. h. alle sind positiv oder alle negativ), befinden Sie sich innerhalb des Rechtecks. Sonst bist du draußen.

Definieren Sie ein neues Koordinatensystem mit zwei Rechteckseiten als Einheitsvektoren und transformieren Sie die Koordinaten des Punktes in das neue Koordinatensystem. Wenn beide Koordinaten zwischen 0 und 1 sind, ist es innen.

In Gleichungen (vorausgesetzt, A, B, C, D sind Ecken des Rechtecks, P ist der Punkt, _x und _y sind die x- und y-Komponenten):

Löse für x und y und überprüfe, ob sie zwischen 0 und 1 liegen

Geschrieben als lineares Gleichungssystem (A, B, C, D, P sind Vektoren der Länge 2):

Das Lösen ist einfach, da es nur zwei Dimensionen hat und Sie sicher sein können, dass Sie nicht singulär sind.

Sie können Ihr Bezugssystem drehen und verschieben, so dass es mit der Position und Drehung des Rechtecks ​​übereinstimmt. Jetzt geht es nur noch um einfache Vergleiche zwischen Koordinaten. Dies ist eher eine mathematische Methode, also nicht die schnellste (Bellieve @Platinum Azure ist eine)

Da das Rechteck gedreht werden könnte, sollten Sie einen Algorithmus in Betracht ziehen, mit dem festgestellt wird, ob ein Punkt liegt innerhalb eines konvexen Polygons .

Sie können auch den Rotationswinkel des Rechtecks ​​berechnen und dann sowohl das Rechteck als auch den Punkt transformieren, um das Rechteck axial auszurichten. Überprüfen Sie dann, ob der transformierte Punkt innerhalb des axial ausgerichteten Rechtecks ​​liegt.

Es ist Teil der klassischen Clipping-Algorithmen, ob ein Punkt in einer begrenzten Region wie einem Rechteck liegt. Siehe die Wikipedia-Artikel auf Clipping und Linienausschnitt , um mehr darüber zu erfahren.

Folgen Sie dem Geist von @Jerry Sarg: Erstellen Sie Segmente von rechteckigen Ecken zu dem fraglichen Punkt. Lösen Sie die linearen Gleichungen. Steigung ist tan(a) . Summiere alle seq arctangents diff, wenn es 2 * PI ist und jedes diff & lt; Der PI - Punkt befindet sich innerhalb des Rechtecks.

Bearbeiten Wahrscheinlich reicht es, nach jedem sequentiellen Unterschied zu suchen & lt; Pi ...