Jak stwierdzić, czy punkt znajduje się po prawej, czy po lewej stronie linii


130

Mam zestaw punktów. Chcę podzielić je na 2 różne zestawy. Aby to zrobić, wybieram dwa punkty ( a i b ) i rysuję między nimi wyimaginowaną linię. Teraz chcę mieć wszystkie punkty, które pozostały z tej linii w jednym zestawie, a te, które są na prawo od tej linii w drugim zestawie.

Jak mogę stwierdzić dla dowolnego punktu z, czy znajduje się on w lewym czy prawym zbiorze? Próbowałem obliczyć kąt między azb - kąty mniejsze niż 180 są po prawej stronie, większe niż 180 po lewej - ale ze względu na definicję ArcCos obliczone kąty są zawsze mniejsze niż 180 °. Czy istnieje wzór do obliczania kątów większych niż 180 ° (lub jakikolwiek inny wzór do wyboru prawej lub lewej strony)?


Jak definiuje się prawą lub lewą stronę? A) patrząc od P1 do P2 lub B) w lewo lub w prawo od linii w płaszczyźnie.
phkahler

2
Aby wyjaśnić, w drugiej części pytania możesz użyć atan2 () zamiast acos () do obliczenia prawidłowego kąta. Jednak użycie produktu krzyżowego jest najlepszym rozwiązaniem tego problemu, jak zauważył Eric Bainville.
dionyziz

Wiele z poniższych rozwiązań nie działa, ponieważ dają przeciwne odpowiedzi, jeśli zamienisz punkty a i b (punkty, których używamy do zdefiniowania naszej linii). Podaję rozwiązanie w Clojure, które najpierw sortuje dwa punkty leksykograficznie przed porównaniem ich z trzecim punktem.
Purplejacket

Odpowiedzi:


202

Użyj znaku wyznacznika wektorów (AB,AM), gdzie M(X,Y)jest punktem zapytania:

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

Jest 0na linii i +1po jednej stronie -1po drugiej stronie.


10
+1 miło, z jedną rzeczą, o której należy pamiętać: błąd zaokrąglania może być problemem, gdy punkt znajduje się bardzo blisko linii. W większości zastosowań nie stanowi to problemu , ale od czasu do czasu gryzie ludzi.
Stephen Canon

16
Jeśli znajdziesz się w sytuacji, w której błąd zaokrąglania w tym teście powoduje problemy, będziesz chciał zapoznać się z „Fast Robust Predicates for Computational Geometry” Jona Shewchuka.
Stephen Canon

14
Dla wyjaśnienia, jest to to samo, co składowa Z iloczynu krzyżowego między linią (ba) i wektorem do punktu z a (ma). W Twojej ulubionej klasie wektorów: pozycja = znak ((ba) .cross (ma) [2])
larsmoa

3
czy zamiana A i B nie pozostawiłaby tej samej linii, ale zmieniłaby znak positions?
Jayen

6
Tak. A, B określa orientację, na przykład „po lewej stronie, gdy stoisz na A i patrzysz na B”.
Eric Bainville

224

Wypróbuj ten kod, który wykorzystuje iloczyn iloczynowy :

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

Gdzie a = punkt linii 1; b = punkt 2 linii; c = punkt do sprawdzenia.

Jeśli formuła jest równa 0, punkty są współliniowe.

Jeśli linia jest pozioma, zwraca prawdę, jeśli punkt znajduje się powyżej linii.


6
Jeśli linia jest pionowa, to?
Tofeeq Ahmad

9
masz na myśli produkt dot?
Baiyan Huang

13
@lzprgmr: Nie, to jest iloczyn krzyżowy, równoważnie wyznacznik macierzy 2D. Rozważmy macierz 2D zdefiniowaną przez wiersze (a, b) i (c, d). Wyznacznikiem jest ad - bc. Powyższa forma polega na przekształceniu prostej reprezentowanej przez 2 punkty w jeden wektor (a, b), a następnie zdefiniowaniu innego wektora za pomocą PointA i PointC w celu uzyskania (c, d): (a, b) = (PointB.x - PointA.x, PointB.y - PointA.y) (c, d) = (PointC.x - PointA.x, PointC.y - PointA.y) Wyznacznik jest więc taki, jak podano w poście.
AndyG

