So erkennen Sie, ob sich ein Punkt auf der rechten oder linken Seite einer Linie befindet

129

Ich habe eine Reihe von Punkten. Ich möchte sie in zwei verschiedene Gruppen 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 von dieser Linie übrig sind, in einem Satz und diejenigen, die direkt von dieser Linie in dem anderen Satz sind, haben.

Wie kann ich für einen bestimmten Punkt z feststellen, ob er sich in der linken oder in der rechten Menge befindet? Ich habe versucht, den Winkel zwischen azb zu berechnen - Winkel kleiner als 180 sind auf der rechten Seite, größer 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)?

Aaginor
quelle
Wie ist rechts oder links definiert? A) in Bezug auf den Blick von P1 nach P2 oder B) links oder rechts von der Linie in der Ebene.
Phkahler
2
Zur Verdeutlichung können Sie im zweiten Teil Ihrer Frage atan2 () anstelle von acos () verwenden, um den richtigen Winkel zu berechnen. Die Verwendung eines Kreuzprodukts ist jedoch die beste Lösung, wie Eric Bainville betonte.
Dionyziz
Viele der folgenden Lösungen funktionieren nicht, weil sie entgegengesetzte Antworten geben, wenn Sie die Punkte a und b austauschen (die Punkte, mit denen wir unsere Linie definieren). Ich gebe in Clojure eine Lösung, die die beiden Punkte zuerst lexikographisch sortiert, bevor sie mit dem dritten Punkt verglichen werden.
Purplejacket

Antworten:

202

Verwenden Sie das Vorzeichen der Determinante von Vektoren (AB,AM), wobei M(X,Y)sich der Abfragepunkt befindet:

position = sign((Bx - Ax) * (Y - Ay) - (By - Ay) * (X - Ax))

Es ist 0auf der Linie und +1auf der einen Seite, -1auf der anderen Seite.

Eric Bainville
quelle
10
+1 schön, wobei eines zu beachten ist: Rundungsfehler können ein Problem sein, wenn der Punkt fast auf der Linie liegt. Für die meisten Anwendungen kein Problem , aber es beißt von Zeit zu Zeit Menschen.
Stephen Canon
16
Sollten Sie sich in einer Situation befinden, in der Rundungsfehler bei diesem Test Probleme verursachen, sollten Sie Jon Shewchuks "Fast Robust Predicates for Computational Geometry" nachschlagen.
Stephen Canon
14
Zur Verdeutlichung ist dies dasselbe wie die Z-Komponente des Kreuzprodukts zwischen der Linie (ba) und dem Vektor zum Punkt von a (ma). In Ihrer bevorzugten Vektorklasse: Position = Zeichen ((ba) .cross (ma) [2])
Larsmoa
3
Würde das Tauschen von A & B nicht die gleiche Linie beibehalten, aber das Vorzeichen von ändern positions?
Jayen
6
Ja. A, B definiert die Ausrichtung wie in "links von A, wenn Sie bei A stehen und B betrachten".
Eric Bainville
223

Probieren Sie diesen Code aus, der ein Kreuzprodukt verwendet :

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;
}

Wobei a = Linienpunkt 1; b = Linienpunkt 2; c = zu prüfender Punkt.

Wenn die Formel gleich 0 ist, sind die Punkte kolinear.

Wenn die Linie horizontal ist, gibt dies true zurück, wenn der Punkt über der Linie liegt.

Jethro
quelle
6
Wenn die Linie dann vertikal ist?
Tofeeq Ahmad
9
Meinst du Punktprodukt?
Baiyan Huang
13
@lzprgmr: Nein, dies ist ein Kreuzprodukt, äquivalent die Determinante einer 2D-Matrix. Betrachten Sie die durch die Zeilen (a, b) und (c, d) definierte 2D-Matrix. Die Determinante ist ad - bc. Die obige Form transformiert eine durch 2 Punkte dargestellte Linie in einen Vektor (a, b) und definiert dann einen anderen Vektor unter Verwendung von PointA und PointC, um (c, d) zu erhalten: (a, b) = (PointB.x - PointA.x, PointB.y - PointA.y) (c, d) = (PointC.x - PointA.x, PointC.y - PointA.y) Die Determinante ist daher genau so, wie sie im Beitrag angegeben ist.
AndyG
6
Ich denke, die Verwirrung darüber, ob dies ein Kreuzprodukt oder ein Punktprodukt ist, liegt darin, dass es zweidimensional ist. Es ist das Kreuzprodukt in zwei Dimensionen: mathworld.wolfram.com/CrossProduct.html
brianmearns
4
Für das, was es wert ist, kann dies leicht vereinfacht werden return (b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x);, aber der Compiler optimiert das wahrscheinlich trotzdem.
Nicu Stiurca
44

