Ich möchte herausfinden, ob ein Punkt innerhalb eines Rechtecks liegt oder nicht. Das Rechteck kann in beliebiger Weise ausgerichtet werden und muss nicht achsenausgerichtet sein.
Eine Methode, die ich mir vorstellen konnte, bestand darin, die Rechteck- und Punktkoordinaten zu drehen, um die Rechteckachse auszurichten, und dann einfach die Punktkoordinaten zu testen, ob sie innerhalb der Rechteckkoordinaten liegen oder nicht.
Das obige Verfahren erfordert eine Drehung und damit Gleitkommaoperationen. Gibt es eine andere effiziente Möglichkeit, dies zu tun?
Antworten:
Wie wird das Rechteck dargestellt? Drei Punkte? Vier Punkte? Punkt, Seiten und Winkel? Zwei Punkte und eine Seite? Etwas anderes? Ohne das zu wissen, haben alle Versuche, Ihre Frage zu beantworten, nur rein akademischen Wert.
In jedem Fall ist der Test für jedes konvexe Polygon (einschließlich Rechteck) sehr einfach: Überprüfen Sie jede Kante des Polygons unter der Annahme, dass jede Kante gegen den Uhrzeigersinn ausgerichtet ist, und testen Sie, ob der Punkt links von der Kante liegt (links) -hand halbe Ebene). Wenn alle Kanten den Test bestehen, befindet sich der Punkt im Inneren. Wenn mindestens einer ausfällt, liegt der Punkt außerhalb.
Um zu testen, ob der Punkt
(xp, yp)
auf der linken Seite der Kante liegt(x1, y1) - (x2, y2)
, müssen Sie nur berechnenWenn ja
D > 0
, befindet sich der Punkt auf der linken Seite. Wenn jaD < 0
, befindet sich der Punkt auf der rechten Seite. WennD = 0
, liegt der Punkt auf der Linie.Die vorherige Version dieser Antwort beschrieb eine scheinbar andere Version des Tests auf der linken Seite (siehe unten). Es kann jedoch leicht gezeigt werden, dass derselbe Wert berechnet wird.
... Um zu testen, ob der Punkt
(xp, yp)
auf der linken Seite der Kante liegt(x1, y1) - (x2, y2)
, müssen Sie die Liniengleichung für die Linie erstellen, die die Kante enthält. Die Gleichung lautet wie folgtwo
Jetzt müssen Sie nur noch berechnen
Wenn ja
D > 0
, befindet sich der Punkt auf der linken Seite. Wenn jaD < 0
, befindet sich der Punkt auf der rechten Seite. WennD = 0
, liegt der Punkt auf der Linie.Dieser Test funktioniert jedoch wieder für jedes konvexe Polygon, was bedeutet, dass er für ein Rechteck möglicherweise zu allgemein ist. Ein Rechteck kann einen einfacheren Test ermöglichen ... Zum Beispiel haben in einem Rechteck (oder einem anderen Parallelogramm) die Werte von
A
undB
dieselbe Größe, aber unterschiedliche Vorzeichen für gegenüberliegende (dh parallele) Kanten, die zur Vereinfachung des Tests ausgenutzt werden können .quelle
A'
undB'
durchA'=B
und angegeben werdenB'=-A
. 3. Es macht keinen Sinn,A xp + B yp
beide Kanten zu berechnen. Kombinieren Sie sie daher zu einem einzigen Test. Dann wird Ihr Test für ein Rechteck(v_min < A xp + B yp < v_max) && ( w_min < B xp - A yp < w_max )
.v_min
, etc?v_min
ist der MindestwertA x + B y
für alle Werte im Inneren des Rechtecks (dies ist der Mindestwert, wenn er an den Ecken ausgewertet wird).v_max
ist das entsprechende Maximum. Diew_?
Werte sind die gleichen, aber fürBx - A y
.Angenommen, das Rechteck wird durch drei Punkte A, B, C mit AB und BC senkrecht dargestellt, müssen Sie nur die Projektionen des Abfragepunkts M auf AB und BC überprüfen:
AB
ist der Vektor AB mit Koordinaten (Bx-Ax, By-Ay) unddot(U,V)
ist das Punktprodukt der Vektoren U und V :Ux*Vx+Uy*Vy
.Update . Nehmen wir ein Beispiel, um dies zu veranschaulichen: A (5,0) B (0,2) C (1,5) und D (6,3). Aus den Punktkoordinaten erhalten wir AB = (- 5,2), BC = (1,3), Punkt (AB, AB) = 29, Punkt (BC, BC) = 10.
Für den Abfragepunkt M (4,2) gilt AM = (- 1,2), BM = (4,0), Punkt (AB, AM) = 9, Punkt (BC, BM) = 4. M befindet sich innerhalb des Rechtecks.
Für den Abfragepunkt P (6,1) haben wir AP = (1,1), BP = (6, -1), Punkt (AB, AP) = –3, Punkt (BC, BP) = 3. P befindet sich nicht innerhalb des Rechtecks, da seine Projektion auf der Seite AB nicht innerhalb des Segments AB liegt.
quelle
Ich habe mir Eric Bainvilles Antwort geliehen:
Was in Javascript so aussieht:
z.B:
dann:
Hier ist ein Codepen zum Zeichnen der Ausgabe als visueller Test :) http://codepen.io/mattburns/pen/jrrprN
quelle
mouseover
Ereignis in meinem Projekt. Wenn sich die Maus über dem Punkt befindet, der sich innerhalb des Rechtecks befinden soll, wird ein schwarzer Kreispunkt um die Maus angezeigt, und außerhalb des Rechtecks sollte nichts angezeigt werden. Ich brauche Hilfe, damit es funktioniert, aber ich bin so verwirrt.mouseover
sollte seinmousemove
, nur Tippfehler.quelle
a
,b
undd
. Während drei Punkte theoretisch ein gültiger Weg sind, um ein beliebiges Rechteck darzustellen, ist es in der Praxis im allgemeinen Fall unmöglich, genau in Interger-Koordinaten zu arbeiten. Im Allgemeinen wird ein Parallelogramm erstellt, das dem Rechteck sehr nahe kommt, aber immer noch kein Rechteck ist.Mir ist klar, dass dies ein alter Thread ist, aber für alle, die daran interessiert sind, dies aus einer rein mathematischen Perspektive zu betrachten, gibt es hier einen ausgezeichneten Thread zum Austausch von Mathematikstapeln:
/math/190111/how-to-check-if-a-point-is-inside-a-rectangle
Bearbeiten: Inspiriert von diesem Thread habe ich eine einfache Vektormethode zusammengestellt, mit der Sie schnell feststellen können, wo Ihr Punkt liegt.
Angenommen, Sie haben ein Rechteck mit Punkten bei p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) und p4 = (x4, y4) im Uhrzeigersinn. Wenn ein Punkt p = (x, y) innerhalb des Rechtecks liegt, liegt das Punktprodukt (p - p1). (P2 - p1) zwischen 0 und | p2 - p1 | ^ 2 und (p - p1). (p4 - p1) liegt zwischen 0 und | p4 - p1 | ^ 2. Dies entspricht der Projektion des Vektors p - p1 entlang der Länge und Breite des Rechtecks mit p1 als Ursprung.
Dies kann sinnvoller sein, wenn ich einen äquivalenten Code zeige:
Und das ist es. Es funktioniert auch für Parallelogramme.
quelle
Ich habe gerade AnTs Antwort mit c ++ implementiert. Ich habe diesen Code verwendet, um zu überprüfen, ob die Koordination des Pixels (X, Y) innerhalb der Form liegt oder nicht.
quelle
Wenn Sie das Problem für das Rechteck nicht lösen können, teilen Sie es in einfachere Probleme auf. Teilen Sie das Rechteck in zwei Dreiecke und prüfen Sie, ob sich der Punkt in einem der Dreiecke befindet, wie hier erläutert
Im Wesentlichen durchlaufen Sie die Kanten aller zwei Linienpaare von einem Punkt aus. Verwenden Sie dann das Kreuzprodukt, um mithilfe des Kreuzprodukts zu überprüfen, ob der Punkt zwischen den beiden Linien liegt. Wenn es für alle 3 Punkte überprüft wurde, befindet sich der Punkt innerhalb des Dreiecks. Das Gute an dieser Methode ist, dass sie keine Gleitkommafehler erzeugt, die auftreten, wenn Sie nach Winkeln suchen.
quelle
Wenn sich ein Punkt innerhalb eines Rechtecks befindet. In einem Flugzeug. Für Mathematiker- oder Geodäsiekoordinaten (GPS)
Machen Sie eine Gleichung für jedes l i . Die Gleichung Art von:
f i (P) = 0.
P ist ein Punkt. Für Punkte, die zu l i gehören , ist die Gleichung wahr.
Also müssen wir das überprüfen:
f AB (P) f AB (C)> = 0
f BC (P) f BC (D)> = 0
f CD (P) f CD (A)> = 0
f DA (P) f DA (B)> = 0
Die Ungleichungen sind nicht streng, denn wenn sich ein Punkt am Rand befindet, gehört er auch zum Rechteck. Wenn Sie keine Punkte an der Grenze benötigen, können Sie Ungleichungen gegen strenge ändern. Während Sie in Gleitkommaoperationen arbeiten, ist die Auswahl irrelevant.
Das einzige, was noch übrig ist, ist eine Gleichung für eine Linie zu erhalten, die durch zwei Punkte verläuft. Es ist eine bekannte lineare Gleichung. Schreiben wir es für eine Linie AB und Punkt P:
f AB (P) ≡ (x A x B ) (y P -Y B ) - (y A -y B ) (x P -X B )
Die Prüfung könnte vereinfacht werden - gehen wir im Uhrzeigersinn entlang des Rechtecks - A, B, C, D, A. Dann befinden sich alle richtigen Seiten rechts von den Linien. Wir müssen uns also nicht mit der Seite vergleichen, auf der sich ein anderer Eckpunkt befindet. Und wir müssen eine Reihe kürzerer Ungleichungen überprüfen:
f AB (P)> = 0
f BC (P)> = 0
f CD (P)> = 0
f DA (P)> = 0
Dies gilt jedoch für den normalen Koordinatensatz eines Mathematikers (aus der Schulmathematik), wobei X rechts und Y oben steht. Und für die Geodäsiekoordinaten , wie sie in GPS verwendet werden, wobei X oben und Y rechts ist, müssen wir die Ungleichungen drehen:
f AB (P) <= 0
f BC (P) <= 0
f CD (P) <= 0
f DA (P) <= 0
Wenn Sie mit den Richtungen der Achsen nicht sicher sind, gehen Sie bei dieser vereinfachten Prüfung vorsichtig vor - prüfen Sie, ob ein Punkt mit der bekannten Platzierung vorhanden ist, wenn Sie die richtigen Ungleichungen ausgewählt haben.
quelle
Der einfachste Weg, den ich mir vorgestellt habe, war, den Punkt einfach auf die Achse des Rechtecks zu projizieren. Lassen Sie mich erklären:
Wenn Sie den Vektor von der Mitte des Rechtecks zur oberen oder unteren Kante und zur linken oder rechten Kante erhalten können. Und Sie haben auch einen Vektor von der Mitte des Rechtecks zu Ihrem Punkt. Sie können diesen Punkt auf Ihre Breiten- und Höhenvektoren projizieren.
P = Punktvektor, H = Höhenvektor, W = Breitenvektor
Erhalten Sie den Einheitsvektor W ', H', indem Sie die Vektoren durch ihre Größe dividieren
proj_P, H = P - (P.H ') H' proj_P, W = P - (P.W ') W'
Es sei denn, ich irre mich, was ich nicht glaube ... (Korrigieren Sie mich, wenn ich falsch liege), aber wenn die Größe der Projektion Ihres Punktes auf den Höhenvektor geringer ist als die Größe des Höhenvektors (was ist) die Hälfte der Höhe des Rechtecks) und die Größe der Projektion Ihres Punktes auf den Breitenvektor ist, dann haben Sie einen Punkt innerhalb Ihres Rechtecks.
Wenn Sie ein universelles Koordinatensystem haben, müssen Sie möglicherweise die Vektoren für Höhe, Breite und Punkt mithilfe der Vektorsubtraktion ermitteln. Vektorprojektionen sind erstaunlich! erinnere dich daran.
quelle
In Fortsetzung Matts antworten. Wir müssen die /math/190111/how-to-check-if-a-point-is-inside-a-rectangle/190373#190373 Lösung verwenden, damit es funktioniert
Unten funktioniert nicht
0 <= Punkt (AB, AM) <= Punkt (AB, AB) && 0 <= Punkt (BC, BM) <= Punkt (BC, BC)
Unten funktioniert
0 <= Punkt (AB, AM) <= Punkt (AB, AB) && 0 <= Punkt (AM, AC) <= Punkt (AC, AC)
Sie überprüfen dies, indem Sie unten in die Javascript-Konsole // Javascript-Lösung für dieselbe einfügen
quelle