6
Myślę, że nieporozumienie co do tego, czy jest to iloczyn krzyżowy czy skalarny, wynika z tego, że występuje w dwóch wymiarach. Jest to iloczyn krzyżowy w dwóch wymiarach: mathworld.wolfram.com/CrossProduct.html
brianmearns

4
Co jest warte, można to nieco uprościć return (b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x);, ale kompilator prawdopodobnie i tak to optymalizuje.
Nicu Stiurca

44

Patrzysz na znak wyznacznika

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

Będzie dodatnia dla punktów z jednej strony i ujemna dla drugiej (i zero dla punktów na samej linii).


1
Rozszerzając tę ​​odpowiedź, w przypadku, gdy ludzie nie wiedzą, jak wygląda produkt krzyżowy. Następnym wizualnym krokiem jest ((x2-x1) * (y3-y1)) - ((y2 - y1) * (x3-x1))
Franky Rivera

10

Wektor (y1 - y2, x2 - x1) jest prostopadły do ​​linii i zawsze wskazuje w prawo (lub zawsze wskazuje w lewo, jeśli orientacja płaszczyzny jest inna niż moja).

Następnie możesz obliczyć iloczyn skalarny tego wektora i (x3 - x1, y3 - y1)określić, czy punkt leży po tej samej stronie linii co wektor prostopadły (iloczyn skalarny> 0), czy nie.


5

Korzystając z równania linii ab , pobierz współrzędną x na linii o tej samej współrzędnej y, co sortowany punkt.

  • Jeśli punktu x> linii x, punkt znajduje się na prawo od linii.
  • Jeśli punkt x <x linii, punkt znajduje się po lewej stronie linii.
  • Jeśli x punktu == x linii, punkt znajduje się na prostej.

To jest złe, ponieważ jak widać z komentarza Aaginora do pierwszej odpowiedzi, nie chcemy dowiedzieć się, czy punkt znajduje się po lewej, czy po prawej stronie DIRECTED linii AB, tj. Czy stoisz na A i patrzysz w kierunku B, czy jest po lewej czy po prawej stronie?
dionyziz

1
@dionyziz - co? Moja odpowiedź nie wyznacza „kierunku” linii biegnącej przez AB. Moja odpowiedź zakłada, że ​​„lewy” to kierunek -x układu corrdinate. Zaakceptowana odpowiedź zdecydowała się zdefiniować wektor AB i zdefiniować lewy za pomocą iloczynu krzyżowego. Pierwotne pytanie nie precyzuje, co należy rozumieć przez „pozostawiony”.
mbeckish

3
UWAGA: Jeśli zastosujesz to podejście (zamiast rozwiązania obejmującego produkty, które zostało zatwierdzone jako odpowiedź), pamiętaj o pułapce, gdy linia zbliża się do poziomu. Błędy matematyczne rosną i osiągają nieskończoność, jeśli są dokładnie poziome. Rozwiązaniem jest użycie dowolnej osi, która ma większą deltę między dwoma punktami. (A może mniejsza delta ... to jest z głowy.)
ToolmakerSteve

to jest całkowicie to, czego szukałem. nie chcę wiedzieć, czy A jest powyżej, czy poniżej B. chcę tylko wiedzieć, czy jest na lewo (w kierunku ujemnym x) linii!
Jayen

5

Najpierw sprawdź, czy masz pionową linię:

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

Następnie oblicz nachylenie: m = (y2-y1)/(x2-x1)

Następnie należy utworzyć równanie linii z wykorzystaniem punktu postać nachylenia: y - y1 = m*(x-x1) + y1. Ze względu na moje wyjaśnienie, uprość to do postaci przecięcia z nachyleniem (niekonieczne w twoim algorytmie):y = mx+b .