Sie betrachten das Zeichen der Determinante von

| x2-x1  x3-x1 |
| y2-y1  y3-y1 |

Es ist positiv für Punkte auf der einen Seite und negativ für die andere Seite (und Null für Punkte auf der Linie selbst).

AVB
quelle
1
Erweitern Sie diese Antwort, falls die Leute nicht wissen, wie das Kreuzprodukt aussieht. Der nächste visuelle Schritt ist ((x2-x1) * (y3-y1)) - ((y2-y1) * (x3-x1))
Franky Rivera
10

Der Vektor (y1 - y2, x2 - x1)ist senkrecht zur Linie und zeigt immer nach rechts (oder immer nach links, wenn sich die Ausrichtung Ihrer Ebene von meiner unterscheidet).

Sie können dann das Punktprodukt dieses Vektors berechnen und (x3 - x1, y3 - y1)feststellen, ob der Punkt auf derselben Seite der Linie liegt wie der senkrechte Vektor (Punktprodukt> 0) oder nicht.

Victor Nicollet
quelle
5

Ermitteln Sie mithilfe der Gleichung der Linie ab die x-Koordinate auf der Linie an derselben y-Koordinate wie der zu sortierende Punkt.

  • Wenn Punkt x> Linie x ist, befindet sich der Punkt rechts von der Linie.
  • Wenn Punkt x <Linie x ist, befindet sich der Punkt links von der Linie.
  • Wenn Punkt x == Linie x ist, befindet sich der Punkt auf der Linie.
mbeckish
quelle
Dies ist falsch, denn wie Sie aus Aaginors Kommentar zur ersten Antwort ersehen können, möchten wir nicht herausfinden, ob der Punkt links oder rechts von der DIREKTIERTEN Linie AB liegt, dh wenn Sie auf A stehen und schauen in Richtung B ist es zu Ihrer Linken oder zu Ihrer Rechten?
Dionyziz
1
@dionyziz - Huh? Meine Antwort weist der Linie durch AB keine "Richtung" zu. Meine Antwort geht davon aus, dass "links" die -x-Richtung des entsprechenden Systems ist. Die akzeptierte Antwort entschied sich dafür, einen Vektor AB zu definieren und links unter Verwendung eines Kreuzprodukts zu definieren. Die ursprüngliche Frage gibt nicht an, was mit "links" gemeint ist.
mbeckish
3
HINWEIS: Wenn Sie diesen Ansatz verwenden (anstelle des produktübergreifenden Ansatzes, der als Antwort genehmigt wurde), müssen Sie sich einer Gefahr bewusst sein, wenn sich die Linie der Horizontalen nähert. Mathematische Fehler nehmen zu und treffen unendlich, wenn sie genau horizontal sind. Die Lösung besteht darin, die Achse zu verwenden, die das größere Delta zwischen den beiden Punkten aufweist. (Oder vielleicht kleineres Delta .. das ist aus meinem Kopf.)
ToolmakerSteve
Das ist genau das, wonach ich gesucht habe. Ich möchte nicht wissen, ob A über oder unter B liegt. Ich möchte nur wissen, ob es links (negative x-Richtung) der Linie liegt!
Jayen
5

Überprüfen Sie zunächst, ob Sie eine vertikale Linie haben:

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

Berechnen Sie dann die Steigung: m = (y2-y1)/(x2-x1)

Erstellen Sie dann eine Gleichung der Linie mit der Punktsteigungsform : y - y1 = m*(x-x1) + y1. Vereinfachen Sie es für meine Erklärung zur Steigungsschnittform (in Ihrem Algorithmus nicht erforderlich) : y = mx+b.

