Scoprire se un punto si trova all’interno di un rettangolo o meno

Voglio scoprire se un punto si trova all’interno di un rettangolo o meno. Il rettangolo può essere orientato in qualsiasi modo e non è necessario che sia allineato sull’asse.

Un metodo che potevo pensare era quello di ruotare il rettangolo e le coordinate del punto per allineare l’asse del rettangolo e quindi semplicemente testando le coordinate del punto che si trovano all’interno o meno del rettangolo.

Il metodo sopra richiede la rotazione e quindi le operazioni in virgola mobile. C’è un altro modo efficace per farlo?

Come viene rappresentato il rettangolo? Tre punti? Quattro punti? Punto, lati e angolo? Due punti e un lato? Qualcos’altro? Senza saperlo, qualsiasi tentativo di rispondere alla tua domanda avrà solo un valore puramente accademico.

In ogni caso, per ogni poligono convesso (incluso il rettangolo) il test è molto semplice: controlla ciascun bordo del poligono, assumendo che ogni spigolo sia orientato in senso antiorario e verifichi se il punto si trova a sinistra del bordo (a sinistra mezzo piano a mano). Se tutti i bordi superano il test, il punto è all’interno. Se uno fallisce, il punto è all’esterno.

Per verificare se il punto (xp, yp) trova sul lato sinistro del bordo (x1, y1) - (x2, y2) , è necessario build l’equazione di linea per la linea che contiene il bordo. L’equazione è la seguente

 A * x + B * y + C = 0 

dove

 A = -(y2 - y1) B = x2 - x1 C = -(A * x1 + B * y1) 

Ora tutto ciò che devi fare è calcolare

 D = A * xp + B * yp + C 

Se D > 0 , il punto si trova sul lato sinistro. Se D < 0 , il punto si trova sul lato destro. Se D = 0 , il punto è sulla linea.

Tuttavia, questo test, ancora, funziona per qualsiasi poligono convesso, il che significa che potrebbe essere troppo generico per un rettangolo. Un rettangolo potrebbe consentire un test più semplice ... Ad esempio, in un rettangolo (o in qualsiasi altro parallelogramma) i valori di A e B hanno la stessa grandezza ma segni diversi per i bordi opposti (cioè paralleli), che possono essere sfruttati per semplificare il test.

Supponendo che il rettangolo sia rappresentato da tre punti A, B, C, con AB e BC perpendicolare, è sufficiente controllare le proiezioni del punto di interrogazione M su AB e BC:

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

AB è vettore AB, con coordinate (Bx-Ax, By-Ay) e dot(U,V) è il prodotto punto dei vettori U e V: Ux*Vx+Uy*Vy .

Aggiornamento Facciamo un esempio per illustrare questo: A (5,0) B (0,2) C (1,5) e D (6,3). Dalle coordinate del punto, otteniamo AB = (- 5,2), BC = (1,3), punto (AB, AB) = 29, punto (BC, BC) = 10.

Per il punto interrogativo M (4,2), abbiamo AM = (- 1,2), BM = (4,0), punto (AB, AM) = 9, punto (BC, BM) = 4. M è dentro il rettangolo.

Per il punto interrogativo P (6,1), abbiamo AP = (1,1), BP = (6, -1), punto (AB, AP) = - 3, punto (BC, BP) = 3. P non è all'interno del rettangolo, perché la sua proiezione sul lato AB non è all'interno del segmento AB.

 # Pseudo code # Corners in ax,ay,bx,by,dx,dy # Point in x, y bax = bx - ax bay = by - ay dax = dx - ax day = dy - ay if ((x - ax) * bax + (y - ay) * bay < 0.0) return false if ((x - bx) * bax + (y - by) * bay > 0.0) return false if ((x - ax) * dax + (y - ay) * day < 0.0) return false if ((x - dx) * dax + (y - dy) * day > 0.0) return false return true 

Ho preso in prestito dalla risposta di Eric Bainville:

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

Che in javascript assomiglia a questo:

 function pointInRectangle(m, r) { var AB = vector(rA, rB); var AM = vector(rA, m); var BC = vector(rB, rC); var BM = vector(rB, m); var dotABAM = dot(AB, AM); var dotABAB = dot(AB, AB); var dotBCBM = dot(BC, BM); var dotBCBC = dot(BC, BC); return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC; } function vector(p1, p2) { return { x: (p2.x - p1.x), y: (p2.y - p1.y) }; } function dot(u, v) { return ux * vx + uy * vy; } 