Teraz podłącz (x3, y3)do xa y. Oto pseudokod opisujący szczegółowo, co powinno się stać:

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

3
Niepowodzenie: Obliczenie nachylenia jest nieprawidłowe dla linii pionowych. Niekończące się rzeczy if / else. Nie jestem pewien, czy to właśnie oznaczał OP przez lewy / prawy - jeśli spojrzeć na to obrócony o 90 stopni, przeciąłby ten kod na pół, ponieważ „powyżej” oznaczałoby prawe lub lewe.
phkahler

1
Ta odpowiedź ma kilka problemów. Pionowe linie powodują dzielenie przez zero. Co gorsza, zawodzi, ponieważ nie martwi się, czy nachylenie linii jest dodatnie czy ujemne.

2
@phkahler, naprawiono problem z linią pionową. Zdecydowanie nie porażka za zapomnienie o jednym przypadku testowym, ale dzięki za miłe słowa. „Nieskończone, jeśli / inaczej” ma wyjaśnić teorię matematyczną; nic w pytaniu OP nie wspomina o programowaniu. @woodchips, naprawiono problem z linią pionową. Nachylenie jest zmienną m; Sprawdzam, czy jest pozytywny czy negatywny.
maksim

5

Zaimplementowałem to w Javie i przeprowadziłem test jednostkowy (źródło poniżej). Żadne z powyższych rozwiązań nie działa. Ten kod przechodzi test jednostkowy. Jeśli ktoś znajdzie test jednostkowy, który nie przejdzie, daj mi znać.

Kod: UWAGA: nearlyEqual(double,double)zwraca prawdę, jeśli te dwie liczby są bardzo zbliżone.

