Come sapere se un punto si trova sul lato destro o sinistro di una linea

Question

Ho una serie di punti.Voglio separarli in 2 set distinti.Per fare ciò, scelgo due punti (UN E B) e tracciare una linea immaginaria tra di loro.Ora voglio avere tutti i punti a sinistra di questa linea in un insieme e quelli a destra di questa linea nell'altro insieme.

Come posso dirlo per un dato punto z se è nel set di sinistra o di destra?Ho provato a calcolare l'angolo tra a-z-b – gli angoli inferiori a 180 si trovano sul lato destro, maggiori di 180 sul lato sinistro – ma a causa della definizione di ArcCos, gli angoli calcolati sono sempre inferiori a 180°.Esiste una formula per calcolare gli angoli maggiori di 180° (o qualche altra formula per scegliere il lato destro o sinistro)?

Answer 1

Con il segno del determinante di vettori (AB,AM), dove M(X,Y) è il punto di query:

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

È 0 sulla linea, e +1 da un lato, -1 sull'altro lato.

Answer 2

Prova questo codice che fa uso di un prodotto vettoriale :

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

Dove un = linea punto 1; b = linea del punto 2; c = punto per controllare contro.

Se la formula è uguale a 0, i punti sono collineari.

Se la linea è orizzontale, allora questo restituisce true se il punto è al di sopra della linea.

Answer 3

Si guarda il segno del determinante di

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

Sarà positivo per punti su un lato, e negativo sull'altro (e zero per punti sulla linea stessa).

Answer 4

Il vettore (y1 - y2, x2 - x1) è perpendicolare alla linea, e sempre destro di puntamento (o sempre punta a sinistra, se piano di orientamento è diverso dal mio).

È possibile quindi calcolare il prodotto scalare di tale vettore e (x3 - x1, y3 - y1) per determinare se il punto giace sullo stesso lato della linea come vettore perpendicolare (dot prodotto> 0) o meno.

Answer 5

ho implementato questo in Java ed ho fatto funzionare una prova di unità (fonte qui di seguito). Nessuno dei precedenti lavori soluzioni. Questo codice passa il test di unità. Se qualcuno trova una prova di unità che non passa, per favore fatemelo sapere.

Codice: NOTA:. nearlyEqual(double,double) restituisce true se i due numeri sono molto vicini

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

Ecco la prova di unità:

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

Answer 6

Utilizzando le href="http://en.wikipedia.org/wiki/Linear_equation" della linea ab , ottenere il x-coordinate sulla linea allo stesso coordinata y come punto da smistare.

• Se di punto x> x della linea, il punto è a destra della linea.
• Se il punto di x
• Se x del punto == x della linea, il punto è sulla linea.

Answer 7

In primo luogo verificare se si dispone di una linea verticale:

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

Quindi, calcolare la pendenza: m = (y2-y1)/(x2-x1)

Quindi creare un'equazione della linea tramite il modulo pendenza punto: y - y1 = m*(x-x1) + y1. Per il bene della mia spiegazione, semplificare al modulo di pendenza-intercetta (non è necessario nel vostro algoritmo): y = mx+b

.

Ora collegare (x3, y3) per x e y. Ecco alcuni pseudocodice dettagliare ciò che dovrebbe accadere:

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

Answer 8

in fondo, credo che ci sia una soluzione che è molto più facile e dritto in avanti, per ogni poligono, diciamo costituito da quattro vertici (P1, P2, P3, P4), trovare i due vertici opposti estremi nel poligono , in altre parole, trovare l'ad esempio il vertice più alto a sinistra (diciamo P1) e il vertice opposto che si trova al più basso a destra (diciamo). Quindi, dato il vostro punto di prova C (x, y), ora devi fare doppio controllo tra C e p1 e C e P4:

se cx> P1X e Cy> P1Y ==> significa che C è più bassa e del diritto di p1 Il prossimo se cx significa che C è superiore ed a sinistra della p4