per esempio:

 var r = { A: {x: 50, y: 0}, B: {x: 0, y: 20}, C: {x: 10, y: 50}, D: {x: 60, y: 30} }; var m = {x: 40, y: 20}; 

poi:

 pointInRectangle(m, r); // returns true. 

Ecco una codepen per disegnare l'output come test visivo 🙂 http://codepen.io/mattburns/pen/jrrprN

inserisci la descrizione dell'immagine qui

Mi rendo conto che questo è un thread vecchio, ma per chiunque sia interessato a guardare questo da una prospettiva puramente matematica, c’è una discussione eccellente sullo scambio di carte matematiche, qui:

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle

Modifica: ispirato da questo thread, ho messo insieme un semplice metodo vettoriale per determinare rapidamente dove si trova il tuo punto.

Supponiamo di avere un rettangolo con punti a p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) e p4 = (x4, y4), andando in senso orario. Se un punto p = (x, y) si trova all’interno del rettangolo, quindi il prodotto punto (p – p1). (P2 – p1) si troverà tra 0 e | p2 – p1 | ^ 2 e (p – p1). (p4 – p1) si troverà tra 0 e | p4 – p1 | ^ 2. Ciò equivale a prendere la proiezione del vettore p – p1 lungo la lunghezza e la larghezza del rettangolo, con p1 come origine.

Questo potrebbe avere più senso se mostro un codice equivalente:

 p21 = (x2 - x1, y2 - y1) p41 = (x4 - x1, y4 - y1) p21magnitude_squared = p21[0]^2 + p21[1]^2 p41magnitude_squared = p41[0]^2 + p41[1]^2 for x, y in list_of_points_to_test: p = (x - x1, y - y1) if 0 <= p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared: if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared: return "Inside" else: return "Outside" else: return "Outside" 

E questo è tutto. Funzionerà anche per i parallelogrammi.

Se non riesci a risolvere il problema del rettangolo prova a suddividere il problema in problemi più semplici. Dividi il rettangolo in 2 triangoli e verifica se il punto è all’interno di uno di essi, come spiegano qui

In sostanza, si ciclano i bordi su ogni due coppie di linee da un punto. Quindi utilizzare il prodotto incrociato per verificare se il punto si trova tra le due linee utilizzando il prodotto incrociato. Se è verificato per tutti e 3 i punti, il punto è all’interno del triangolo. La cosa buona di questo metodo è che non crea errori di virgola mobile che si verificano se si controllano gli angoli.

 bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) { Point AB = vect2d(A, B); float C1 = -1 * (AB.y*Ax + AB.x*Ay); float D1 = (AB.y*mx + AB.x*my) + C1; Point AD = vect2d(A, D); float C2 = -1 * (AD.y*Ax + AD.x*Ay); float D2 = (AD.y*mx + AD.x*my) + C2; Point BC = vect2d(B, C); float C3 = -1 * (BC.y*Bx + BC.x*By); float D3 = (BC.y*mx + BC.x*my) + C3; Point CD = vect2d(C, D); float C4 = -1 * (CD.y*Cx + CD.x*Cy); float D4 = (CD.y*mx + CD.x*my) + C4; return 0 >= D1 && 0 >= D4 && 0 <= D2 && 0 >= D3;} Point vect2d(Point p1, Point p2) { Point temp; temp.x = (p2.x - p1.x); temp.y = -1 * (p2.y - p1.y); return temp;} 

Punti all'interno del poligono

Ho appena implementato la risposta di AnT usando c ++. Ho usato questo codice per verificare se la coordinazione del pixel (X, Y) si trova all’interno della forma o meno.

Se un punto è all’interno di un rettangolo. Su un aereo. Per coordinate matematiche o geodetiche (GPS)

  • Lascia che il rettangolo sia impostato dai vertici A, B, C, D. Il punto è P. Le coordinate sono rettangolari: x, y.
  • Consente di prolungare i lati del rettangolo. Quindi abbiamo 4 linee rette l AB , l BC , l CD , l DA , o, per carenza, l 1 , l 2 , l 3 , l 4 .
  • Crea un’equazione per ogni io . L’equazione sorta di:

    f i (P) = 0.