Jetzt (x3, y3)für xund einstecken y. Hier ist ein Pseudocode, der genau beschreibt, 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
Maksim
quelle
3
Fehler: Steigungsberechnung für vertikale Linien ungültig. Endlos wenn / sonst Zeug. Ich bin mir nicht sicher, ob das OP das ist, was mit links / rechts gemeint ist. Wenn Sie es um 90 Grad drehen, wird dieser Code halbiert, da "oben" rechts oder links ist.
Phkahler
1
Diese Antwort hat mehrere Probleme. Vertikale Linien bewirken eine Division durch Null. Schlimmer noch, es schlägt fehl, weil es sich keine Sorgen darüber macht, ob die Steigung der Linie positiv oder negativ ist.
2
@phkahler, das Problem mit der vertikalen Linie wurde behoben. Auf keinen Fall ein Fehler, einen Testfall zu vergessen, aber danke für die freundlichen Worte. "Endlos wenn / sonst" soll die mathematische Theorie erklären; Nichts in der Frage von OP erwähnt die Programmierung. @woodchips, das Problem mit der vertikalen Linie wurde behoben. Die Steigung ist die Variable m; Ich überprüfe, ob es positiv oder negativ ist.
Maksim
5

Ich habe dies in Java implementiert und einen Unit-Test durchgeführt (Quelle unten). Keine der oben genannten Lösungen funktioniert. Dieser Code besteht den Komponententest. Wenn jemand einen Unit-Test findet, der nicht bestanden wird, lassen Sie es mich bitte wissen.

Code: HINWEIS: nearlyEqual(double,double)Gibt true zurück, wenn die beiden Zahlen sehr nahe beieinander liegen.