conclusione, C è all'interno del rettangolo.

Grazie :)

Answer 9

Supponendo che i punti sono (Ax, Ay) (Bx, By) e (Cx, Cy), è necessario calcolare:

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

Questo sarà pari a zero se il punto C è sulla linea formata dai punti A e B, ed avrà un segno diverso a seconda del lato. Che laterale, questa dipende dall'orientamento del (x, y) coordinate, ma è possibile inserire valori di prova per A, B e C in questa formula per determinare se i valori negativi sono verso sinistra o verso destra.

Answer 10

La risposta di @AVB in rubino

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

Se det se è positivo è sopra, se è negativo è sotto.Se 0, è sulla linea.

Answer 11

Ecco una versione, sempre utilizzando la logica del prodotto croce, scritto 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)))))

Esempio di utilizzo:

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

Vale a dire che il punto (0, 10) è a sinistra della linea determinata da (-3, -1) e (3, 1).

Nota: Questa implementazione risolve un problema che nessuno degli altri (finora) fa! questioni Ordine quando dare i punti che determinano la linea. Vale a dire, si tratta di una "linea diretta", in un certo senso. Quindi, con il codice di cui sopra, questa invocazione produce anche il risultato di true:

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

Questo perché di questo frammento di codice:

(sort line)

Infine, come con le altre soluzioni basate prodotto incrociato, questa soluzione ritorna un valore booleano, e non dà un terzo risultato per collinearità. Ma vi darà un risultato che ha un senso, per esempio:.

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

Answer 12

Ho voluto fornire una soluzione ispirata dalla fisica.

Immaginate una forza applicata lungo la linea e si sta misurando la coppia della forza circa il punto. Se la coppia è positivo (in senso antiorario), allora il punto è la "sinistra" della linea, ma se la coppia è negativo il punto è il "diritto" della linea.

Quindi, se il vettore forza è uguale la durata dei due punti che definiscono la linea

fx = x_2 - x_1
fy = y_2 - y_1

si prova per il lato di un punto (px,py) basata sul segno dei seguenti test

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

Answer 13

Un modo alternativo di ottenere una sensazione di soluzioni fornite da pescherecci con reti è quello di capire un po implicazioni geometria.

Let pqr = [P, Q, R] sono punti che formano un piano che è diviso in 2 parti per linea [P, R] . Siamo per scoprire se due punti su pqr piano, A, B, sono sullo stesso lato.

Qualsiasi punto T sul piano pqr può essere rappresentato con 2 vettori: v = PQ e u = RQ, come:

T'= T-Q = i * v + j * U

Ora le implicazioni geometria:

1. i + j = 1: T on line pr
2. i + j <1: T sul Sq
3. i + j> 1: T sul SNQ
4. i + j = 0: T = Q
5. i + j <0: T sul Sq e oltre Q.

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

In generale,

• i + j è una misura di quanto T è fuori Q o linea [P, R] e
• il segno del i + j-1 implica sideness T.

Gli altri significati geometria di i e j (non legati a questa soluzione) sono:

• i , j sono scalari per T in un nuovo sistema di coordinate in cui v, u sono i nuovi assi e Q è la nuova origine;
• i , j può essere visto come trazione P, R , rispettivamente. Il grande i , il T più è fuori R (pull grande da P ).

Il valore di i, j può essere ottenuto risolvendo le equazioni:

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

Così ci viene dato 2 punti, A, B sul piano:

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

Se A, B sono dalla stessa parte, questo sarà vero:

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

Notare che si applica anche alla domanda: sono A, B sullo stesso lato del piano [P, Q, R] , in cui:

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

e i + j + k = 1 implica che T sia sul piano [P, Q, R] e il segno di i + j + k-1 implica la sua sideness. Da questo abbiamo:

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

e A, B sono sullo stesso lato del piano [P, Q, R] se

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