Java controlla se due rettangoli si sovrappongono in qualsiasi punto

Ho più rettangoli e un rettangolo speciale: il rettangolo di selezione. Voglio verificare per ogni rettangolo se il rettangolo contiene almeno un punto che si trova all’interno del rettangolo di selezione. Ecco un’immagine per chiarezza:

Esempio di selezione

Questo troverà se il rettangolo si sovrappone a un altro rettangolo:

 public boolean overlaps (Rectangle r) { return x < rx + r.width && x + width > rx && y < ry + r.height && y + height > ry; } 

Possiamo determinare un rettangolo con solo una delle sue diagonali.
Diciamo che la diagonale del rettangolo di sinistra è (x1, y1) a (x2, y2)
E la diagonale del rettangolo destro è (x3, y3) a (x4, y4)

Campione

Ora, se una di queste 4 condizioni è vera, puoi dire che i rettangoli non si sovrappongono:

  1. x3> x2 (OR)
  2. y3> y2 (OR)
  3. x1> x4 (OR)
  4. y1> y4 inserisci la descrizione dell'immagine qui

Qualsiasi cosa oltre a queste condizioni significa che si stanno sovrapponendo!

Vorrei creare oggetti Rectangle ( http://docs.oracle.com/javase/8/docs/api/java/awt/Rectangle.html ) e quindi utilizzare i metodi Rectangle.intersects e Rectangle.contains per determinare se si intersecano o se uno contiene l’altro.

Dato che hai un grande rettangolo, cioè il rettangolo di selezione, questo è ancora più facile di quanto pensassi. Esegui Rectangle.contains e, per tutti i rettangoli che non sono contenuti, esegui Rectangle.intersects e ottieni ciò che stai cercando.

Ecco un’altra soluzione più semplice:

  // Left x int leftX = Math.max(x1, x3); // Right x int rightX = Math.min(x2, x4); // Bottom y int botY = Math.max(y1, y3); // TopY int topY = Math.min(y2, y4); if (rightX > leftX && topY > botY) return true; 

Se il primo implementa RectangularShape e il secondo è Rectangle2D , puoi semplicemente utilizzare RectangularShape.intersects :

 selectionRectangle.intersects(otherRectangle) 

Verifica se l’interno della forma interseca l’interno di un rettangolo2D specificato

Dai documenti Oracle Java

Due rettangoli non si sovrappongono se una delle seguenti condizioni è vera.
1) Un rettangolo è sopra il bordo superiore dell’altro rettangolo.
2) Un rettangolo si trova sul lato sinistro del bordo sinistro dell’altro rettangolo.

Nota che un rettangolo può essere rappresentato da due coordinate, in alto a sinistra e in basso a destra. Quindi principalmente ci vengono date le seguenti quattro coordinate.
l1: Coordinata in alto a sinistra del primo rettangolo.
r1: coordinata in basso a destra del primo rettangolo.
l2: coordinata in alto a sinistra del secondo rettangolo.
r2: coordinata in basso a destra del secondo rettangolo.

 class Point { int x, y; }; // Returns true if two rectangles (l1, r1) and (l2, r2) overlap bool doOverlap(Point l1, Point r1, Point l2, Point r2) { // If one rectangle is on left side of other if (l1.x > r2.x || l2.x > r1.x) return false; // If one rectangle is above other if (l1.y < r2.y || l2.y < r1.y) return false; return true; } 

Ho un’implementazione generica per i poligoni nel sistema di coordinate GPS, che può essere un po ‘eccessivo per i rettangoli (che sono poligoni semplici); ma funzionerà. Dovrebbe essere abbastanza semplice adattare l’approccio al tuo caso, se per qualsiasi motivo non vuoi usare AWT.

https://github.com/jillesvangurp/geogeometry/blob/master/src/main/java/com/jillesvangurp/geo/GeoGeometry.java#L753 (metodo di sovrapposizione)

Quello che faccio lì è semplicemente controllare se i poligoni hanno punti che sono contenuti nell’altro poligono.

Per il contenimento dei punti dei poligoni, ho un semplice algoritmo che percorre i bordi del poligono per verificare se il punto si trova all’interno o all’esterno di O (n). Per i rettangoli dovrebbe essere economico da gestire.

La cosa bella di questo approccio funzionerà per qualsiasi rettangolo e anche rettangoli ruotati o forms più complesse.

Questa class presuppone che l’ordine left<=right , top<=bottom , x1<=x2 , y1<=y2 :

 public class Rect { int left, right, bottom, top; Rect(int left, int top, int right, int bottom) { this.left = left; this.right = right; this.top = top; this.bottom = bottom; } boolean overlap(int x1, int y1, int x2, int y2) { // if one rectangle is to the left or right, then there can be no overlap if(x2 < left || right < x1) return false; // the x values overlap, but the y values may still lie outside the rectangle // if one rectangle is above or below, then there can be no overlap if(y2 < top || bottom < y1) return false; // otherwise we must overlap ! return true; } } 

Modifica Come menzionato nella risposta accettata, l’object Rettangolo AWT fornisce questa funzionalità con il metodo intersects . Se non si desidera utilizzare AWT o per qualche altro motivo, di seguito è una soluzione variante.

Se vuoi reinventare la ruota, ecco alcune cose. Usando l’immagine di esempio, questo test del rettangolo nero si sovrappone al rettangolo blu. Inoltre, questo presuppone che il contatto non si sovrapponga.

Ogni rettangolo sarà rappresentato da due coppie di coordinate: topLeft e bottomRight.

Ciò presuppone che 0, 0 sia nell’angolo in alto a sinistra.

 Function xOverlapCheck(black, blue) { // black left side overlaps. if ((black.topLeft.x <= blue.bottomRight.x) && (black.topLeft.x >= blue.topLeft.x)) { return true; } // black right side overlaps. if ((black.bottomRight.x <= blue.bottomRight.x) && (black.bottomRight.x >= blue.topLeft.x)) { return true; } // black fully contains blue. if ((black.bottomRight.x >= blue.bottomRight.x) && (black.topLeft.x <= blue.topLeft.x)) { return true; } } Function yOverlapCheck(black, blue) { // black top side overlaps. if ((black.topLeft.y >= blue.topLeft.y) && (black.topLeft.y <= blue.bottomRight.y)) { return true; } // black bottom side overlaps. if ((black.bottomRight.y >= blue.topLeft.y) && (black.bottomRight.y <= blue.bottomRight.y)) { return true; } // black fully contains blue. if ((black.bottomRight.y >= blue.bottomRight.y) && (black.topLeft.y <= blue.topLeft.y)) { return true; } } 

Il nero si sovrappone al blu quando entrambe le funzioni restituiscono true.

Modifica: usa <= e> = per i confronti di sovrapposizione.