/*
 * @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 der Unit-Test:

@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));
}
Al Globus
quelle
2

Angenommen, die Punkte sind (Axe, Ay) (Bx, By) und (Cx, Cy), müssen Sie Folgendes berechnen:

(Bx - Axe) * (Cy - Ay) - (By - Ay) * (Cx - Axe)

Dies ist gleich Null, wenn sich der Punkt C auf der Linie befindet, die durch die Punkte A und B gebildet wird, und hat je nach Seite ein anderes Vorzeichen. Welche Seite dies ist, hängt von der Ausrichtung Ihrer (x, y) -Koordinaten ab. Sie können jedoch Testwerte für A, B und C in diese Formel einfügen, um festzustellen, ob negative Werte links oder rechts liegen.

user2154342
quelle
2

Ich wollte eine Lösung anbieten, die von der Physik inspiriert ist.

Stellen Sie sich eine Kraft vor, die entlang der Linie ausgeübt wird, und Sie messen das Drehmoment der Kraft um den Punkt. Wenn das Drehmoment positiv ist (gegen den Uhrzeigersinn), befindet sich der Punkt links von der Linie. Wenn das Drehmoment negativ ist, ist der Punkt rechts von der Linie.

Wenn also der Kraftvektor der Spanne der beiden Punkte entspricht, die die Linie definieren

fx = x_2 - x_1
fy = y_2 - y_1

Sie testen die Seite eines Punktes (px,py)anhand des Vorzeichens des folgenden Tests

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
John Alexiou
quelle
1

Grundsätzlich denke ich, dass es eine Lösung gibt, die viel einfacher und unkomplizierter ist. Für jedes Polygon, das beispielsweise aus vier Eckpunkten besteht (p1, p2, p3, p4), finden Sie die beiden extrem entgegengesetzten Eckpunkte im Polygon in einem anderen Wörter, finden Sie zum Beispiel den Scheitelpunkt oben links (sagen wir p1) und den gegenüberliegenden Scheitelpunkt, der sich höchstens unten rechts befindet (sagen wir mal). Angesichts Ihres Testpunktes C (x, y) müssen Sie nun eine doppelte Überprü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 oben und links von p4 ist

Schlussfolgerung: C befindet sich innerhalb des Rechtecks.

Vielen Dank :)

Mohamed
quelle
1
(1) Beantwortet eine andere Frage als gestellt? Klingt nach einem "Begrenzungsrahmen" -Test, wenn ein Rechteck mit beiden Achsen ausgerichtet ist. (2) Im Detail: Nimmt die möglichen Beziehungen zwischen 4 Punkten an. Nehmen Sie zum Beispiel ein Rechteck und drehen Sie es um 45 Grad, sodass Sie einen Diamanten haben. Es gibt keinen "oberen linken Punkt" in diesem Diamanten. Der Punkt ganz links ist weder ganz oben noch ganz unten. Und natürlich können 4 Punkte noch seltsamere Formen bilden. Zum Beispiel könnten 3 Punkte in einer Richtung weit entfernt sein und der 4. Punkt in einer anderen Richtung. Weiter versuchen!
ToolmakerSteve
1

@ AVBs Antwort in Rubin

det = Matrix[
  [(x2 - x1), (x3 - x1)],
  [(y2 - y1), (y3 - y1)]
].determinant

Wenn detpositiv ist, ist es oben, wenn negativ, ist es unten. Wenn 0, ist es in der Leitung.

boulder_ruby
quelle
1

Hier ist eine Version, die wiederum die produktübergreifende Logik verwendet und in Clojure geschrieben wurde.

(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)))))

Anwendungsbeispiel:

(is-left? [[-3 -1] [3 1]] [0 10])
true

Das heißt, der Punkt (0, 10) liegt links von der durch (-3, -1) und (3, 1) bestimmten Linie.

HINWEIS: Diese Implementierung löst ein Problem, das (bisher) keiner der anderen hat! Die Reihenfolge ist wichtig, wenn Sie die Punkte angeben, die die Linie bestimmen. Das heißt, es ist in gewissem Sinne eine "gerichtete Linie". Mit dem obigen Code erzeugt dieser Aufruf also auch das Ergebnis von true:

(is-left? [[3 1] [-3 -1]] [0 10])
true

Das liegt an diesem Codeausschnitt:

(sort line)

Schließlich gibt diese Lösung wie die anderen produktübergreifenden Lösungen einen Booleschen Wert zurück und liefert kein drittes Ergebnis für die Kollinearität. Aber es wird ein Ergebnis ergeben, das Sinn macht, z.

(is-left? [[1 1] [3 1]] [10 1])
false
Lila Jacke
quelle
0

Eine alternative Möglichkeit, sich ein Bild von den Lösungen zu machen, die von Nettern bereitgestellt werden, besteht darin, einige Implikationen der Geometrie zu verstehen.

Sei pqr = [P, Q, R] Punkte, die eine Ebene bilden, die durch die Linie [P, R] in zwei Seiten unterteilt ist . Wir müssen herausfinden, ob zwei Punkte auf der pqr- Ebene A, B auf derselben Seite liegen.

Jeder Punkt T auf der pqr-Ebene kann mit 2 Vektoren dargestellt werden: v = PQ und u = RQ als:

T '= TQ = i * v + j * u

Nun die Geometrie Implikationen:

  1. i + j = 1: T in der PR-Zeile
  2. i + j <1: T auf Sq
  3. i + j> 1: T auf Snq
  4. i + j = 0: T = Q.
  5. 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

Allgemein,

  • i + j ist ein Maß dafür, wie weit T von Q oder der Linie [P, R] und entfernt ist
  • Das Vorzeichen von i + j-1 impliziert die Nebenwirkung von T.

Die anderen Geometriebedeutungen von i und j (nicht mit dieser Lösung verbunden) sind:

  • i , j sind die Skalare für T in einem neuen Koordinatensystem, wobei v, u die neuen Achsen und Q der neue Ursprung sind;
  • i , j kann als Zugkraft für P bzw. R angesehen werden. Je größer i ist , desto weiter ist T von R entfernt (größerer Zug 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

Wir erhalten also 2 Punkte, A, B in der Ebene:

A = a1 * v + a2 * u B = b1 * v + b2 * u

Wenn A, B auf derselben Seite sind, ist dies wahr:

sign(a1+a2-1) = sign(b1+b2-1)

Beachten Sie, dass dies auch für die Frage gilt: Befinden sich A, B auf derselben Seite der Ebene [P, Q, R] , in der:

T = i * P + j * Q + k * R.

und i + j + k = 1 impliziert, dass T auf der Ebene [P, Q, R] liegt und das Vorzeichen von i + j + k-1 seine Nebenwirkung impliziert. Daraus haben wir:

A = a1 * P + a2 * Q + a3 * R B = b1 * P + b2 * Q + b3 * R

und A, B liegen auf derselben Seite der Ebene [P, Q, R], wenn

sign(a1+a2+a3-1) = sign(b1+b2+b3-1)

Läufeun
quelle