P è un punto. Per i punti, che appartengono a l, l’equazione è vera.

  • Abbiamo bisogno delle funzioni sul lato sinistro delle equazioni. Sono f 1 , f 2 , f 3 , f 4 .
  • Si noti che per ogni punto da un lato di l i la funzione f i è maggiore di 0, per i punti dall’altro lato f i è minore di 0.
  • Quindi, se stiamo controllando che P sia nel rettangolo, abbiamo solo bisogno che il p sia sui lati corretti di tutte e quattro le linee. Quindi, dobbiamo controllare quattro funzioni per i loro segni.
  • Ma quale lato della linea è quello giusto, a cui appartiene il rettangolo? È il lato, dove giacciono i vertici del rettangolo che non appartengono alla linea. Per il controllo possiamo scegliere qualcuno dei due vertici non appartenenti.
  • Quindi, dobbiamo controllare questo:

    f AB (P) f AB (C)> = 0

    f BC (P) f BC (D)> = 0

    f CD (P) f CD (A)> = 0

    f DA (P) f DA (B)> = 0

Le diseguaglianze non sono rigide, perché se un punto si trova sul confine, anche questo appartiene al rettangolo. Se non hai bisogno di punti sul confine, puoi modificare le disuguaglianze per quelle severe. Ma mentre lavori in operazioni in virgola mobile, la scelta è irrilevante.

  • Per un punto, cioè nel rettangolo, tutte e quattro le disequazioni sono vere. Si noti che funziona anche per ogni poligono convesso, solo il numero di linee / equazioni sarà diverso.
  • L’unica cosa rimasta è quella di ottenere un’equazione per una linea che attraversa due punti. È un’equazione lineare ben nota. Scriviamolo per una riga AB e il punto P:

    f AB (P) ≡ (x A -x B ) (y P -y B ) – (y A -y B ) (x P -x B )

Il controllo potrebbe essere semplificato – andiamo lungo il rettangolo in senso orario – A, B, C, D, A. Quindi tutti i lati corretti saranno a destra delle linee. Quindi, non dobbiamo confrontarci con il lato in cui si trova un altro vertice. E abbiamo bisogno di controllare una serie di disuguaglianze più brevi:

f AB (P)> = 0

f BC (P)> = 0

f CD (P)> = 0

f DA (P)> = 0

Ma questo è corretto per il normale, matematico (dalla matematica della scuola) insieme di coordinate, dove X è a destra e Y verso l’alto. E per le coordinate geodetiche , come sono usate nel GPS, dove X è in cima, e Y è a destra, dobbiamo girare le disequazioni:

f AB (P) <= 0

f BC (P) <= 0

f CD (P) <= 0

f DA (P) <= 0

Se non sei sicuro delle direzioni degli assi, fai attenzione con questo controllo semplificato – controlla un punto con il posizionamento noto, se hai scelto le disequazioni corrette.

Il modo più semplice a cui pensavo era di proiettare il punto sull’asse del rettangolo. Lasciatemi spiegare:

Se riesci a ottenere il vettore dal centro del rettangolo verso il bordo superiore o inferiore e il bordo sinistro o destro. E hai anche un vettore dal centro del rettangolo al punto, puoi proiettare quel punto sui vettori di larghezza e altezza.

P = vettore punto, H = vettore altezza, W = larghezza vettore

Ottieni il vettore unitario W ‘, H’ dividendo i vettori per la loro grandezza

proj_P, H = P – (P.H ‘) H’ proj_P, W = P – (P.W ‘) W’

A meno che non sbagli, che non penso di essere … (correggimi se sbaglio) ma se l’entity framework della proiezione del tuo punto sul vettore dell’altezza è inferiore alla grandezza del vettore dell’altezza (che è metà dell’altezza del rettangolo) e la grandezza della proiezione del punto sul vettore della larghezza è, quindi si ha un punto all’interno del rettangolo.

Se si dispone di un sistema di coordinate universale, potrebbe essere necessario calcolare i vettori di altezza / larghezza / punto utilizzando la sottrazione vettoriale. Le proiezioni vettoriali sono incredibili! ricordatelo.