So erkennen Sie, ob sich ein Punkt auf der rechten oder linken Seite einer Linie befindet
https://stackoverflow.com/questions/1560492
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine Reihe von Punkten.Ich möchte sie in zwei verschiedene Sätze aufteilen.Dazu wähle ich zwei Punkte (A Und B) und zeichne eine imaginäre Linie zwischen ihnen.Jetzt möchte ich alle Punkte, die links von dieser Linie liegen, in einem Satz haben und diejenigen, die rechts von dieser Linie liegen, im anderen Satz.
Wie kann ich das für einen bestimmten Punkt feststellen? z ob es im linken oder im rechten Satz ist?Ich habe versucht, den Winkel dazwischen zu berechnen a-z-b – Winkel kleiner als 180 liegen auf der rechten Seite, größere als 180 auf der linken Seite – aber aufgrund der Definition von ArcCos sind die berechneten Winkel immer kleiner als 180°.Gibt es eine Formel zur Berechnung von Winkeln größer als 180° (oder eine andere Formel zur Auswahl der rechten oder linken Seite)?
Lösung
Mit dem Vorzeichen des Determinante von Vektoren (AB,AM), wo M(X,Y) die Abfrage Punkt:
position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))
Es ist 0 auf der Linie, und +1 auf der einen Seite, -1 auf der anderen Seite.
Andere Tipps
Versuchen Sie diesen Code, die Verwendung eines Kreuzprodukt macht:
public bool isLeft(Point a, Point b, Point c){
return ((b.X - a.X)*(c.Y - a.Y) - (b.Y - a.Y)*(c.X - a.X)) > 0;
}
Wo a = Zeile Nummer 1; b = Zeile Nummer 2; c = Punkt zu prüfen, gegen.
Wenn die Formel gleich 0 ist, werden die Punkte kollinear sind.
Wenn die Linie horizontal ist, dann dieser true zurück, wenn der Punkt über der Linie ist.
schauen Sie auf dem Vorzeichen des Determinante
| x2-x1 x3-x1 |
| y2-y1 y3-y1 |
Es wird für Punkte auf der einen Seite positiv und negativ auf der anderen (und Null für Punkte auf der Linie selbst).
Der Vektor (y1 - y2, x2 - x1) ist senkrecht zur Linie, und immer nach rechts zeigt (oder immer nach links zeigt, wenn Sie Ebenenorientierung unterscheidet sich von mir ist).
Sie können dann berechnet das Skalarprodukt dieses Vektors und (x3 - x1, y3 - y1), um zu bestimmen, ob der Punkt liegt auf der gleichen Seite der Leitung wie der senkrechten Vektor (Skalarprodukt> 0) oder nicht.
Ich implementiert diese in Java und lief eine Unit-Test (Quelle unten). Keine der oben genannten Lösungen zu arbeiten. Dieser Code übergibt das Gerät zu testen. Wenn jemand einen Komponententest findet das nicht passieren, lassen Sie es mich wissen.
Code: HINWEIS: nearlyEqual(double,double) gibt true zurück, wenn die beiden Zahlen sind ganz in der Nähe
/*
* @return integer code for which side of the line ab c is on. 1 means
* left turn, -1 means right turn. Returns
* 0 if all three are on a line
*/
public static int findSide(
double ax, double ay,
double bx, double by,
double cx, double cy) {
if (nearlyEqual(bx-ax,0)) { // vertical line
if (cx < bx) {
return by > ay ? 1 : -1;
}
if (cx > bx) {
return by > ay ? -1 : 1;
}
return 0;
}
if (nearlyEqual(by-ay,0)) { // horizontal line
if (cy < by) {
return bx > ax ? -1 : 1;
}
if (cy > by) {
return bx > ax ? 1 : -1;
}
return 0;
}
double slope = (by - ay) / (bx - ax);
double yIntercept = ay - ax * slope;
double cSolution = (slope*cx) + yIntercept;
if (slope != 0) {
if (cy > cSolution) {
return bx > ax ? 1 : -1;
}
if (cy < cSolution) {
return bx > ax ? -1 : 1;
}
return 0;
}
return 0;
}
Hier ist das Gerät zu testen:
@Test public void testFindSide() {
assertTrue("1", 1 == Utility.findSide(1, 0, 0, 0, -1, -1));
assertTrue("1.1", 1 == Utility.findSide(25, 0, 0, 0, -1, -14));
assertTrue("1.2", 1 == Utility.findSide(25, 20, 0, 20, -1, 6));
assertTrue("1.3", 1 == Utility.findSide(24, 20, -1, 20, -2, 6));
assertTrue("-1", -1 == Utility.findSide(1, 0, 0, 0, 1, 1));
assertTrue("-1.1", -1 == Utility.findSide(12, 0, 0, 0, 2, 1));
assertTrue("-1.2", -1 == Utility.findSide(-25, 0, 0, 0, -1, -14));
assertTrue("-1.3", -1 == Utility.findSide(1, 0.5, 0, 0, 1, 1));
assertTrue("2.1", -1 == Utility.findSide(0,5, 1,10, 10,20));
assertTrue("2.2", 1 == Utility.findSide(0,9.1, 1,10, 10,20));
assertTrue("2.3", -1 == Utility.findSide(0,5, 1,10, 20,10));
assertTrue("2.4", -1 == Utility.findSide(0,9.1, 1,10, 20,10));
assertTrue("vertical 1", 1 == Utility.findSide(1,1, 1,10, 0,0));
assertTrue("vertical 2", -1 == Utility.findSide(1,10, 1,1, 0,0));
assertTrue("vertical 3", -1 == Utility.findSide(1,1, 1,10, 5,0));
assertTrue("vertical 3", 1 == Utility.findSide(1,10, 1,1, 5,0));
assertTrue("horizontal 1", 1 == Utility.findSide(1,-1, 10,-1, 0,0));
assertTrue("horizontal 2", -1 == Utility.findSide(10,-1, 1,-1, 0,0));
assertTrue("horizontal 3", -1 == Utility.findSide(1,-1, 10,-1, 0,-9));
assertTrue("horizontal 4", 1 == Utility.findSide(10,-1, 1,-1, 0,-9));
assertTrue("positive slope 1", 1 == Utility.findSide(0,0, 10,10, 1,2));
assertTrue("positive slope 2", -1 == Utility.findSide(10,10, 0,0, 1,2));
assertTrue("positive slope 3", -1 == Utility.findSide(0,0, 10,10, 1,0));
assertTrue("positive slope 4", 1 == Utility.findSide(10,10, 0,0, 1,0));
assertTrue("negative slope 1", -1 == Utility.findSide(0,0, -10,10, 1,2));
assertTrue("negative slope 2", -1 == Utility.findSide(0,0, -10,10, 1,2));
assertTrue("negative slope 3", 1 == Utility.findSide(0,0, -10,10, -1,-2));
assertTrue("negative slope 4", -1 == Utility.findSide(-10,10, 0,0, -1,-2));
assertTrue("0", 0 == Utility.findSide(1, 0, 0, 0, -1, 0));
assertTrue("1", 0 == Utility.findSide(0,0, 0, 0, 0, 0));
assertTrue("2", 0 == Utility.findSide(0,0, 0,1, 0,2));
assertTrue("3", 0 == Utility.findSide(0,0, 2,0, 1,0));
assertTrue("4", 0 == Utility.findSide(1, -2, 0, 0, -1, 2));
}
Mit der Gleichung der Linie ab , erhält die x-Koordinate auf der Linie mit der gleichen y-Koordinate wie der Punkt sortiert werden.
- Wenn Punkt der x> Linie x, der Punkt ist, rechts von der Linie.
- Wenn der Punkt
x
- Wenn Punkt der x == Linie x, der Punkt auf der Linie ist.
Überprüfen Sie zuerst, wenn Sie eine vertikale Linie:
if (x2-x1) == 0
if x3 < x2
it's on the left
if x3 > x2
it's on the right
else
it's on the line
Dann berechnet man die Steigung: m = (y2-y1)/(x2-x1)
erstellen Dann eine Gleichung des Linienpunktes Steigung Formular: y - y1 = m*(x-x1) + y1. Aus Gründen der meine Erklärung, vereinfachen sie Steigungsabschnitt-Form (nicht notwendig in Ihrem Algorithmus). y = mx+b
stecken nun in (x3, y3) für x und y. Hier einig Pseudo-Code detailliert, was passieren soll:
if m > 0
if y3 > m*x3 + b
it's on the left
else if y3 < m*x3 + b
it's on the right
else
it's on the line
else if m < 0
if y3 < m*x3 + b
it's on the left
if y3 > m*x3+b
it's on the right
else
it's on the line
else
horizontal line; up to you what you do
Grundsätzlich denke ich, dass es eine Lösung gibt, die viel einfacher und unkomplizierter ist: Für jedes gegebene Polygon, das beispielsweise aus vier Eckpunkten besteht (p1, p2, p3, p4), finden Sie die beiden äußersten gegenüberliegenden Eckpunkte im Polygon in einem anderen Suchen Sie beispielsweise den Scheitelpunkt ganz oben links (sagen wir p1) und den gegenüberliegenden Scheitelpunkt, der sich ganz unten rechts befindet (sagen wir ).Ausgehend von Ihrem Testpunkt C(x,y) müssen Sie nun eine doppelte Prüfung zwischen C und p1 und C und p4 durchführen:
Wenn cx> p1x und cy> p1y ==> bedeutet, dass C niedriger und rechts von P1 als nächstes ist, wenn cx <p2x und cy <p2y ==> bedeutet, dass C ober und links von P4 ist
Fazit: C liegt innerhalb des Rechtecks.
Danke :)
Unter der Annahme, die Punkte (Ax, Ay) (Bx, By) und (Cx, Cy), müssen Sie berechnen:
(Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
Dies wird gleich Null sein, wenn der Punkt C auf der Linie durch die Punkte A und B gebildet ist, und wird ein anderes Vorzeichen hat, auf der Seite abhängig. Welche Seite das ist, hängt von der Ausrichtung des (x, y) Koordinaten, aber man kann Prüfwerte für A, B und C in diese Formel stecken, um zu bestimmen, ob negative Werte nach links oder nach rechts.
@ AVB Antwort in Ruby
det = Matrix[
[(x2 - x1), (x3 - x1)],
[(y2 - y1), (y3 - y1)]
].determinant
Wenn det positiv ist seine oben, wenn sie negativ ist seine unten. Wenn 0, sein auf der Linie.
Hier ist eine Version, wieder das Kreuzprodukt Logik, geschrieben in Clojure.
(defn is-left? [line point]
(let [[[x1 y1] [x2 y2]] (sort line)
[x-pt y-pt] point]
(> (* (- x2 x1) (- y-pt y1)) (* (- y2 y1) (- x-pt x1)))))
Beispiel Nutzung:
(is-left? [[-3 -1] [3 1]] [0 10])
true
Was ist zu sagen, dass der Punkt (0, 10) ist auf die linke Seite der Linie bestimmt durch (-3, -1) und (3, 1).
Hinweis: Diese Implementierung löst ein Problem, dass keiner der anderen (bisher) tut! Auftragsangelegenheiten , wenn die Punkte geben, die die Linie bestimmen. Das heißt, es ist eine „gerichtete Linie“, in einem gewissen Sinne. Also mit dem obigen Code, dieser Aufruf erzeugt auch das Ergebnis der true:
(is-left? [[3 1] [-3 -1]] [0 10])
true
Das ist, weil dieser Code-Snippet:
(sort line)
Schließlich, wie bei den anderen Kreuzprodukt basierten Lösungen, gibt diese Lösung eine boolean, und nicht ein drittes Ergebnis für Kollinearität geben. Aber es wird ein Ergebnis geben, die Sinn macht, z.
(is-left? [[1 1] [3 1]] [10 1])
false
wollte ich mit einer Lösung von Physik inspiriert schaffen.
Stellen Sie sich eine Kraft, die entlang der Linie angelegt und Sie werden das Drehmoment der Kraft um den Punkt zu messen. Wenn das Drehmoment positiv ist (gegen den Uhrzeigersinn), dann ist der Punkt, auf den „links“ von der Linie, aber wenn das Drehmoment negativ ist der Punkt ist die „richtige“ der Linie.
Also, wenn der Kraftvektor ist gleich der Spannweite der beiden Punkte definiert, die Zeile
fx = x_2 - x_1
fy = y_2 - y_1
Sie testen, für die Seite eines Punktes (px,py) auf dem Schild des folgenden Tests auf Basis
var torque = fx*(py-y_1)-fy*(px-x_1)
if torque>0 then
"point on left side"
else if torque <0 then
"point on right side"
else
"point on line"
end if
Eine andere Möglichkeit, um ein Gefühl von Lösungen des Erhaltens von Netzfänger vorgesehen ist ein wenig Geometrie Auswirkungen zu verstehen.
Let PQR = [P, Q, R] sind Punkte, die eine Ebene bildet, die in 2 durch die Linie Seiten [P, R] unterteilt ist. Wir sind um herauszufinden, ob zwei Punkte auf PQR Ebene, A, B, ist auf der gleichen Seite.
Jeder Punkt T auf pqr Ebene kann mit 2-Vektoren dargestellt werden: v = PQ und u = RQ, wie:
T‘= T-Q = i * v + j * u
Nun ist die Geometrie Auswirkungen:
- i + j = 1: T auf pr Zeile
- i + j <1: T auf Sq
- i + j> 1: T auf Snq
- i + j = 0: T = Q
- i + j <0: T auf Sq und darüber hinaus Q.
i+j: <0 0 <1 =1 >1
---------Q------[PR]--------- <== this is PQR plane
^
pr line
In der Regel
- i + j ist ein Maß dafür, wie weit T weg von Q oder line [P, R] und
- das Zeichen i + j-1 impliziert t Sie.
Die andere Geometrie Wertigkeiten von i und j (nicht zu dieser Lösung bezogen) ist:
- i , j die Skalare für T in einem neuen Koordinatensystem sind, wobei v, u sind die neuen Achsen und Q ist der neue Ursprung;
- i , j als Zugkraft für P, R zu sehen ist. Je größer i , je weiter weg von T ist R (größere Pull von P ).
Der Wert von i, j kann durch Lösen der Gleichungen erhalten werden:
i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z
So sind wir 2 Punkte gegeben, A, B auf der Ebene:
A = a1 * v + a2 * u
B = b1 * v + b2 * u
Wenn A, B auf der gleichen Seite ist, wird dies wahr sein:
sign(a1+a2-1) = sign(b1+b2-1)
Beachten Sie, dass dies gilt auch für die Frage: sind A, B in der gleichen Seite der Ebene [P, Q, R] , wobei:
T = i * P + j * Q + k * R
und i + j + k = 1 impliziert, daß T auf der Ebene [P, Q, R] und das Vorzeichen von i + j + k-1 impliziert seine Einander. Daraus haben wir:
A = a1 * P + a2 * Q + a3 * R
B = b1 * P + b2 * Q + b3 * R
und A, B sind auf der gleichen Seite der Ebene [P, Q, R], wenn
sign(a1+a2+a3-1) = sign(b1+b2+b3-1)
