Determina se due rettangoli si sovrappongono l’un l’altro?

Sto provando a scrivere un programma C ++ che prende i seguenti input dall’utente per build rettangoli (tra 2 e 5): altezza, larghezza, x-pos, y-pos. Tutti questi rettangoli esisteranno parallelamente alla xe all’asse y, cioè tutti i loro bordi avranno pendenze di 0 o infinito.

Ho cercato di implementare ciò che è menzionato in questa domanda, ma non ho molta fortuna.

La mia attuale implementazione fa la seguente:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1 // point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on... // Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2 // rotated edge of point a, rect 1 int rot_x, rot_y; rot_x = -arrRect1[3]; rot_y = arrRect1[2]; // point on rotated edge int pnt_x, pnt_y; pnt_x = arrRect1[2]; pnt_y = arrRect1[3]; // test point, a from rect 2 int tst_x, tst_y; tst_x = arrRect2[0]; tst_y = arrRect2[1]; int value; value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y)); cout << "Value: " << value; 

Tuttavia non sono abbastanza sicuro se (a) ho implementato l’algoritmo che ho collegato correttamente, o se ho fatto esattamente come interpretarlo?

Eventuali suggerimenti?

 if (RectA.Left < RectB.Right && RectA.Right > RectB.Left && RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

oppure, usando le coordinate cartesiane

(Con X1 come coordente sinistro, X2 come coord destro, crescente da sinistra a destra e Y1 come coord superiore, e Y2 come cordone inferiore, crescente dal basso verso l'alto) ...

 if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 && RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

NOTA: PER TUTTI QUINDI UTENTI CON AUTORITÀ DI MODIFICA. PER FAVORE, FERMATEVI FIDDLING CON QUESTO.

Supponiamo che tu abbia Rect A e Rect B. Proof sia per contraddizione. Ognuna delle quattro condizioni garantisce che non possa esistere alcuna sovrapposizione :

  • COND1. Se il margine sinistro di A è a destra del margine destro del B, - quindi A è Totalmente a destra di B
  • Cond2. Se il lato destro di A è a sinistra del margine sinistro di B, - quindi A è Totalmente a sinistra di B
  • Cond3. Se il margine superiore di A è sotto il bordo inferiore di B, - allora A è Totalmente sotto B
  • Cond4. Se il margine inferiore di A è sopra il margine superiore di B, - allora A è Totalmente sopra B

Quindi la condizione per Non-Overlap è

  Cond1 o Cond2 o Cond3 o Cond4 

Pertanto, una condizione sufficiente per Sovrapposizione è l'opposto.

  Non (Cond1 o Cond2 o Cond3 o Cond4) 

La legge di De Morgan dice
Not (A or B or C or D) è uguale a Not A And Not B And Not C And Not D
quindi usando De Morgan, abbiamo

  Non Cond1 e non Cond2 e non Cond3 e non Cond4 

Questo è equivalente a:

  • A sinistra a sinistra del lato destro di B, [ RectA.Left < RectB.Right ], e
  • Il lato destro a destra del lato sinistro di B, [ RectA.Right > RectB.Left ], e
  • A è in alto sopra il fondo di B, [ RectA.Top > RectB.Bottom ], e
  • A's bottom below B's Top [ RectA.Bottom < RectB.Top ]

Nota 1 : è abbastanza ovvio che questo stesso principio può essere esteso a qualsiasi numero di dimensioni.
Nota 2 : Dovrebbe anche essere abbastanza ovvio contare le sovrapposizioni di un solo pixel, cambiare il < e / o il > su quel confine con <= o a >= .
Nota 3 : Questa risposta, quando si utilizzano le coordinate cartesiane (X, Y) si basa su coordinate cartesiane algebriche standard (x aumenta da sinistra a destra, e Y aumenta dal basso verso l'alto). Ovviamente, dove un sistema informatico potrebbe meccanizzare le coordinate dello schermo in modo diverso (ad esempio, aumentando Y dall'alto verso il basso o X da destra verso sinistra), la syntax dovrà essere regolata di conseguenza /

 struct rect { int x; int y; int width; int height; }; bool valueInRange(int value, int min, int max) { return (value >= min) && (value <= max); } bool rectOverlap(rect A, rect B) { bool xOverlap = valueInRange(Ax, Bx, Bx + B.width) || valueInRange(Bx, Ax, Ax + A.width); bool yOverlap = valueInRange(Ay, By, By + B.height) || valueInRange(By, Ay, Ay + A.height); return xOverlap && yOverlap; } 
 struct Rect { Rect(int x1, int x2, int y1, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) { assert(x1 < x2); assert(y1 < y2); } int x1, x2, y1, y2; }; bool overlap(const Rect &r1, const Rect &r2) { // The rectangles don't overlap if // one rectangle's minimum in some dimension // is greater than the other's maximum in // that dimension. bool noOverlap = r1.x1 > r2.x2 || r2.x1 > r1.x2 || r1.y1 > r2.y2 || r2.y1 > r1.y2; return !noOverlap; } 

È più facile controllare se un rettangolo è completamente al di fuori dell’altro, quindi se lo è

sulla sinistra…

 (r1.x + r1.width < r2.x) 

o sulla destra ...

 (r1.x > r2.x + r2.width) 

o sopra ...

 (r1.y + r1.height < r2.y) 

o sul fondo ...

 (r1.y > r2.y + r2.height) 

del secondo rettangolo, non può eventualmente scontrarsi con esso. Quindi, per avere una funzione che restituisce un detto booleano che contamina i rettangoli, combiniamo semplicemente le condizioni con OR logici e annulliamo il risultato:

 function checkOverlap(r1, r2) : Boolean { return !(r1.x + r1.width < r2.x || r1.y + r1.height < r2.y || r1.x > r2.x + r2.width || r1.y > r2.y + r2.height); } 

Per ricevere un risultato positivo solo toccando, possiamo cambiare "<" e ">" di "<=" e "> =".

Poniti la domanda opposta: come posso determinare se due rettangoli non si intersecano affatto? Ovviamente, un rettangolo A completamente a sinistra del rettangolo B non si interseca. Anche se A è completamente a destra. E allo stesso modo se A è completamente sopra B o completamente sotto B. In qualsiasi altro caso A e B si intersecano.

Quello che segue può avere bug, ma sono abbastanza fiducioso riguardo all’algoritmo:

 struct Rectangle { int x; int y; int width; int height; }; bool is_left_of(Rectangle const & a, Rectangle const & b) { if (ax + a.width <= bx) return true; return false; } bool is_right_of(Rectangle const & a, Rectangle const & b) { return is_left_of(b, a); } bool not_intersect( Rectangle const & a, Rectangle const & b) { if (is_left_of(a, b)) return true; if (is_right_of(a, b)) return true; // Do the same for top/bottom... } bool intersect(Rectangle const & a, Rectangle const & b) { return !not_intersect(a, b); } 

Supponiamo di aver definito le posizioni e le dimensioni dei rettangoli in questo modo:

inserisci la descrizione dell'immagine qui

L’implementazione del mio C ++ è così:

 class Vector2D { public: Vector2D(int x, int y) : x(x), y(y) {} ~Vector2D(){} int x, y; }; bool DoRectanglesOverlap( const Vector2D & Pos1, const Vector2D & Size1, const Vector2D & Pos2, const Vector2D & Size2) { if ((Pos1.x < Pos2.x + Size2.x) && (Pos1.y < Pos2.y + Size2.y) && (Pos2.x < Pos1.x + Size1.x) && (Pos2.y < Pos1.y + Size1.y)) { return true; } return false; } 

Un esempio di chiamata di funzione secondo la figura sopra riportata:

 DoRectanglesOverlap(Vector2D(3, 7), Vector2D(8, 5), Vector2D(6, 4), Vector2D(9, 4)); 

I confronti all'interno del blocco if avranno il seguente aspetto:

 if ((Pos1.x < Pos2.x + Size2.x) && (Pos1.y < Pos2.y + Size2.y) && (Pos2.x < Pos1.x + Size1.x) && (Pos2.y < Pos1.y + Size1.y)) ↓ if (( 3 < 6 + 9 ) && ( 7 < 4 + 4 ) && ( 6 < 3 + 8 ) && ( 4 < 7 + 5 )) 

Ecco come è fatto nell’API Java:

 public boolean intersects(Rectangle r) { int tw = this.width; int th = this.height; int rw = r.width; int rh = r.height; if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) { return false; } int tx = this.x; int ty = this.y; int rx = rx; int ry = ry; rw += rx; rh += ry; tw += tx; th += ty; // overflow || intersect return ((rw < rx || rw > tx) && (rh < ry || rh > ty) && (tw < tx || tw > rx) && (th < ty || th > ry)); } 
 struct Rect { Rect(int x1, int x2, int y1, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) { assert(x1 < x2); assert(y1 < y2); } int x1, x2, y1, y2; }; //some area of the r1 overlaps r2 bool overlap(const Rect &r1, const Rect &r2) { return r1.x1 < r2.x2 && r2.x1 < r1.x2 && r1.y1 < r2.y2 && r2.x1 < r1.y2; } //either the rectangles overlap or the edges touch bool touch(const Rect &r1, const Rect &r2) { return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 && r1.y1 <= r2.y2 && r2.x1 <= r1.y2; } 

Nella domanda, si collega alla matematica per quando i rettangoli sono ad angoli di rotazione arbitrari. Se capisco il bit degli angoli nella domanda, tuttavia, interpreto che tutti i rettangoli sono perpendicolari tra loro.

Una conoscenza generale dell’area della formula di sovrapposizione è:

Utilizzando l’esempio:

  1 2 3 4 5 6

 1 + --- + --- +
    |  |   
 2 + A + --- + --- +
    |  |  B |
 3 + + + --- + --- +
    |  |  |  |  |
 4 + --- + --- + --- + --- + +
                |  |
 5 + C +
                |  |
 6 + --- + --- +

1) raccogli tutte le coordinate x (sia a sinistra che a destra) in una lista, poi ordinala e rimuovi i duplicati

  1 3 4 5 6 

2) raccogli tutte le coordinate y (sia in alto che in basso) in una lista, quindi ordinala e rimuovi i duplicati

  1 2 3 4 6 

3) creare una matrice 2D per numero di spazi tra le coordinate x univoche * numero di spazi tra le uniche coordinate y.

  4 * 4 

4) dipingere tutti i rettangoli in questa griglia, incrementando il conteggio di ciascuna cella su cui si trova:

    1 3 4 5 6

 1 + --- +
    |  1 |  0 0 0
 2 + --- + --- + --- +
    |  1 |  1 |  1 |  0
 3 + --- + --- + --- + --- +
    |  1 |  1 |  2 |  1 |
 4 + --- + --- + --- + --- +
      0 0 |  1 |  1 |
 6 + --- + --- +

