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

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

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.

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.

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

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.

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.

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

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

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.

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

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

@ 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.

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

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)