Bestimmen Sie, ob zwei Rechtecke einander überlappen?
https://stackoverflow.com/questions/306316
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, ein C++-Programm zu schreiben, das die folgenden Eingaben des Benutzers annimmt, um Rechtecke (zwischen 2 und 5) zu konstruieren:Höhe, Breite, x-Position, y-Position.Alle diese Rechtecke liegen parallel zur x- und y-Achse, das heißt, alle ihre Kanten haben eine Steigung von 0 oder unendlich.
Ich habe versucht, das umzusetzen, was in erwähnt wird Das Frage, aber ich habe nicht viel Glück.
Meine aktuelle Implementierung macht Folgendes:
// 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;
Allerdings bin ich mir nicht ganz sicher, ob (a) ich den Algorithmus, auf den ich verlinkt habe, richtig implementiert habe, oder ob ich das genau interpretiert habe?
Irgendwelche Vorschläge?
Lösung
if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top )
oder mit rechtwinkligen Koordinaten
(Mit X1 coord gelassen zu werden, X2 rechts coord ist, von links nach rechts erhöht und Y1 Top coord zu sein, und Y2 Bottom coord ist, von unten nach oben zu erhöhen) ...
if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1)
Hinweis: Um alle damit die Benutzer mit Editierberechtigung. BITTE STOPPEN MIT DIESER Hantieren.
Sagen Sie Rect A haben, und Rect B. Der Nachweis ist durch Widerspruch. Jeder von vier Bedingungen garantiert, dass kann keine Überschneidungen existieren :
- cond1. Wenn A die linke Rand nach rechts von dem rechten Kante des B ist, - dann ist A total nach rechts von B
- Cond2. Wenn A die rechte Kante links von dem linken Kante des B ist, - dann ist A total nach links von B
- Cond3. Wenn A die Oberkante unterhalb der Unterkante B ist, - dann ist A total unter B
- Cond4. Wenn A der Unterkante oberhalb der Oberkante B ist, - dann ist A total über B
So Bedingung für Nicht-Overlap ist
Cond1 Or Cond2 Or Cond3 Or Cond4
Daher ist eine hinreichende Bedingung für die Overlap ist das Gegenteil.
Not (Cond1 Or Cond2 Or Cond3 Or Cond4)
De Morgans Gesetz sagt
Not (A or B or C or D) ist das gleiche wie Not A And Not B And Not C And Not D
so mit De Morgan, haben wir
Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4
Dies entspricht:
- A linker Rand nach links von B rechten Rand, [
RectA.Left < RectB.Right] und - A rechten Rand nach rechts von der B linken Rand, [
RectA.Right > RectB.Left] und - A die oben oben B unten, [
RectA.Top > RectB.Bottom] und - A die Unterseite unter B Top [
RectA.Bottom < RectB.Top]
Hinweis 1 . Es ist ziemlich offensichtlich, das gleiche Prinzip kann auf eine beliebige Anzahl von Dimensionen erweitert werden
Hinweis 2 :. Es sollte auch ziemlich offensichtlich sein Überlappungen von nur ein Pixel zu zählen, ändern Sie die < und / oder die > an dieser Grenze zu einem <= oder einem >=
Note 3 : Diese Antwort, wenn kartesisch Verwendung (X, Y) auf Standard-algebraischen kartesisch basiert (x steigt von links nach rechts, und Y erhöht unten nach oben). Offensichtlich, wo ein Computersystem könnte Bildschirm mechanisieren Koordinaten unterschiedlich (z.B. Erhöhen Y von oben nach unten, oder X von rechts nach links), die Syntax muß entsprechend eingestellt werden /
Andere Tipps
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(A.x, B.x, B.x + B.width) ||
valueInRange(B.x, A.x, A.x + A.width);
bool yOverlap = valueInRange(A.y, B.y, B.y + B.height) ||
valueInRange(B.y, A.y, A.y + 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;
}
Es ist einfacher, zu überprüfen, ob ein Rechteck vollständig außerhalb des anderen ist, so dass, wenn es entweder
auf der linken Seite ...
(r1.x + r1.width < r2.x)
oder auf der rechten Seite ...
(r1.x > r2.x + r2.width)
oder oben ...
(r1.y + r1.height < r2.y)
oder auf dem Boden ...
(r1.y > r2.y + r2.height)
des zweiten Rechtecks, kann es möglicherweise nicht mit ihm kollidieren. So eine Funktion zu haben, die einen Booleschen sagen Wetter gibt die Rechtecke kollidieren, haben wir einfach die Bedingungen durch logische RUP kombinieren und negiert das Ergebnis:
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);
}
Um bereits ein positives Ergebnis zu erhalten, wenn nur zu berühren, können wir das ändern „<“ und „>“ durch „<=“ und „> =“.
Stellen Sie sich die gegenteilige Frage:Wie kann ich feststellen, ob sich zwei Rechtecke überhaupt nicht schneiden?Offensichtlich schneidet ein Rechteck A ganz links vom Rechteck B nicht.Auch wenn A ganz rechts liegt.Und das Gleiche gilt, wenn A vollständig über B oder vollständig unter B liegt.In jedem anderen Fall schneiden sich A und B.
Was folgt, kann Fehler enthalten, aber ich bin ziemlich zuversichtlich, was den Algorithmus angeht:
struct Rectangle { int x; int y; int width; int height; };
bool is_left_of(Rectangle const & a, Rectangle const & b) {
if (a.x + a.width <= b.x) 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);
}
Nehmen wir an, dass Sie die Positionen und Größen der Rechtecke wie folgt definiert sind:
Meine C ++ Implementierung ist wie folgt:
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;
}
Ein Beispiel Funktionsaufruf entsprechend der gegebenen Abbildung oben:
DoRectanglesOverlap(Vector2D(3, 7),
Vector2D(8, 5),
Vector2D(6, 4),
Vector2D(9, 4));
Die Vergleiche innerhalb des if Block wird wie folgt aussehen:
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 ))
Hier ist, wie es in dem Java-API getan:
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 = r.x;
int ry = r.y;
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));
}
In der Frage, verknüpfen Sie die Mathematik für, wenn Rechtecke sind in beliebigen Drehwinkeln. Wenn ich die etwas über Winkel in der Frage jedoch verstehen, interpretieren ich, dass alle Rechtecke senkrecht zueinander sind.
Eine allgemeine Kenntnis der Überlappungsbereich Formel lautet:
Am Beispiel:
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1) sammelt all x-Koordinaten (links und rechts) in eine Liste, dann sortieren und Duplikate entfernen
1 3 4 5 6
2) Sammle alle y-Koordinaten (oben und unten) in eine Liste, dann Sortieren und Entfernen von Duplikaten
1 2 3 4 6
3) Erstellen einer 2D-Anordnung nach der Anzahl der Lücken zwischen den einzigartig x-Koordinaten * Anzahl der Lücken zwischen den einzigartigen Y-Koordinaten.
4 * 4
4) malen alle Rechtecke in dieses Raster, die Zählung jeder Zelle erhöht wird es erfolgt über:
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) Wenn Sie die Rechtecke malen, ist es einfach die Überlappungen abzufangen.
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;
}
Denken Sie nicht an Koordinaten wie die anzeigt, wo Pixel sind. Denken Sie an sich als zwischen den Pixeln zu sein. Auf diese Weise sollte die Fläche eines 2x2 Rechteck 4, 9 nicht.
bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
&& (A.Bottom >= B.Top || B.Bottom >= A.Top));
Der einfachste Weg ist
/**
* 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);
}
vor allem steckte es in dem Sinne, dass das Koordinatensystem steht auf dem Kopf in Computern. x-Achse ist das gleiche wie in der Mathematik, aber y-Achse nach unten zunimmt und eine Abnahme auf nach oben gehen .. wenn Rechteck sind von Mitte gezogen. wenn x1-Koordinaten größer als x2 plus seine seine Hälfte widht. dann bedeutet es, geht die Hälfte werden sie einander berühren. und auf die gleiche Weise geht nach unten + die Hälfte seiner Höhe. es wird kollidieren ..
Nehmen wir die beiden Rechtecke sind Rechteck A und Rechteck B. dort Zentren A1 sein lassen und B1 (Koordinaten von A1 und B1 können leicht gefunden werden), lassen Sie die Höhen sein Ha und Hb, Breite sein Wa und Wb, lassen dx sein, wobei die Breite (x) Abstand zwischen A1 und B1 und dy wird die Höhe (y) Abstand zwischen A1 und B1.
Jetzt können wir sagen, dass wir A und B Überlappung sagen kann: wenn
if(!(dx > Wa+Wb)||!(dy > Ha+Hb)) returns true
Ich habe eine C # Version implementiert, ist es leicht zu C ++ konvertiert wird.
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;
}
Ich habe eine sehr einfache Lösung
seien x1,y1 x2,y2 ,l1,b1,l2,ihre Koordinaten und deren Länge bzw. Breite
Betrachten Sie die Bedingung ((x2
Jetzt können sich diese Rechtecke nur dann überlappen, wenn der Punkt diagonal zu x1,y1 innerhalb des anderen Rechtecks liegt oder ähnlich der Punkt diagonal zu x2,y2 innerhalb des anderen Rechtecks liegt.was genau die obige Bedingung impliziert.
A und B zwei Rechteck sein. C ihre Abdeckung Rechteck sein.
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)
Es braucht alle möglichen Fälle kümmern.
Dies ist aus Übung 3.28 aus dem Buch Einführung in Java Programmier- Umfassende Ausgabe. Die Code prüft, ob die beiden Rechtecke sind indenticle, ob eine in der anderen ist und ob man sich außerhalb des anderen. Wenn keine dieser Bedingungen erfüllt werden dann die beiden überlappen.
** 3,28 (Geometrie: zwei Rechtecke) Schreiben Sie ein Programm, das den Benutzer auffordert, die einzugeben Zentrum x-, y-Koordinaten, die Breite und die Höhe von zwei Rechtecken und bestimmt, ob das zweite Rechteck ist mit dem ersten in dem ersten oder Überlappungen, wie gezeigt in Abbildung 3.9. Testen Sie Ihr Programm alle Fälle abzudecken. Hier sind die Probeläufe:
Enter r1 Zentrum x-, y-Koordinaten, die Breite und Höhe: 2,5 4 2,5 43 Geben Sie r2 Zentrum x-, y-Koordinaten, die Breite und Höhe: 1,5 5 0,5 3 r2 ist innerhalb r1
Enter r1 Zentrum x-, y-Koordinaten, die Breite und Höhe: 1 2 3 5.5 Geben Sie r2 Zentrum x-, y-Koordinaten, die Breite und Höhe: 3 4 4.5 5 r2 überlappt r1
Enter r1 Zentrum x-, y-Koordinaten, die Breite und Höhe: 1 2 3 3 Geben Sie r2 Zentrum x-, y-Koordinaten, die Breite und Höhe: 40 45 3 2 r2 nicht r1 überlappt
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;
}
Für diejenigen von Ihnen, die Mittelpunkte und halbe Größen für ihre Rechteck Daten verwenden, anstelle der typischen x, y, w, h, oder x0, y0, x1, x1, hier ist, wie Sie es tun können:
#include <cmath> // 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));
}
Diese Antwort sollte die obere Antwort sein:
Wenn die Rechtecken überlappen dann der Überlappungsbereich größer als Null sein wird. Lassen Sie uns nun den Überlappungsbereich finden:
Wenn sie dann den linken Rand des Überlappungs rect überlappen die max(r1.x1, r2.x1) und rechten Rand wird min(r1.x2, r2.x2) werden. So ist die Länge der Überlappung wird min(r1.x2, r2.x2) - max(r1.x1, r2.x1)
So ist der Bereich wird sein:
area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))
Wenn area = 0 dann überlappen sie nicht.
Einfach ist es nicht?
Ein Blick auf die Sache von einer anderen Seite.
Der Fall stellt sich heraus um ganz einfach zu sein, wenn wir das Problem (den Algorithmus) von der anderen Seite betrachten.
Das bedeutet, anstatt die Frage zu beantworten:„Überlappen sich die Rechtecke?“, beantworten wir die Frage:„Sind die Rechtecke? nicht Überlappung?".
Am Ende lösen beide Fragen das gleiche Problem, aber Die Antwort auf die zweite Frage ist einfacher umzusetzen Weil Rechtecke überlappen sich nur dann nicht, wenn eines unter dem anderen liegt oder wenn eines weiter links vom anderen liegt (es reicht aus, wenn einer dieser Fälle eintritt, es kann aber natürlich vorkommen, dass beide gleichzeitig eintreten – hier ist ein gutes Verständnis der logischen Bedingung „oder“ wichtig).Dies reduziert viele Fälle, die bei der ersten Frage berücksichtigt werden müssen.
Die ganze Sache ist auch durch die Verwendung geeigneter Variablennamen vereinfacht:
#include<bits/stdc++.h>
struct Rectangle
{
// Coordinates of the top left corner of the rectangle and width and height
float x, y, width, height;
};
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
// Declaration and initialization of local variables
// if x and y are the top left corner of the rectangle
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
// The main part of the algorithm
// The first rectangle is under the second or vice versa
if (top1 < bottom2 || top2 < bottom1)
{
return false;
}
// The first rectangle is to the left of the second or vice versa
if (right1 < left2 || right2 < left1)
{
return false;
}
// Rectangles overlap
return true;
}
Sogar Wenn wir eine andere Darstellung eines Rechtecks haben, ist es einfach, die obige Funktion daran anzupassen, indem wir nur den Abschnitt ändern, in dem die Variablenänderungen definiert sind. Der weitere Teil der Funktion bleibt unverändert (die Kommentare werden hier natürlich nicht wirklich benötigt, ich habe sie aber hinzugefügt, damit jeder diesen einfachen Algorithmus schnell verstehen kann).
Ein Äquivalent aber vielleicht etwas weniger lesbar Form der obigen Funktion könnte so aussehen:
bool areRectanglesOverlap(Rectangle rect1, Rectangle rect2)
{
float left1, top1, right1, bottom1, left2, top2, right2, bottom2;
left1 = rect1.x;
top1 = rect1.y;
right1 = rect1.x + rect1.width;
bottom1 = rect1.y - rect1.height;
left2 = rect2.x;
top2 = rect2.y;
right2 = rect2.x + rect2.width;
bottom2 = rect2.y - rect2.height;
return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
„Wenn Sie Subtraktion x oder y-Koordinaten entsprechend den Eckpunkten der beiden jedes Rechteck mit Blick auf ausführen, wenn die Ergebnisse die gleichen Vorzeichen aufweisen, wobei die beiden Rechteck nicht überlappen Achsen, dass“ (Es tut mir leid, ich bin mir nicht sicher, Übersetzung ist korrekt)
Quelle: http : //www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
Java-Code, um herauszufinden, ob Rectangles werden kontaktieren oder überlappend sie
...
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;
}
}
}
}
...