/*
 * @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;
}

Oto test jednostkowy:

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

2

Zakładając, że punkty to (Ax, Ay) (Bx, By) i (Cx, Cy), musisz obliczyć:

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

Będzie to równe zero, jeśli punkt C znajduje się na linii utworzonej przez punkty A i B i będzie miał inny znak w zależności od strony. To, która strona to jest, zależy od orientacji twoich współrzędnych (x, y), ale możesz podłączyć wartości testowe dla A, B i C do tego wzoru, aby określić, czy wartości ujemne są po lewej czy po prawej stronie.


2

Chciałem dostarczyć rozwiązanie inspirowane fizyką.

Wyobraź sobie siłę przyłożoną wzdłuż linii i mierzysz moment siły działającej na punkt. Jeśli moment obrotowy jest dodatni (przeciwnie do ruchu wskazówek zegara), to punkt znajduje się „po lewej” linii, ale jeśli moment jest ujemny, punkt jest „po prawej” linii.

Więc jeśli wektor siły jest równy rozpiętości dwóch punktów definiujących linię

fx = x_2 - x_1
fy = y_2 - y_1

sprawdzasz stronę punktu (px,py)na podstawie znaku następującego testu

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

1

w zasadzie myślę, że istnieje rozwiązanie, które jest dużo łatwiejsze i prostsze do przodu, dla dowolnego danego wielokąta, powiedzmy składającego się z czterech wierzchołków (p1, p2, p3, p4), znajdź dwa skrajnie przeciwne wierzchołki w wielokącie, w innym słów, znajdź na przykład najwyższy lewy wierzchołek (powiedzmy p1) i przeciwległy wierzchołek, który znajduje się najbardziej na dole po prawej (powiedzmy). Stąd, biorąc pod uwagę twój punkt testowy C (x, y), teraz musisz dwukrotnie sprawdzić między C i p1 oraz C i p4:

if cx> p1x AND cy> p1y ==> oznacza, że ​​C jest niżej i na prawo od p1, a następnie jeśli cx <p2x AND cy <p2y ==> oznacza, że ​​C jest na górze i na lewo od p4

Podsumowując, C znajduje się wewnątrz prostokąta.

Dzięki :)


1
(1) Odpowiada na inne pytanie niż zostało zadane? Brzmi jak test „obwiedni”, gdy prostokąt jest wyrównany do obu osi. (2) Bardziej szczegółowo: przyjmuje założenie dotyczące możliwych relacji między 4 punktami. Na przykład weź prostokąt i obróć go o 45 stopni, aby uzyskać diament. W diamentie nie ma czegoś takiego jak „lewy górny punkt”. Najbardziej na lewo punkt nie znajduje się ani najwyżej, ani najniżej. I oczywiście 4 punkty mogą tworzyć jeszcze dziwniejsze kształty. Na przykład 3 punkty mogą znajdować się daleko w jednym kierunku, a czwarty punkt w innym. Próbuj dalej!
ToolmakerSteve,

1

@ Odpowiedź AVB w rubinie

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

Jeśli detjest dodatnie, to powyżej, jeśli ujemne, to poniżej. Jeśli 0, to jest na linii.


1

Oto wersja, ponownie wykorzystująca logikę obejmującą wiele produktów, napisana w 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)))))

Przykładowe użycie:

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

To znaczy, że punkt (0, 10) znajduje się na lewo od prostej określonej przez (-3, -1) i (3, 1).

UWAGA: Ta implementacja rozwiązuje problem, którego żadna z pozostałych (jak dotąd) nie rozwiązuje! Porządek ma znaczenie przy przyznawaniu punktów, które wyznaczają linię. To znaczy, w pewnym sensie jest to „linia skierowana”. Więc w powyższym kodzie wywołanie to również daje wynik true:

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

To z powodu tego fragmentu kodu:

(sort line)

Wreszcie, podobnie jak w przypadku innych rozwiązań opartych na iloczynach krzyżowych, rozwiązanie to zwraca wartość logiczną i nie daje trzeciego wyniku dla kolinearności. Ale da wynik, który ma sens, np:

(is-left? [[1 1] [3 1]] [10 1])
false

0

Alternatywnym sposobem zapoznania się z rozwiązaniami oferowanymi przez netters jest zrozumienie implikacji geometrii.

Niech pqr = [P, Q, R] są punktami tworzącymi płaszczyznę podzieloną na 2 boki linią [P, R] . Mamy sprawdzić, czy dwa punkty na płaszczyźnie pqr , A, B, leżą po tej samej stronie.

Dowolny punkt T na płaszczyźnie pqr można przedstawić za pomocą 2 wektorów: v = PQ iu = RQ, jako:

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

Teraz implikacje geometrii:

  1. i + j = 1: T na linii pr
  2. i + j <1: T na Sq
  3. i + j> 1: T na Snq
  4. i + j = 0: T = Q
  5. i + j <0: T na Sq i poza Q.

i+j: <0 0 <1 =1 >1 ---------Q------[PR]--------- <== this is PQR plane ^ pr line

Ogólnie,

  • i + j jest miarą odległości T od Q lub linii [P, R] i
  • znak i + j-1 implikuje boczność T.

Inne znaczenia geometryczne i i j (niezwiązane z tym rozwiązaniem) to:

  • i , j to skalary T w nowym układzie współrzędnych, gdzie v, u to nowe osie, a Q to nowy początek;
  • i , j widać, jak siła pociągowa dla P, B , odpowiednio. Im większe i , tym dalej T jest oddalony od R (większe pociągnięcie od P ).

Wartość i, j można uzyskać rozwiązując równania:

i*vx + j*ux = T'x
i*vy + j*uy = T'y
i*vz + j*uz = T'z

Mamy więc na płaszczyźnie 2 punkty, A, B:

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

Jeśli A, B są po tej samej stronie, będzie to prawdą:

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

Zauważ, że dotyczy to również pytania: Czy A, B są po tej samej stronie płaszczyzny [P, Q, R] , w której:

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

a i + j + k = 1 oznacza, że ​​T jest na płaszczyźnie [P, Q, R], a znak i + j + k-1 implikuje jego boczność. Z tego mamy:

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

i A, B są po tej samej stronie płaszczyzny [P, Q, R] jeśli

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.