5) Mentre dipingi i rettangoli, è facile intercettare le sovrapposizioni.

Diciamo che i due rettangoli sono il rettangolo A e il rettangolo B. Lasciate che i centri siano A1 e B1 (le coordinate di A1 e B1 possono essere facilmente individuate), che le altezze siano Ha e Hb, larghezza sia Wa e Wb, sia dx sia il larghezza (x) distanza tra A1 e B1 e deve essere l’altezza (y) della distanza tra A1 e B1.
Ora possiamo dire che possiamo dire che A e B si sovrappongono: quando

if (! (dx> Wa + Wb) ||! (dy> Ha + Hb)) restituisce true

Il modo più semplice è

 /** * Check if two rectangles collide * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle */ boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2) { return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2); } 

prima di tutto tieni a mente che nei computer il sistema di coordinate è capovolto. l'asse x è lo stesso della matematica, ma l'asse y aumenta verso il basso e diminuisce andando verso l'alto ... se il rettangolo viene estratto dal centro. se le coordinate x1 è maggiore di x2 più la sua metà della larghezza. allora significa che andranno a metà si toccheranno. e allo stesso modo andando verso il basso + metà della sua altezza. si scontrerà ..

Ho implementato una versione C #, è facilmente convertibile in C ++.

 public bool Intersects ( Rectangle rect ) { float ulx = Math.Max ( x, rect.x ); float uly = Math.Max ( y, rect.y ); float lrx = Math.Min ( x + width, rect.x + rect.width ); float lry = Math.Min ( y + height, rect.y + rect.height ); return ulx <= lrx && uly <= lry; } 

Non pensare alle coordinate come ad indicare dove sono i pixel. Pensa a loro come se fossero tra i pixel. In questo modo, l’area di un rettangolo 2×2 dovrebbe essere 4, non 9.

 bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right) && (A.Bottom >= B.Top || B.Bottom >= A.Top)); 

Ho una soluzione molto semplice

sia x1, y1 x2, y2, l1, b1, l2, sia le coordinate e le lunghezze e le ampiezze rispettivamente

considera la condizione ((x2

ora l’unico modo in cui questo rettangolo si sovrapporrà è se il punto diagonale di x1, y1 giace all’interno dell’altro rettangolo o similmente il punto diagonale a x2, y2 giacerà all’interno dell’altro rettangolo. che è esattamente la condizione di cui sopra implica.

A e B sono due rettangoli. C essere il loro rettangolo di copertura.

 four points of A be (xAleft,yAtop),(xAleft,yAbottom),(xAright,yAtop),(xAright,yAbottom) four points of A be (xBleft,yBtop),(xBleft,yBbottom),(xBright,yBtop),(xBright,yBbottom) A.width = abs(xAleft-xAright); A.height = abs(yAleft-yAright); B.width = abs(xBleft-xBright); B.height = abs(yBleft-yBright); C.width = max(xAleft,xAright,xBleft,xBright)-min(xAleft,xAright,xBleft,xBright); C.height = max(yAtop,yAbottom,yBtop,yBbottom)-min(yAtop,yAbottom,yBtop,yBbottom); A and B does not overlap if (C.width >= A.width + B.width ) OR (C.height >= A.height + B.height) 

Si occupa di tutti i casi possibili.

Questo è dall’esercizio 3.28 del libro Introduction to Java Programming-Comprehensive Edition. Il codice verifica se i due rettangoli sono indentri, se uno è all’interno dell’altro e se uno è al di fuori dell’altro. Se nessuna di queste condizioni viene soddisfatta, le due si sovrappongono.

** 3.28 (Geometria: due rettangoli) Scrivi un programma che richiede all’utente di inserire le coordinate x, y, larghezza e altezza di due rettangoli e determina se il secondo rettangolo si trova all’interno del primo o si sovrappone al primo, come mostrato in Figura 3.9. Metti alla prova il tuo programma per coprire tutti i casi. Ecco le esecuzioni di esempio:

Immettere le coordinate x, y, larghezza e altezza del centro r1: 2.5 4 2.5 43 Immettere le coordinate x, y, larghezza e altezza del centro r2: 1.5 5 0.5 3 r2 è all’interno di r1

Inserisci le coordinate x, y, larghezza e altezza del centro di r1: 1 2 3 5.5 Inserisci le coordinate x, y, larghezza e altezza del centro r2: 3 4 4.5 5 r2 si sovrappongono r1

Inserisci le coordinate x, y, larghezza e altezza del centro di r1: 1 2 3 3 Inserisci le coordinate x, y, larghezza e altezza di r2: 40 45 3 2 r2 non si sovrappone a r1

 import java.util.Scanner; public class ProgrammingEx3_28 { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out .print("Enter r1's center x-, y-coordinates, width, and height:"); double x1 = input.nextDouble(); double y1 = input.nextDouble(); double w1 = input.nextDouble(); double h1 = input.nextDouble(); w1 = w1 / 2; h1 = h1 / 2; System.out .print("Enter r2's center x-, y-coordinates, width, and height:"); double x2 = input.nextDouble(); double y2 = input.nextDouble(); double w2 = input.nextDouble(); double h2 = input.nextDouble(); w2 = w2 / 2; h2 = h2 / 2; // Calculating range of r1 and r2 double x1max = x1 + w1; double y1max = y1 + h1; double x1min = x1 - w1; double y1min = y1 - h1; double x2max = x2 + w2; double y2max = y2 + h2; double x2min = x2 - w2; double y2min = y2 - h2; if (x1max == x2max && x1min == x2min && y1max == y2max && y1min == y2min) { // Check if the two are identicle System.out.print("r1 and r2 are indentical"); } else if (x1max <= x2max && x1min >= x2min && y1max <= y2max && y1min >= y2min) { // Check if r1 is in r2 System.out.print("r1 is inside r2"); } else if (x2max <= x1max && x2min >= x1min && y2max <= y1max && y2min >= y1min) { // Check if r2 is in r1 System.out.print("r2 is inside r1"); } else if (x1max < x2min || x1min > x2max || y1max < y2min || y2min > y1max) { // Check if the two overlap System.out.print("r2 does not overlaps r1"); } else { System.out.print("r2 overlaps r1"); } } } 
 bool Square::IsOverlappig(Square &other) { bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area return result1 | result2 | result3 | result4; } 

Per quelli di voi che utilizzano i punti centrali e le mezze misure per i loro dati rettangolari, invece delle tipiche x, y, w, h o x0, y0, x1, x1, ecco come potete farlo:

 #include  // for fabsf(float) struct Rectangle { float centerX, centerY, halfWidth, halfHeight; }; bool isRectangleOverlapping(const Rectangle &a, const Rectangle &b) { return (fabsf(a.centerX - b.centerX) <= (a.halfWidth + b.halfWidth)) && (fabsf(a.centerY - b.centerY) <= (a.halfHeight + b.halfHeight)); } 

“Se esegui la sottrazione di coordinate x o y corrispondenti ai vertici dei due di fronte a ciascun rettangolo, se i risultati sono lo stesso segno, i due rettangoli non si sovrappongono agli assi che” (mi dispiace, non sono sicuro che la mia traduzione sia corretta )

inserisci la descrizione dell'immagine qui

Fonte: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html

Codice Java per capire se i rettangoli stanno contattando o si sovrappongono l’un l’altro

  for (int i = 0;i < n;i++) { for (int j = 0;j < n; j++) { if (i != j) { Rectangle rectangle1 = rectangles.get(i); Rectangle rectangle2 = rectangles.get(j); int l1 = rectangle1.l; //left int r1 = rectangle1.r; //right int b1 = rectangle1.b; //bottom int t1 = rectangle1.t; //top int l2 = rectangle2.l; int r2 = rectangle2.r; int b2 = rectangle2.b; int t2 = rectangle2.t; boolean topOnBottom = t2 == b1; boolean bottomOnTop = b2 == t1; boolean topOrBottomContact = topOnBottom || bottomOnTop; boolean rightOnLeft = r2 == l1; boolean leftOnRight = l2 == r1; boolean rightOrLeftContact = leftOnRight || rightOnLeft; boolean leftPoll = l2 <= l1 && r2 >= l1; boolean rightPoll = l2 <= r1 && r2 >= r1; boolean leftRightInside = l2 >= l1 && r2 <= r1; boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside; boolean bottomPoll = t2 >= b1 && b2 <= b1; boolean topPoll = b2 <= b1 && t2 >= b1; boolean topBottomInside = b2 >= b1 && t2 <= t1; boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside; boolean topInBetween = t2 > b1 && t2 < t1; boolean bottomInBetween = b2 > b1 && b2 < t1; boolean topBottomInBetween = topInBetween || bottomInBetween; boolean leftInBetween = l2 > l1 && l2 < r1; boolean rightInBetween = r2 > l1 && r2 < r1; boolean leftRightInBetween = leftInBetween || rightInBetween; if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) { path[i][j] = true; } } } } 

...

Questa risposta dovrebbe essere la risposta migliore:

se i rettangoli si sovrappongono, l’area di sovrapposizione sarà maggiore di zero. Ora cerchiamo di trovare l’area di sovrapposizione:

se si sovrappongono, il margine sinistro di overlap-rect sarà il massimo (r1.x1, r2.x1) e il margine destro sarà min (r1.x2, r2.x2). quindi la lunghezza della sovrapposizione sarà min (r1.x2, r2.x2) -max (r1.x1, r2.x1)

quindi l’area sarà: area = (max (r1.x1, r2.x1) – min (r1.x2, r2.x2)) * (max (r1.y1, r2.y1) – min (r1.y2, r2.y2))

se area = 0 non si sovrappongono. Semplice no?